분할정복

Devied And Conquer(분할정복) 정의 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 직접 풀 수 있는 문제가 간단해질 때까지 재귀적으로 분할하고 부속문제들의 해답들이 다시 합쳐서 해결하자는 개념 문제를 더 이상 나눌 수 없을 때까지 나눈 후 문제들을 해결하며 병합하여 결과 값을 얻는 알고리즘 알고리즘 설계 방법 (1) Devied(분할) : 문제가 분할이 가능한 경우, 2개 이상 하위 문제로 나눈다. (2) Recursion(재귀) : 재귀적으로 부속문제들을 푼다. (3) Conquer(정복) : 해답들을 적절하게 합친다. 중요사항 문제를 잘 나누는 것 문제를 잘 합치는 것 분할 정복 기법에서는 재귀를 이용하여 비슷한 종류의 부속 문제들을 해결 장점 어려운 문제를 해결한다..