분할 정복
분할 정복이란 크고 방대한 문제를 조금씩 나눠가면서 쉽게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 문제를 해결하는 방법이다.
설계
분할 정복은 세 단계로 설계할 수 있다.
(1) Divide
기존 문제를 작은 문제로 나누는 Divide단계
(2) Conquer
나누어진 각 부분 문제를 해결(정복)하는 Conquer단계
(3) Combine
해결한 부분 문제들을 합쳐 기존 문제를 해결하는 Combine단계
기존 문제를 바로 풀 수 없다면 Divde로 문제를 나누면 되는데 Divide로 나눈 후 나눈 부분 문제가 Base Case인지 Recursive Case인지 구분하면 된다.
Base Case는 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않아도 바로 답을 구할 수 있는 경우를 의미한다.
Recusrive Case는 문제가 커서 바로 답을 알 수 없어서, 같은 형태의 부분 문제들로 쪼개야 하는 경우를 의미한다.
문제를 Base Case가 나올 때까지 Divide한 다음에 답을 구한(Conquer) 후 부분 문제들의 결합(Combine)으로 기존 문제를 해결해 나가면 된다.
예시
예를 들어 1~8까지의 합을 구해보자.
(1) Divide
1~8(Recursive Case)까지의 합을 바로 구하기 어려우므로
1~4 , 5~8을 각각 구하는 경우로 나누자.
1~4, 5~8(Recursive Case)을 구하는 것도 어려우므로 1~2, 3~4, 5~6, 7~8을
각각 구하는 것으로 나누자.
1~2, 3~4, 5~6, 7~8(Recursive Case)을 구하는 것도 어려우므로 각각의 경우를 또 나누어보자.
1~1, 2~2, 3~3, 4~4, 5~5, 6~6, 7~7, 8~8(Base Case)은 바로 답을 구할 수 있다.
(2) Conquer
1~1 = 1
2~2 = 2
3~3 = 3
4~4 = 4
5~5 = 5
6~6 = 6
7~7 = 7
8~8 = 8
(3) Combine
이제 기존 문제들을 풀어보자
1~2 = 1+2 = 3
3~4 = 3+4 = 7
5~6 = 5+6 = 11
7~8 = 7+8 = 15
1~4 = 3+7 = 10
5~8 = 11+15 = 26
1~8 = 10+26 = 36
분할 정복 vs 다이나믹 프로그래밍
공통점 : 기존 문제를 작은 문제로 나눔
차이점 :
- 분할 정복 : 부분 문제 독립적
부분 문제가 다른 부분 문제에 영향 안 미침, 1~4의 합 계산하는데 5~8의 합은 아무 영향 없음 - 다이나믹 프로그래밍 : 부분 문제 종속적
부분 문제가 다른 부분 문제에 영향 미침, 피보나치 수열의 셋째 항의 값이
피보나치 수열의 넷째 항의 값 구할 때 영향 미침.
