[Algorithm] Divide & Conquer (분할 정복)

Divide & Conquer

📢 부분 문제로 나누어 각각을 해결 하여 전체 문제를 해결하는 방법

---

🔎 분할 정복 의미

• 각 문제를 두 개 이상의 부분 문제로 나누어서 전체 문제를 해결하는 알고리즘이에요.
• 재귀 호출을 이용하여 해결해요.
• 아래의 3가지 요소를 가져요.
  • 더 작은 문제로 분할하기 (divide)
  • 더 작은 문제에서 구한 답을 원래 문제의 답으로 병합하기 (merge)
  • 더이상 분할하지 않고 답을 구할 수 있는 문제 (base case)

---

💡 분할 정복을 나타낸 그림

• 각 문제를 2개 이상의 부분 문제로 나타낸 것을 확인할 수 있어요.
• base case 문제까지 분할 후 위의 그림의 역 방향으로 답을 합쳐나가요.
• 큰 문제를 잘게 쪼개는 과정을 잘 설계하는 것이 중요해요.

💡 일반 재귀 호출을 나타낸 그림

일반적인 재귀 호출을 사용하게 된다면 분할 정복 보다 더 많은 문제 수가 생겨서 효율적이지 않아요.

---

📋 예제

백준 10830 - 행렬 제곱

백준 10830 - 해답

백준 2630 - 색종이 만들기

백준 2630 - 해답