1. 분할 정복 알고리즘
분할정복알고리즘이란?
분할과 정복이라는 이름에 걸맞게, 해결하려고 하는 문제를 작은 문제로 분할하여 큰 문제를 정복하는 알고리즘이다.
분할정복의 3단계
1. Divide -> 기존 문제를 작은 부분 문제들로 나눈다.
2. Conquer -> 각 부분 문제를 해결(정복)
3. Combine -> 부분문제들의 솔루션을 통해 기존 문제를 해결
이 때 2. Conquer 과정은 다시 Divide, Conquer, Combine의 과정을 거쳐 풀기도 한다. -> 재귀적
Base Case vs Recursive Case
Divide 단계에서 기존 문제를 작은 부분으로 나눌 때 무조건 나누는 것이 아니라,
Base Case인지, Recursive Case 인지를 판단해야 한다.
- Base Case : 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않아도 바로 답을 알 수 있는 경우
- Recursive Case : 문제가 커서 바로 답을 알 수 없어서, 같은 형태의 부분 문제들로 쪼개서 풀어야 하는 경우
2. 합병 정렬
- 단순하지 않은 정렬 시리즈 중 가장 단순한 정렬이다.
- 분할 정복 알고리즘이다.
- 분할 후 정복
- 모든 숫자를 다 나눈 다음에 병합하는 방식으로 정렬을 진행한다.
->그룹이 만들어지고 그 그룹이 합해지면서 더 큰 그룹으로 합쳐지는 방식이다.
- 정확히 반절씩 나눈다는 점에서 편량되게 분할될 가능성이 없으므로 최악의 경우에도 O(nlogn)의 시간복잡도를 보장한다. (평균적으로 퀵정렬보다 빠르진 않다.)
- 기본 아이디어: 일단 정확히 반으로 나누고 나중에 정렬하는 것
시간 복잡도
- Worst: O(nlogn)
- Average: O(nlogn)
- Best: O(nlogn)
3. 퀵 정렬
- 분할 정복 알고리즘이다.
- 정복 후 분할하는 알고리즘
- 각 부분문제의 크기가 일정하지 않은 형태일 때 사용
- 피벗(Pivot-기준값)이 존재한다.
- 피벗을 기준으로 더 작은 것은 왼쪽에, 더 큰 것은 오른쪽으로 옮긴다.
- 피벗은 적당히 물리적으로 중간에 있는 값을 선택한다.
Partitioning
- start값과 end값을 선택한다.
- start는 pivot보다 작은 값들을 무시하면서 뒤로 간다. pivot값보다 큰 값을 만나면 기다린다.
- end는 pivot보다 큰 값들을 무시하면서 앞으로 간다. pivot값보다 작은 값을 만나면 기다린다.
- start와 end가 모두 멈춘 상태일 때 두 값을 바꿔주고, start 포인터와 end 포인터를 한 칸씩 옮겨준다.
- 이를 반복하다가, start와 end가 만나면 루프를 빠져나온다.
Partitioning이 끝나면 pivot 왼쪽은 pivot보다 작은 값, pivot 오른쪽은 pivot보다 큰 값이 남는다.
(pivot을 기준으로 오른쪽 또는 왼쪽에 배열 방이 하나도 남지 않으면 더 이상 그쪽으로는 진행하지 않게 해야한다. 하지만 그게 아니라면 start와 end를 왼쪽 오른쪽으로 나누어 다시 진행해준다.)
퀵정렬-재귀
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
lesser_arr, equal_arr, greater_arr = [], [], []
for num in arr:
if num < pivot:
lesser_arr.append(num)
elif num > pivot:
greater_arr.append(num)
else:
equal_arr.append(num)
return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)
퀵정렬-최적화
def quick_sort(arr):
def sort(low, high):
if high <= low:
return
mid = partition(low, high)
sort(low, mid - 1)
sort(mid, high)
def partition(low, high):
pivot = arr[(low + high) // 2]
while low <= high:
while arr[low] < pivot:
low += 1
while arr[high] > pivot:
high -= 1
if low <= high:
arr[low], arr[high] = arr[high], arr[low]
low, high = low + 1, high - 1
return low
return sort(0, len(arr) - 1)
'알고리즘 > 알고리즘' 카테고리의 다른 글
[알고리즘] 3. 최근접 점의 쌍 찾기 알고리즘 (3) (0) | 2022.03.29 |
---|---|
[알고리즘] 3. 선택 문제 알고리즘 (2) (0) | 2022.03.29 |
동적 계획 알고리즘 (0) | 2022.03.20 |
[알고리즘/개념정리] 2. 알고리즘이란? (0) | 2022.03.15 |
알고리즘 시간복잡도로 평가하기 (0) | 2021.03.19 |