분할 정복 솔루션

[1. 개요]

문제를 한 조각과 나머지 전체로 나누는 완전 탐색과 달리

거의 같은 크기의 부분 문제로 나누는 점에서 분할 정복은 완전 탐색과 다르다고 볼 수 있다.

 

분할 정복을 사용하는 알고리즘은 보통 아래와 같은 형태로 구성된다.

1. 문제를 분할 하는 과정 (Divide)
2. 분할하여 해결 한 답을 전체의 답으로 병합하는 과정 (Merge)
3. 더 이상 분할하지 않고 바로 풀 수 있는 작은 문제 (Base case)
   => 꼭, 더 이상 분할 할 수 없는 경우가 아니더라도
   => 이 구간 혹은 이번 부분 문제에서 원하는 답을 구할 수 없겠다 싶으면,
   => 더 이상 분할하지 않고 넘어 갈 수 있다.
   단, 이 구간에서 초기화 해야 될 값이 있으면, 스킵으로 인해 이 값이 적절히 초기화는 시켜주어야 한다.

구현 패턴

1. 기저 사례 처리 (바로 종료 가능)
   => head > tail 인지 확인도 하는 것이 좋다.
2. [head, mid] 에 대한 재귀 호출
3. [mid+1, tail] 에 대한 재귀 호출
4. [head, tail] 에 대한 문제 풀이

분할 정복은 구현 패턴 중 4단계가 핵심이라 볼 수 있다.

O(N) 으로 해결 가능 한 문제가 대부분이지만,

 

경우에 따라서는 완전 탐색을 하는 경우도 발생할 수 있다.

단, 아래와 같이 가지치기를 통해 탐색 속도를 향상 할 수 있다.

• 완전 탐색 할 대상을 선별 
• 스위핑을 통한 탐색 (적절한 기준을 갖고 데이터가 정렬되어 있어야 한다.)
  => 분할 정복 실행 전 정렬 기준과 같다면 무의미 하므로, 기존과 다른 기준으로 정렬 할 필요가 있다.
• 등호 조심...

 

4번 단계가 O(N) 으로 해결 가능한 경우

• 먼저 [mid, mid+1] 구간을 먼저 해결한다.
  => mid 는 왼쪽 구간, mid+1 은 오른쪽 구간에 속하였으므로, 이 두가지를 선택하는 경우는 체크 된 적 없다.
• while (l > left || r < right) 
  => if         ## 왼쪽 오른쪽 모두 갈 수 있는 경우
  => else if ## 왼쪽으로만 갈 수 있는 경우
  => else    ## 오른쪽으로만 갈 수 있는 경우

 

---

[2. 예제]

1. https://testkernelv2.tistory.com/456
2. https://testkernelv2.tistory.com/487
3. https://testkernelv2.tistory.com/511
4. https://testkernelv2.tistory.com/514
5. e
6. f
7. g
8. h