D&C (1) 썸네일형 리스트형 25. Divide and Conquer 분할 정복(Divide and Conquer)은 큰 문제를 여러 개의 작은 부분 문제로 분할한 다음 각각의 부분 문제를 해결하고, 그 결과를 바탕으로 큰 문제의 답을 구하는 문제 해결 방법이다. 동적 계획법과 설명이 비슷하지만 동적 계획법에서는 중복되는 부분 문제가 있었다. 분할 정복의 부분 문제들은 서로 중복되지 않는다. 분할 정복에도 기저 사례가 존재하며, 기저 사례는 더 작은 부분 문제로 분할하지 않고 바로 해결할 수 있다. 분할 정복 자체가 재귀함수를 이용하여 구현하는 경우가 많기 때문에 코드에 자연스럽게 추가되기도 한다. BOJ 1629. 곱셈 (Silver I) 지수가 큰 경우의 거듭제곱을 구하는 문제가 분할 정복을 사용하는 대표적인 예시이다. 지수가 크기 때문에 $B$번 반복되는 반복문을 쓰.. 이전 1 다음
