목록분할정복 (1)

영아일지

코딩테스트 - 분할정복 알고리즘

분할정복 알고리즘 큰 문제를 하위 문제로 분할하고, 각 하위 문제를 독립적으로 해결한 후 그 결과를 결합하여 최종 결과를 얻는다 (일반화) - 특징 분할 정복 알고리즘의 시간 복잡도 O(n^log_b(a)) - 절차 1. 분할 : 주어진 문제를 동일한 크기의 하위 문제로 분할 2. 정복 : 하위 문제를 재귀적으로 해결 3. 결합 : 각 하위 문제의 결과를 결합 - 기본적인 예시 (이진 검색) def binary_search(arr, low, high, target): if high >= low: mid = (high + low) // 2 if arr[mid] == target: return mid elif arr[mid] > target: return binary_search(arr, low, mid -..
디지털/코딩테스트 2023. 4. 27. 16:54
이전 Prev 1 Next 다음