| English | 의미 |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | 분할 정복 |
| merge sort/mɜːdʒ sɔːt/ | 병합 정렬 |
| merge/mɜːdʒ/ | 병합 |
재귀와 검색 및 정렬
- 동일한 분할 정복 divide-and-conquer 원리가 재귀 이진 검색과 합병 정렬 merge sort의 핵심이다.
- 문제를 반으로 나누고, 각 반을 해결한 뒤 합친다.
- 재귀 이진 검색은 한쪽 반에 대해 본인을 호출하여 검색한다.
- 합병 정렬은 각 반을 정렬한 뒤, 정렬된 반들을 합병(merge) 시킨다.
재귀 이진 검색
- 기저 사례: 빈(empty) 범위라면 목표가 발견되지 않음을 의미한다.
- 중간(mid) 요소를 본다.它就是目标，则返回其索引。
- 목표가 작으면 왼쪽 반에 대해 재귀(recurse)하고, 크면 오른쪽 반에 대해 재귀한다.
- 각 호출마다 범위가 절반으로 줄어든다—동일한
O(log n)이지만 재귀 형태로 구현되었다.
합병 정렬
- 배열을 두 반으로 나눈다(split) ; 각 반을 재귀적으로 정렬(sort recursively) 한다.
- 기저 사례: 0개 또는 1개 요소의 배열은 이미 정렬된 상태이다.
- 합병(merge) : 두 정렬된 반을 동시에Walk하며, 항상 앞쪽에서 더 작은 요소를 취한다.
n²정렬보다 훨씬 빠르다—약n log n의 작업량이 걸린다.
분할 정복이勝利的原因
- 매 단계마다 문제를 절반으로 줄이면
log n인자가 됩니다. - 큰 배열에서 병합 정렬의
n log n가 선택 정렬/삽입 정렬의n²보다 우수합니다. - 기저 사례(빈 배열 또는 1개 요소)가 모든 가지(branch)를 멈춘다.
- 모든 재귀와 동일한 형태: 아래로 분할하고, 위로 결합(combine)한다.
재귀 이진 탐색은 목표가 한쪽에만 존재하므로 한쪽 반만 재귀적으로 탐색합니다; 병합 정렬은 두 반 모두에 대해 재귀를 수행한 후 병합합니다. 두 알고리즘 모두 기저 사례(base case)가 필요합니다. 탐색에서는 빈 범위는 "발견되지 않음"을 의미하며, 병합 정렬에서는 0개 또는 1개 요소로 구성된 배열은 이미 정렬된 상태입니다. 분할 정복이 이들 알고리즘의 빠른 성능(O(log n) 및 O(n log n))을 결정합니다.
[3, 1, 2, 4]에 대한 합병 정렬:
- ⟨
[3, 1]⟩와 ⟨[2, 4]⟩로 나눈다; 각각 정렬 → ⟨[1, 3]⟩와 ⟨[2, 4]⟩. - 합병: 1, 2, 3, 4을 순서대로 취함 → ⟨
[1, 2, 3, 4]⟩. - 각 병합 단계에서는 앞쪽 요소 중 작은 것을 순서대로 선택합니다.
재귀 이진 탐색은 한쪽 반에 대해 재귀를 수행하며(기본 경우: 빈 범위 = 미발견), O(log n) 검색을 위한 것입니다. 병합 정렬은 양쪽 반에 대해 재귀를 수행하고 병합하며(기본 경우: 0 또는 1개 요소), O(n log n) 정렬을 위한 것입니다. 둘 다 분할 정복 전략입니다: 아래로 나누고 다시 위로 합칩니다 — n²보다 훨씬 빠릅니다.
병합 정렬은 반으로 나누고, 위쪽으로 병합합니다
단일 요소는 정렬됨(기본 경우); 병합은 위쪽으로 결합합니다.
재귀 이진 검색은 ...에서 재귀합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
타겟은 중간값의 한쪽에만 있습니다.
병합 정렬은 ...에서 재귀합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
각 반을 정렬한 후 두 정렬된 반을 병합합니다.
병합 정렬의 기본 경우는 ...인 배열입니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
하나(또는 영개)의 요소는 정렬이 필요 없습니다.
병합 정렬의 실행 시간은 약 ...입니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
splitting의 log n 레벨, 각 레벨당 n의 작업량.
재귀 이진 검색과 병합 정렬 모두 분할 정복(dive-and-conquer) 알고리즘입니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
두算法 모두 문제를 반으로 나누고 재귀합니다.
반 [1,3]과 [2,4]에 대한 병합 단계를 정리하십시오.
난이도 3/5 · 200 코인 + 오늘 첫 완료 시 소액 보너스
항상 작은 앞쪽 요소를 취함: 1, 2, 3, 4.