이진 검색

분할 정복(divide and conquer) 알고리즘 개념 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 기법이다. 재귀적으로 구현한다. 대표적인 예시로는 병합 정렬(Merge Sort), 이진 검색(Binary Search), 거듭 제곱(Exponentiation), 퀵 정렬(Quick Sort)이 있다. 이 외로는 행렬 곱셈(Matrix Multiplication), 최대 부분 합(Maximum Subarray)이 있다. 설계 1) Divide(분할): 주어진 문제를 분할한다. 단, 문제를 적절한 크기로 분할하는 것이 중요하다. (최소 2개 이상) 2) Conquer(정복): 각 하위 문제들을 재귀적으로 해결한다. 나눌 수 없으면 탈출 조건을 설정하고, 문제를 해결한다. 3) Combine(..