분할과 정복 내용정리

분할 정복 알고리즘 이란?

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

일반적으로 재귀 함수로 구현한다.

설계 단계

• Divide (분할) : 문제가 분할이 가능한 경우, 원래 문제를 분할하여 더 작은 하위 문제들로 분할한다.
• Conquer (정복) : 나누어진 문제가 여전히 분할이 가능하다면, 다시 Divide 수행하고 그렇지 않다면 문제를 해결한다.
• Combine (합치기): 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)를 구한 값