Divide and Conquer

분할 정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다.

Divide and Conquer알고리즘이란 하나의 문제를 작은 단위로 나누어 재귀적으로 각 문제를 해결한 후 이를 다시 합쳐 원래 문제를 해결하는 방법이다.

분할정복 알고리즘은 일반적으로 재귀함수를 통해 자연스럽게 구현된다.

def F(x):
  if F(x)의 문제가 간단:
    return F(x)을 직접 계산한 값
  else:
    x를 y1, y2로 분할
    F(y1)과 F(y2)를 호출
    return F(y1), F(y2)로부터 F(x)를 구한 값

Divide and Conquer 설계

• Divide : 문제가 분할이 가능한 경우 2개 이상의 문제로 나누고, 더이상 분할이 불가능할 때 까지 반복한다. 단, 분할된 문제들은 모두 독립적이어야 한다.
• Conquer : 더이상 분할이 불가능한 문제를 푼다
• Merge : Conquer가 완료된 문제들을 합쳐 원래 문제의 답을 찾는다

Divide and Conquer알고리즘은 Subproblem이 전체 문제에 비해 크기가 매우 작을 때 유리하다(N -> N/2 -> N/4 ...)

Divide and Conquer의 장단점

• 장점 : 큰 문제를 나누어 해결하기 떄문에 간단하고 빠르게 문제를 해결할 수 있고, 병렬처리가 가능하다
• 단점 : 재귀적으로 문제를 해결하기 때문에 메모리 사용량이 높다.

Divide and Conquer의 종류

• Merge Sort
• Quick Sort
• Heap Sort
• Binary Search
• 최대/최솟값 찾기