🦝 분할정복
그 자체로 해결하기 힘든 문제를 작은 문제로 분할하여 해결하는 방법이다.
divide : 기존 문제를 작은 부분 문제로 나눈다.
conquer : 각 부분 문제를 해결(정복)한다.
combine : 부분 문제들의 답을 통해 기존 문제를 해결한다.
정복하는 것도 작은 divide, conquer, combine 과정이 반복되며 보통 재귀적으로 해결된다고 볼 수 있다.
재귀적으로 문제 해결 시에는 아래와 같은 부분을 생각해볼 수 있다.
-
base case : 이미 문제가 충분히 작아서 더 작은 문제로 나누지 않아도 바로 답을 알 수 있는 경우
-
recursive case : 문제가 커서 바로 답을 알 수 없으며, 같은 형태의 부분 문제로 쪼개어 문제를 풀어야 하는 경우
ex_1) 1~8까지의 합을 구하는 문제
1~4 → 1~2, 3~4 → 1, 2, 3, 4 (모두 base case가 되도록 한다.)
5~8 → 5~6, 7~8 → 5, 6, 7, 8 (모두 base case가 되도록 한다.)
🐼 동적계획법과 분할정복법의 차이
주요 차이는 memoization의 여부이다.
ex) 피보나치 수열 계산
-
동적계획법 : 중복되는 부분 문제가 있는 경우, 굳이 하나하나 재계산하지 않고, 저장해두었다가 재사용한다.
-
분할정복법 : 부분 문제들을 독립적으로 해결한다. 부분문제 중복이 없으며, memoization을 이용하지 않는다. 분할의 깊이가 깊어질 수록 계산의 중복 횟수가 지수적으로 증가한다.
두 방법의 주요 차이는 top-down, bottom-up이라기보다 memoization의 여부라고 생각한다.
문제 조건에 따라 top-down, bottom-up 접근법은 달라질 수 있다고 생각하기 때문이다. 동적계획법은 분할정복법의 중복을 줄이기 위한 분할정복법의 확장의 느낌이다.
그래도 보통 코드를 작성해보면 분할정복(top-down), 동적계획법(bottom-up)의 경향이 있다.
동적계획법에서 top-down형식으로 푼 피보나치 계산의 경우, 접근 방식의 관점에서 보았을 때 memoization을 이용하지 않고 중복 계산을 이뤘기 때문에 분할정복법(top-down)으로 접근한 것으로 판단할 수 있었다.
실제로 문제를 풀 때, 중복이 발생하는 경우 memoization을 이용하지 않고 접근한다면 에러가 발생할 여지가 있다.
