컴퓨터 알고리즘 Ch05

Recursive algorithm

나 자신을 호출하는 재귀적(순환적)인 알고리즘

분할 정복 또한 이러한 재귀적인 알고리즘 중 하나이다.

Divide and Conquer (분할 정복)

1. divide : 큰 문제를 작은 문제로 나눔
2. conquer : 작은 문제를 재귀적으로 해결
3. combine : 해결된 작은 문제들을 결합하여 원래 문제의 답을 찾음

• top-down(하향식) 문제해결 방법론
• 시스템적인 측면에서 살펴보면 함수가 재귀적으로 호출되어 stack에 쌓이며 문제가 분할되고, stack을 비워내며 작게 나눠진 문제를 정복해 나가게 된다.
  
• 수학적으로는 f(g(h(x)))

▶ Merge 분할 정복 방식을 사용하여 효율적으로 해결할 수 있는 문제 4가지