분할정복(Divide and conquer)

분할정복은 주어진 문제를 작은 사례로 나누고(Divide) 각각의 문제들을 해결하여 정복(Conquer)하는 알고리즘이다.

1. 시간복잡도

• 모든 경우에 대해 NlogN이다
  

2. 분할정복 설계

(1) Divide

• 원래 문제가 분할하여 더 작은 하위 문제로 분할이 가능할 때 까지 나눈다.

(2) Conquer

• 각 하위의 문제를 재귀적으로 해결한다.

(3) Combine

• 정복한 문제들을 통합하여 원래 문제의 잡을 얻어 해결한다.

💯 백준 1074_Z

https://www.acmicpc.net/problem/1074