공부해라 공부 공부해라 공부

공부/알고리즘

• 원형 큐 알고리즘

  공부/알고리즘 2024. 6. 15. 15:00

  pseudocode원형 큐 생성 : font, rear 0으로 초기화createQUeue() cQ[n]; front

  Read More
• 알고리즘 정리

  공부/알고리즘 2023. 10. 9. 09:54

  이것이 코딩테스트다 참고하여 작성 https://github.com/ndb796/python-for-coding-test GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소 github.com 저자 깃허브 chapter3.그리디 https://github.com/Zzang-yeah/codingTest_python/blob/master/codingTest_Python/c..

  Read More
• KMP, 라빈 카프 알고리즘

  공부/알고리즘 2021. 6. 15. 16:43

  백준 5525번 풀다가 모르겠어서 질문 검색란 보니 요런 알고리즘이 있길래 정리 https://www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 문자열 검색 시 가장 간단한 방법을 생각해보자면 한자리씩 옮겨가면서 비교하는 방법이 떠오를 것 백준 문제를 예시로 들어보자 O O I O I O I O I I O I I I O I OOI!=IOI 불일치 O O I O I O I O I I O I I I O I OIO!=IOI 불일치 O O I O I O I O I I O I I I O I IO..

  Read More
• DFS/BFS

  공부/알고리즘 2021. 5. 29. 14:20

  DFS(Depth-First Search) 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 모든 노드를 방문하고자 할 때 유용, 스택이용 동작 과정 : 1)탐색 시작 노드를 스택에 삽입하고 방문처리 2)스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리, 방문합지 않은 인접 노드가 없으면 스택에서 최상단 노드를 pop BFS(Breadth First Search) 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘 두 노드 사이의 최단 거리나 임의의 경로를 찾고 싶을 때 유용, 큐 이용 동작 과정 : 1)탐색 시작 노드를 큐에 삽입하고 방문처리 2)큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입, 방문 ..

  Read More
• 구현

  공부/알고리즘 2021. 5. 29. 14:18

  피지컬로 승부하기구현하기 어려운 문제 ex)알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는(파싱을 해야 하는)문제 등 -> 사소한 조건 설정이 많은 문제시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 구현 시 고려해야할 메모리 제약 사항 int 자료형 데이터의 개수에 따른 메모리 사용량데이터의 개수(리스트의 길이)메모리 사용량 1,000 약 4KB 1,000,000 약 4MB 10,000,000 약 40MB 파이썬은 자료형을 지정할 필요도..

  Read More
• 그리디 알고리즘

  공부/알고리즘 2021. 5. 29. 14:16

  그리디 알고리즘이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법->매순간 가장 좋아보이는 것을 선택, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형 ex)가장 큰 순서대로, 가장 작은 순서대로 *다익스트라 알고리즘은 그리디 알고리즘이면서 암기가 필요한 알고리즘 그리디 알고리즘의 정당성 모든 문제에 적용할 수 있는 것은 아님->탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을때 사용! 대표적 그리디 알고리즘 문제 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔,..

  Read More