이 장에서는 작은 입력으로 네 가지 알고리즘을 손으로 따라가 봅니다. 병합 정렬, 병합하면서 역순 쌍 세기, 빠른 거듭제곱, 퀵셀렉트입니다. 추적을 한 번 직접 해 보면 다음 장의 코드가 훨씬 쉽게 읽힙니다.
여덟 개 수의 병합 정렬
[5, 2, 4, 7, 1, 3, 2, 6]을 예로 듭니다. 조각마다 원소가 하나 남을 때까지 절반으로 자른 뒤, 아래 단계부터 차례로 병합합니다.
단계마다 모든 원소를 한 번씩 다루고 단계 수는 log2 8 = 3입니다. 여기서 O(n log n)이 나옵니다. 병합은 정렬된 두 목록의 맨 앞 원소를 비교해 작은 쪽을 꺼내는 일을 되풀이합니다.
def merge(left, right):
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= 를 쓰면 같은 값의 순서가 유지된다(안정 정렬)
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
print(merge([2, 4, 5, 7], [1, 2, 3, 6])) # [1, 2, 2, 3, 4, 5, 6, 7]
병합하면서 역순 쌍 세기
역순 쌍(inversion)은 i < j이면서 a[i] > a[j]인 위치 쌍입니다. 모든 쌍을 확인하면 O(n^2)이 듭니다. 분할 정복에서는 역순 쌍을 세 종류로 나눕니다. 두 원소가 모두 왼쪽 절반에 있는 쌍, 모두 오른쪽 절반에 있는 쌍, 양쪽에 하나씩 있는 쌍(경계를 넘는 쌍)입니다. 앞의 두 종류는 재귀 호출이 세고, 경계를 넘는 쌍은 병합하면서 거의 공짜로 셉니다. right[j]가 left[i]보다 먼저 꺼내지면 그 값은 left[i]와 그 뒤에 남은 왼쪽 원소 모두보다 작으므로 len(left) - i개의 역순 쌍을 만듭니다.
위 추적의 마지막 병합, [2, 4, 5, 7]과 [1, 2, 3, 6]을 따라가 봅니다.
마지막 병합에서 11이 더해집니다. 아래 단계에서는 [5]와 [2]의 병합에서 1, [2, 5]와 [4, 7]에서 1(4가 5보다 작음), [1, 3]과 [2, 6]에서 1(2가 3보다 작음)이 더해지므로 이 배열의 역순 쌍은 모두 14개입니다. 값이 같을 때(2 <= 2) 왼쪽을 먼저 꺼내므로 같은 값은 역순 쌍으로 세지 않습니다.
빠른 거듭제곱
e가 크면 b를 e - 1번 곱하는 방법은 쓸 수 없습니다. 대신 지수를 절반으로 줄입니다. e가 짝수면 b^e = (b^(e/2))^2, 홀수면 b^e = (b^((e-1)/2))^2 * b입니다. 호출마다 e가 절반이 되므로 곱셈은 많아야 약 2 log2 e번입니다.
3^13을 추적해 봅니다(13은 이진수로 1101).
def power(b, e):
if e == 0:
return 1
half = power(b, e // 2)
return half * half * b if e % 2 else half * half
print(power(3, 13)) # 1594323
곱셈 열두 번이 호출 다섯 번으로 줄었습니다. e = 10^18이라면 10^18단계 대신 약 60번의 호출로 끝납니다.
퀵셀렉트
퀵셀렉트는 전체를 정렬하지 않고 k번째(0부터)로 작은 원소를 찾습니다. 퀵 정렬처럼 피벗을 기준으로 분할한 뒤, 위치 k가 들어 있는 쪽에서만 계속합니다.
마지막 원소를 피벗으로 쓰는 경우를 a = [7, 2, 9, 4, 1, 8, 3], k = 3으로 추적합니다.
첫 단계 이후로는 분할할 때마다 원소가 하나씩만 줄어듭니다. 피벗을 잘못 고르면 이렇게 최악의 경우 O(n^2)이 됩니다. 피벗을 무작위로 고르면 이런 일이 일어날 가능성이 매우 낮아져 기대 시간이 O(n)이 됩니다.
import random
def quickselect(a, k):
"""a 에서 k 번째(0부터)로 작은 원소. a 의 순서를 제자리에서 바꾼다."""
lo, hi = 0, len(a) - 1
while lo < hi:
p = random.randint(lo, hi) # 무작위 피벗
a[p], a[hi] = a[hi], a[p]
pivot, store = a[hi], lo
for i in range(lo, hi): # 로무토 분할
if a[i] < pivot:
a[i], a[store] = a[store], a[i]
store += 1
a[store], a[hi] = a[hi], a[store]
if k == store:
return a[k]
if k < store:
hi = store - 1
else:
lo = store + 1
return a[k]
print(quickselect([7, 2, 9, 4, 1, 8, 3], 3)) # 4
정리
- 병합 정렬의 실제 작업은 병합에 있습니다.
O(n) 작업이 log n 단계 반복됩니다. - 오른쪽 원소가 먼저 꺼내질 때마다
len(left) - i만큼 경계를 넘는 역순 쌍이 생깁니다. - 빠른 거듭제곱은 지수를 절반씩 줄여 곱셈을
O(log e)번만 합니다. - 퀵셀렉트는 한쪽에서만 계속하며, 무작위 피벗으로 기대 시간
O(n)을 얻습니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.