분할정복

 

Divide & Conquer

• 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘
• 분할정복 알고리즘의 핵심은 "문제를 잘게 쪼개기", 하지만 문제를 쪼개는 방법에 대해서 정해진 규칙은 없다
• 분할정복의 3가지 구성요소
  1. divide : 문제를 더 작은 문제로 분할
  2. base case : 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제
  3. merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합
• 분할시 생기는 각 하위 문제는 완전히 독립접이므로 네트워크상의 여러 컴퓨터에 의해 병렬처리가 가능

 

예제 BOJ 1780 - 종이의 갯수 https://www.acmicpc.net/problem/1780