+ 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다.
분할 정복 기법 (Divide-and-Conquer)
문제의 크기가 커지면 더 풀기가 어렵다.
=> Divide: 원래 문제를 독립적으로 풀 수 있는 작은 문제로 나눈다.
=> Delegate: 각각의 문제를 푼다.
=> Combine: 각각의 문제의 답을 이용하여 원래 문제의 답을 만든다.
정렬 문제에 대한 분할 정복 기법
1. 병합 정렬 (Mergesort)
2. 퀵 정렬 (Quicksort)
병합 정렬
Divide: 정렬할 리스트를 앞쪽 반, 뒤쪽 반으로 나눈다.
Delegate: 앞쪽 반을 정렬한다.
Delegate: 뒤쪽 반을 정렬한다.
Combine: 이 둘을 합쳐서 하나의 정렬된 리스트를 만든다.
- 앞쪽 반, 뒤쪽 반은 병합 정렬로 재귀적으로 정렬한다.
- 리스트의 길이가 1이면 그 자체가 정렬되어 있다 .
- 또는, 어느 정도 길이 이하라면 다른 방법으로 정렬할 수 있다.
import random
def mergesort(arr):
if len(arr) < 2: # 배열의 길이가 1이면
return arr # 그 자체로 정렬되어 있음
mid = len(arr) // 2 # 가운데 인덱스
A = mergesort(arr[:mid]) # 반으로 나눈 배열 (좌)
B = mergesort(arr[mid:]) # 반으로 나눈 배열 (우)
#print(f"{arr}를 두 배열로 분할 후 정렬: {A}와 {B}")
C = [] # 정렬된 배열을 병합하여 저장
# 병합 시작
while 0 < len(A) and 0 < len(B): # 어느 한 쪽이 모두 없어지면 종료
if A[0] < B[0]: # A와 B는 이미 정렬되어 있으므로 맨 앞 인덱스 부터 비교
C.append(A.pop(0))
else:
C.append(B.pop(0))
# 한 쪽 배열이 크기가 0이라면 나머지 배열을 C 뒤에 붙이기
C += A
C += B
#print(f"병합 {C}")
return C
List = list(range(20))
random.shuffle(List)
print(List)
print(mergesort(List))
< 병합 과정의 정확성 >
- A, B 둘 중 하나가 비어 있는 경우, 나머지 하나는 이미 정렬되어 있으므로 병합 결과는 그 자신이다.
- A, B 모두 비어 있지 않은 경우, 리스트에 들어가는 원소는 모든 원소 중 가장 작다.
- 재귀적으로 진행되는 과정에서, A, B 둘 중 하나는 원래보다 원소가 하나 작다.
< 병합 과정의 시간 복잡도 >
최적: 두 리스트가 서로 교차되는 부분이 없을 때 => n / 2
ex) A = 1 2 3 4 5, B = 6 7 8 9 10
최악: 두 리스트가 서로 모두 교차할 때 => n - 1 = Θ(n) (마지막 하나는 비교 X)
ex) A = 1 3 5 7 9, B = 2 4 6 8 10
< 공간 복잡도 >
A, B를 복사하는 경우 => 2n
Linked List로 구현하는 경우 => n
< 병합 정렬의 시간 복잡도 >
맨 마지막에는 원소 하나를 가지는 리스트이고, 정렬된 리스트를 연속으로 병합한다.
점화식: T(n) = 2T(n/2) + n => T(n) = Θ(n×log(n))
2T(n/2): 두 개의 배열을 정렬하는 데 걸리는 시간
n: 두 개의 배열을 병합하는 데 걸리는 시간
- 입력의 형태에 상관없이 언제나 같은 시간 복잡도를 보장한다.
- 언제나 문제의 크기가 1 / 2로 줄어든다.
- 실제로는 원소들이 더 자주 움직이므로 시간이 더 많이 걸린다. (재귀는 더 시간이 걸린다.)
퀵 정렬의 경우, 일단 순서가 정해진 원소는 움직이지 않으므로 가장 빠르다.
퀵 정렬
가장 널리 쓰이는 정렬 알고리즘이다.
1. 특정 원소를 중심으로 작은 것들은 왼쪽, 큰 것들은 오른쪽 옮긴다.
=> 왼쪽, 오른쪽에 있는 원소들의 순서와는 무관하게 특정 원소의 순서는 결정된다. (최종 위치가 바로 결정)
2. 왼쪽에 있는 원소들을 퀵 정렬, 오른쪽에 있는 원소들을 퀵 정렬한다. (재귀적 반복)
< 특정 원소를 중심으로 왼쪽, 오른쪽으로 나누는 방법 >
1. 맨 왼쪽 원소(= 특정 원소)를 비운다. (빈 칸)
2 - 1. 맨 오른쪽 원소부터 특정 원소보다 크면 그대로, 작으면 빈 칸으로 이동한다. (빈칸 위치 변경)
+ 빈칸의 위치가 변경되면 반대쪽 원소부터 비교
2 - 2. 맨 왼쪽 원소부터 특정 원소보다 작으면 그대로, 크면 빈 칸으로 이동한다.
3. 마지막 빈 칸에 특정 원소를 넣는다.
< 퀵 정렬 동작 예제 - 추가적인 메모리 없이 정렬>
5 1 3 7 6 2 8 4
_ 1 3 7 6 2 8 4
4 1 3 7 6 2 8 _
=> 특정 원소보다 작으므로 위치 변경 => 조건 변경
4 1 3 7 6 2 8 _
4 1 3 7 6 2 8 _
=> 특정 원소보다 작으므로 위치 변경 X
4 1 3 7 6 2 8 _
4 1 3 7 6 2 8 _
=> 특정 원소보다 작으므로 위치 변경 X
4 1 3 7 6 2 8 _
4 1 3 _ 6 2 8 7
=> 특정 원소보다 크므로 위치 변경 => 조건 변경
4 1 3 _ 6 2 8 7
4 1 3 _ 6 2 8 7
=> 특정 원소보다 크므로 위치 변경 X
4 1 3 _ 6 2 8 7
4 1 3 2 6 _ 8 7
=> 특정 원소보다 작으므로 위치 변경 => 조건 변경
4 1 3 2 6 _ 8 7
4 1 3 2 _ 6 8 7
=> 특정 원소보다 크므로 위치 변경
4 1 3 2 5 6 8 7
=> 특정 원소 삽입
+ 왼쪽 배열과 오른쪽 배열을 붙이는 방법을 이용하면 더 쉽지만 메모리 낭비가 심하다.
(크기가 n-1인 왼쪽, 오른쪽 배열을 생성해야한다.)
import random
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0] # 특정 원소
left = []
right = []
for num in arr:
if num < pivot:
left.append(num)
elif num > pivot:
right.append(num)
return quicksort(left) + [pivot] + quicksort(right)
List = list(range(8))
random.shuffle(List)
print(List)
print(quicksort(List))
< 퀵 정렬의 시간 복잡도 >
최선의 경우: 기준의 왼쪽, 오른쪽에 같은 수의 원소가 이동하는 경우 (가운데)
- (n-1) / 2 개 이지만 편의상 n / 2로 계산
T(n) = 2T(n/2) + n = Θ(n logn)
최악의 경우: 기준의 왼쪽 또는 오른쪽 한 쪽으로만 원소가 쏠린 경우
T(n) = T(n-1) + n = Θ(n^2)
평균적인 경우: 복잡
극단적인 경우 (1%와 99%로 왼쪽, 오른쪽이 나뉜 경우): T(n) = T(99n/100) + T(n/100) + n = Θ(n × logn)
< 난수를 이용한 퀵정렬 >
import random
def randomizedquicksort(L):
if (len(L) == 1) or (len(L) == 0):
return L
pivot = int(random.random() * len(L))
left = []
right = []
for x in L[:pivot]+L[pivot+1:]:
if (x < L[pivot]):
left.append(x)
else:
right.append(x)
return randomizedquicksort(left) + [L[pivot]] + randomizedquicksort(right)=> 최악의 경우를 피하기 위해 기준을 첫 번째 원소가 아니라 랜덤으로 고른다면 확률이 작아진다.
'Study > Algorithm Study' 카테고리의 다른 글
| [Algorithm] 정렬: 버킷 정렬, 기수 정렬 (0) | 2023.09.24 |
|---|---|
| [Algorithm] 정렬: 힙 정렬 (1) | 2023.09.24 |
| [Algorithm] 정렬: 버블 정렬, 삽입 정렬 (2) | 2023.09.17 |
| [Algorithm] 알고리즘 기초 (3) (0) | 2023.09.16 |
| [Algorithm] 알고리즘 기초 (2) (0) | 2023.09.05 |
