목록divide and conquer (1)

Little bIT awesome

[Week3] 분할 정복 (Divide and Conquer)

분할 정복 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬이나 합병 정렬이 있으며, 이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제들이 대표적이다. 분할 정복 설계 1) Divide 원래 문제를 더 작은 하위 문제로 분할하는 과정이다. 이 단계에서 문제를 해결하기 쉬운 형태로 나누어야 한다. 이 과정은 주어진 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 나눌 수 있을 때까지 계속된다. 2) Conquer 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다. 3) Combine (= Merge) Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 ..
코딩테스트/알고리즘 정리 2024. 2. 16. 21:22
이전 Prev 1 Next 다음