분할정복(백준 알고리즘 10830번)
♣ 분할정복(divide and conquer)하나의 문제를 작은 문제로 분할하여 해결하는 방법을 의미한다. 퀵 정렬, 합병 정렬, 이진탐색, 선택 문제, 고속푸리에 변환 문제들이 대표적으로 분할정복 알고리즘으로 해결할 수 있는 문제들이다. ♣ 분할정복 설계1. Divide문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할때까지 나눈다. 2. Conquer각 하위 문제를 재귀적으로 해결한다. 하위 문제가 더 이상 나눌 수 없는 단위가 되면 탈출 조건을 설정하여 해결한다. 3. CombineConquer한 문제들을 통합하여 원래의 문제의 답을 얻어 해결한다. ♣ 분할 정복의 특징 및 장단점1. 분할된 작은 문제는 원래 문제와 성격이 동일하다2. 분할된 문제는 서로 독립적이다. 3...
2024.06.06