Algorithm/개념

분할 정복(divide and conquer) 알고리즘 개념 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 기법이다. 재귀적으로 구현한다. 대표적인 예시로는 병합 정렬(Merge Sort), 이진 검색(Binary Search), 거듭 제곱(Exponentiation), 퀵 정렬(Quick Sort)이 있다. 이 외로는 행렬 곱셈(Matrix Multiplication), 최대 부분 합(Maximum Subarray)이 있다. 설계 1) Divide(분할): 주어진 문제를 분할한다. 단, 문제를 적절한 크기로 분할하는 것이 중요하다. (최소 2개 이상) 2) Conquer(정복): 각 하위 문제들을 재귀적으로 해결한다. 나눌 수 없으면 탈출 조건을 설정하고, 문제를 해결한다. 3) Combine(..
- 탐색 알고리즘 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. DFS, BFS는 그래프 탐색 알고리즘에 속한다. - 그래프 노드(Node)와 간선(Edge)으로 이루어진 자료구조의 일종 간선으로 연결되어 있는 노드들을 인접하다(adjacent)라고 표현된다. 구현하는 방식 → 인접 행렬, 인접 리스트 인접 리스트 graph = [ [1, 2, 3], [0, 3], [0, 3], [0, 1, 2] ] 각각의 인덱스에 해당하는 노드에 연결된 노드들을 리스트 형태로 저장하는 방식 연결 리스트를 활용하여 표현하는 방식 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 인접 행렬 graph = [[0, 1, 1, 1], [1, 0, 0, 1], [1, 0, 0, 1], [1, 1, ..