[Week02] 분할정복 (Divide & Conquer)

분할정복?

: 문제를 더 이상 나눌 수 없을 때까지 나눈 후 각각 풀고 그 후 다시 합병하여 문제의 답을 얻는 알고리즘

 

설계요령

1) Divide : 문제의 분할이 가능할 시, 2개 이상의 문제로 나눔

2) Conquer : 나누어진 문제를 해결

3) Combine : Conquer한 문제들을 결합

 

대표적인 예

: 병합정렬, 거듭제곱, 피보나치 수열 등

 

Base Case & Recursive Case

1) Base Case : 더 이상 divide 할 수 없는 상태

2) Recursive Case : 문제들을 나눠야 하는 상황

 

출처 : 파이썬 알고리즘 인터뷰 (나무위키)

 

출처

https://namu.wiki/w/%EB%B6%84%ED%95%A0%20%EC%A0%95%EB%B3%B5%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

분할 정복 알고리즘 - 나무위키

 

https://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5

[알고리즘] Divide and Conquer (분할정복)

 

https://youtu.be/qDEKiNzAH1U