17251 분할 정복(Divide and Conquer) 목차 분할 정복(Divide and Conquer) 분할 정복은 큰 문제를 독립적인 작은 문제들로 나누어 해결합니다. 각각의 작은 문제들은 독립적으로 해결되며, 결합 단계에서 이러한 작은 문제들의 해답을 결합하여 큰 문제의 해답을 얻습니다. 따라서 재귀형태로 구현하는 경우가 많습니다. 대표적인 예시로는 병합 정렬(merge sort), 이분 탐색(binary search) ,거듭제곱 연산(a^n)등이 있습니다. 병합 정렬 이분탐색 거듭제곱 연산 기본적인 거듭제곱 연산의 시간복잡도는 O(n)입니다. 이는 'a'를 'n'번 곱하는 것을 의미합니다. 분할 정복을 사용하면 이를 O(log n)으로 줄일 수 있습니다. 분할정복과 Top-Down 방식의 DP와 차이점 분할정복은 DP의 Top-Down 방식과 유사합.. 2023. 10. 12. 이전 1 다음
