분할정복 알고리즘이란?
분할정복(Divide and Conquer)은 문제를 작은 부분 문제로 나누고, 각각을 해결한 후 전체 문제의 답을 구하는 알고리즘 기법이다.
보통 재귀(Recursion)를 활용해 문제를 점진적으로 해결한다.
분할정복의 3단계는 다음과 같다.
- 분할(Divide) - 문제를 더 작은 부분 문제로 나눈다. (보통 원래 문제의 크기를 절반씩 줄여가며 나눈다)
- 정복(Conquer) - 나눈 부분 문제를 각각 해결한다. (보통 부분 문제의 크기가 충분히 작아질 때까지 재귀적으로 수행된다)
- 결합(Combine) - 해결된 부분 문제의 결과를 결합하여 원래 문제의 해답을 도출한다.
분할정복의 대표적인 예시인 합병정렬(merge sort)을 보며 동작 과정을 이해해보자.
/ discusschool
먼저 리스트를 절반씩 나누며 문제의 크기를 줄여간다.
절반으로 나눠진 리스트들을 재귀적으로 정렬하고 하나로 합친다.
문제를 작은 부분 문제로 나눈다는 점에서 동적계획법(DP)와 유사하지만 목적과 사용방법에 차이가 있다.
분할정복은 문제를 독립적인 부분 문제로 나누어 해결 후 병합한다.
부분 문제 간의 중복이 없거나 적을 때 효과적이고 보통 재귀를 이용해 구현한다.
대표적인 예시로 합병 정렬, 퀵 정렬, 이진 탐색이 있다.
반면에 동적계획법은 하위 문제를 해결하고, 그 결과를 재사용해 상위 문제를 해결한다.
부분 문제가 중복되어 재활용이 가능할 때 효과적이고 재귀와 반복문을 이용해 구현한다.
대표적인 예시로 피보나치 수열, 배낭 문제, 최장 공통 부분 수열이 있다.
문제의 특성을 보고 분할정복과 동적계획법 중 적합한 알고리즘 기법을 선택해 사용해야 한다.
