반응형 합병정렬1 분할 정복법(Divide & Conquer)과 합병 정렬(Merge Sort) 분할 정복법(Divide & Conquer)이란 분할 정복법은 주어진 문제를 작은 단위로 분할(Divide)하여 작은 단위부터 정복(Conquer)하는 방식입니다. 일반적으로 재귀식을 사용해 큰 문제를 최대한 작게 쪼개고, 이 부분들을 하나씩 해결해 나갑니다. 순차적 방법보다 비교적 성능이 좋으며 대표적으로 O(n log n)의 성능을 갖는 합병정렬과 퀵정렬이 있습니다. 분할 정복법 설계전략 분할 정복법의 설계전략은 3단계의 하향식(top-down) 해법을 사용합니다. 1. 분할 해결하기 쉽게 큰 문제를 여러 개의 작은 부분으로 분할합니다. 2. 정복 분할된 문제들을 각각 해결(정복)하여 부분 해를 구합니다. 3. 통합 필요하다면 부분 해를 통합하여 전체 해를 구합니다. 이러한 방식으로 이루어지는 분할 .. 2022. 2. 22. 반응형 이전 1 다음
오픈 채팅
