분할정복 알고리즘

개요

분할정복이란?

• 문제를 작은 부분문제들로 쪼개어 각 부분문제들을 해결한 뒤, 각 부분문제들의 정답을 활용하여 기존 문제를 해결하는 기법이다.

분할정복 과정

1. Divide
   • 기존 문제를 작은 부분문제들로 나누는 과정이다.
2. Conquer
   • 각 부분문제들을 해결하는 과정이다.

     이때 다시 1~3번 과정을 거칠 수 있다. 즉, 분할 정복을 재귀적으로 다시 적용할 수 있다.
     자세한 것은 아래에서 다룬다.

3. Combine
   • 부분문제들의 솔루션을 통해, 기존 문제를 해결하는 과정이다.

Divide를 하기전에 고려해야 하는 사항

• 주어진 문제가 Base Case 인지, Recursive Case 인지 판단해야 한다.
  • Base Case: 이미 문제가 충분히 작아서, 더 작은 부분문제로 나누지 않아도 바로 답을 구할 수 있는 경우
  • Recursive Case: 문제가 커서 바로 답을 알 수 없기 때문에, 같은 형태의 부분 문제들로 쪼개서 풀어야 하는 경우

예시 문제) 1~8까지의 합 구하기

풀이과정