[알고리즘] 분할 정복이란 (divide conquer)

분할정복(divide and conquer)

분할정복이란

• 두괄식으로 설명하자면 큰 문제를 작은 문제로 나눠서 작은 문제의 문제들을 해결하고
• 그 해결한 값으로 큰문제를 해결하는 해결 방식이다.

분할정복의 구성

• divide(분할) : 문제를 작은 크기의 문제들로 나눈다
• conquer(정복): 더 이상 나눌 수 없는 문제라면 해를 구한다.
• conbine : 작은 문제의 해를 합쳐서 original 문제의 해를 구한다.
• conquer은 더 나눌수 있는 문제라면 위 방식을 재귀적으로 반복한다.큰문제 (divide) → 작은 문제 작은 문제 (conquer)하지만 더 나눌수 있다면 divide
• ex)

분할 정복 예

• 거듭 제곱 예
• 3^8을 구한다고 가정
  • 3을 한번씩 8번 곱할 수 있음
  • 하지만 분할정복을 사용하면

 

• 위 같이 분할 되는 것을 볼 수있다.
• 3^8에서 3^4 3^4로 divide 하였다.
• 하지만 3^4는 더 나눌수 있으므로 divide한다
• 결국 3^1로 더 나눌수 없고 이제 서브 문제들을 conbine하면서 해를 구해나간다.
• 위 그림만 보면 더 비효율적일거란 생각이 들것이다.
• 하지만 실질적으로 우리가 계산하는 순간은 33 , 3^23^2,3^4*3^4이다
• 3을 8번 곱하는 연산보다 연산 횟수가 줄어드는 것을 볼 수 있다.

 

이처럼 큰문제를 작은문제로 나누고 작은 문제들의 조합으로 큰문제를 해결하는것을 분할 정복이라 한다.