분할정복
-
[알고리즘] 분할 정복STUDY/Algorithm 2021. 4. 9. 14:51
분할정복 분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각의 문제를 해결하고, 이를 다시 합쳐 문제의 답을 얻는 알고리즘이다. - 분할 정복의 설계 전략 1. Divide : 문제가 분할 가능한 경우, 2개 이상의 문제로 나눈다. 2. Conquer : 나누어진 문제가 여전히 분할 가능하면 다시 분할을 수행한다. 그렇지 않으면 문제를 해결한다. 3. Combine : Conquer 한 문제를 다시 통합하여 원래 문제의 답을 얻는다. 장점 : 문제를 나눔으로써 어려운 문제를 해결할 수 있다. 병렬적으로 문제를 해결하는데 큰 장점이 있다. 단점 : 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생한다. 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나..