분할 정복
2024. 3. 6. 15:58
정의
- 문제를 즉각 해결할 수 있을 때까지 재귀적으로 둘 이상의 하위 문제(sub-problem)들로 나누고(Divide) 문제를 해결한 다음(Conquer) 그 결과를 이용해 다시 전체 문제를 해결하며 합치는 방법
- 큰 문제를 작은 문제로 나누어(분할), 각각을 해결(정복)한 후, 작은 문제들의 해결 방법을 통합하여 전체 문제의 해답을 찾는 전략. 재귀적인 성질을 가지고 있다.
분할정복 방식으로 해결되는 문제들
- 정렬 문제 (퀵 정렬, 병합 정렬)
- 큰 숫자 곱하기 - n자리 수 2개를 곱하여 결과를 나타내는 알고리즘
- 이진 탐색
- Closest Pair of Points : 모든 Point의 쌍의 거리 중 최소의 거리를 찾는 문제
- Strassens's 알고리즘 : 두 행렬을 곱하는 효과적인 알고리즘
핵심 진행 방식
- 분할 : 동일한 타입의 하위 문제로 큰 문제를 분할한다.
- 주어진 문제를 두 개 이상의 작은 문제로 나눈다. 이때, 나누어진 작은 문제들은 원래 문제의 부분문제로서, 가능한 한 동일한 유형의 문제여야 한다.
- 정복 : 재귀적으로 하위 문제들을 해결한다.
- 나누어진 작은 문제들이 충분히 작아서 쉽게 해결할 수 있을 때까지 분할을 반복한다. 그리고 각각의 작은 문제를 해결한다.
- 병합 : 적절히 해결된 결과를 사용해 큰 문제를 해결한다.
- 작은 문제들의 해결책을 결합하여 원래 문제의 해결책을 얻는다.
분할 정복 알고리즘의 예
- 병합 정렬(Merge Sort) : 배열을 반으로 나누고, 각 부분 배열을 재귀적으로 정렬한 다음, 두 부분 배열을 병합하여 정렬된 전체 배열을 얻는다.
- 퀵 정렬(Quick Sort) : 배열에서 하나의 '피벗' 요소를 선택하고, 피벗보다 작은 요소들과 큰 요소들로 배열을 두 부분으로 나누며, 이를 재귀적으로 반복하여 전체 배열을 정렬한다.
- 이진 검색(Binary Search) : 정렬된 배열에서 특정 값의 위치를 찾기 위해 배열을 반으로 나누고, 찾고자 하는 값이 중간 값보다 작은지 또는 큰지에 따라 검색 범위를 반으로 줄여가며 찾는다.
- 퀵셀렉트(QuickSelect) : 퀵 정렬과 유사한 방식으로, 배열 내에서 k번째로 작은(또는 큰) 요소를 찾는다. 전체 배열을 정렬하지 않고도 원하는 요소를 효율적으로 찾을 수 있다.
- 스트라센의 행렬 곱셈 : 행렬을 작은 행렬로 나누고, 이 작은 행렬들을 이용해 원래 행렬의 곱을 계산한다.
분할 정복 vs 다이나믹 프로그래밍
분할 정복
- 큰 문제를 작은 문제로 나누어 해결하는 방식이다.
- 이 과정에서 Top-Down 접근 방식을 사용한다. 큰 문제를 먼저 보고 이를 작은 문제로 분할하여 해결해 나간다.
- 분할 정복에서는 각 문제가 독립적으로 해결되며, 같은 문제를 여러 번 해결하지 않는다.
동적 프로그래밍
- 복잡한 문제를 더 작고 간단한 하위 문제들로 나누어 해결하는 방식이지만, 이때 중복되는 하위 문제들의 해결 결과를 저장해두고 재사용하는 것이 핵심이다.
- Bottom-Up : 작은 문제부터 시작하여 점차 큰 문제로 나아가며 해결한다. 하위 문제의 해결 결과를 테이블에 저장해 나가면서 최종적으로 원하는 문제의 해결책을 얻는다.
- Top-Down : 큰 문제를 해결하기 위해 작은 문제로 나누어 나가며, 이 과정에서 메모이제이션 기법을 사용하여 이미 해결된 하위 문제의 결과를 저장하고 재사용한다. 재귀 호출을 사용하여 구현된다.
왜 동적 프로그래밍은 Bottom-Up도 가능한가?
- 이 방식이 문제를 해결하기 위해 필요한 모든 하위 문제를 체계적으로 해결하고 그 결과를 저장하기 때문이다. 이렇게 하면, 각 하위 문제를 정확히 한 번씩만 해결하게 되며, 이후에 해당 문제의 해결이 필요할 때는 저장된 값을 재사용할 수 있다.
- 문제를 작은 단위부터 시작하여 점차 큰 단위로 확장해 나가는 방식이므로, 문제의 구조와 상관없이 일관된 방식으로 접근할 수 있다. 반면 Top-Down 방식은 큰 문제를 해결하는 과정에서 필요한 하위 문제를 동적으로 결정하며 진행한다.
쿼드 트리 1992
