문제를 분할하여 해결하는 것을 '분할 정복(Divide and Conquer) 기법'이라고 한다.
1805년 아우스터리츠 전투에서 나폴레옹이 사용한 전략에서 유래하였다. (전력이 우세한 연합군을 공격하기 위해 나폴레옹은 연합군의 중앙부로 쳐들어가 연합군을 둘로 나누었음)
분할 정복(Top-down 접근법)의 설계 전략
분할(Divide): 해결할 문제를 여러 개의 작은 부분으로 나눔
정복(Conquer): 나눈 작은 문제를 각각 해결함
통합(Combine): (필요시) 해답을 모음
📌 가짜 동전 찾기 n개의 동전 중 가짜 동전이 하나 포함되어 있을 때, 진짜 동전들은 무게가 동일하고 가짜 동전은 진짜 동전에 비해 아주 조금 가볍다고 한다. 양팔 저울을 최소로 사용하여 가짜 동전을 찾는 방법은 무엇인가?
✅ 거듭 제곱 문제
분할 정복 기법을 사용해 자연수 C의 n제곱 값을 구하는 함수를 구현해보자.
반복을 사용한 알고리즘의 시간복잡도: O(n)
분할 정복 기반의 알고리즘의 시간복잡도: O(log_2 n)
분할 정복 기법으로 구현
# 분할 정복 기법(Divide and Conquer)
def recursive_power(x, n):
if n == 1:
return x
if n % 2 == 0:
y = recursive_power(x, n/2)
return y ** 2
else:
y = recursive_power(x, (n - 1) / 2)
return (y ** 2)* x
result = recursive_power(2, 3)
print(result) # 8
[분할 단계] 분할 정복 알고리즘을 활용하여 자료를 분할한다. → Top-down 방식으로 자료를 최소 단위 문제까지 나눈 후에 차례로 정렬하여 최종 결과를 얻어냄
[병합 단계] 2개의 부분집합을 정렬하면서 하나의 집합으로 병합한다. → Bottom-top 방식으로 진행함
외부 정렬(External Sort)의 기본이 되는 정렬 알고리즘이다.
멀티코어(Multi-Core) CPU나 다수의 프로세서에서 정렬 알고리즘을 병렬화하기 위해 병합 정렬 알고리즘이 활용된다.
📌 {69, 10, 30, 2, 16, 8, 31, 22}를 병합 정렬해보자. 분할 단계 과정병합 단계 과정
# 1. 분할 과정
def merge_sort(arr):
global cnt
if len(arr) <= 1:
return arr
middle = len(arr) // 2
left = arr[:middle]
right = arr[middle:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
# 2. 병합 과정
def merge(left, right):
result = []
l = r = 0
while l < len(left) or r < len(right):
if l < len(left) and r < len(right):
if left[l] <= right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
elif l < len(left):
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
return result
arr = [69, 10, 30, 2, 16, 8, 31, 22]
arr = merge_sort(arr)
print(arr) # [2, 8, 10, 16, 22, 30, 31, 69]
평균 시간복잡도: O(n log n) → 곱해진 n은 partitioning, 그리고 log n이 정렬에 해당하는 시간복잡도이다.
Partitioning이라는 과정을 반복한다.
매우 큰 입력 데이터에 대해 좋은 성능을 보인다.
❔ 병합 정렬(merge-sort)과 동일한 것 아닌가요?
병합 정렬과 비슷해보이지만 아래와 같이 차이점이 있어요. 1. 병합 정렬은 그냥 두 부분으로 나누는 반면, 퀵 정렬은 기준 아이템(pivot item)을 중심으로 분할합니다. 2. 각 부분 정렬이 끝난 후, 병합 정렬은 '병합'하는 후처리 작업이 필요하지만 퀵 정렬은 그렇지 않아요.
💡 Partitioning(파티셔닝)이란?
1. 작업 영역을 정한다. 2. 작업 영역 중 가장 왼쪽에 있는 수를 pivot(기준)으로 삼는다. 3. pivot을 기준으로 왼쪽에는 pivot보다 작은 수를, 오른쪽에는 pivot보다 큰 수를 배치한다.
▶ 파티셔닝(partitioning)이 끝난 후의 pivot 위치는 정렬이 완료된 후의 위치와 동일하다.
📌 호어 분할(Hoarse-Partition)기법 1. 피벗(pivot)을 가장 좌측 요소로 초기화한다. 2. left는 피벗(pivot) 다음 요소로, right는 가장 오른쪽 요소로 초기화한다. 3. left는 배열을 순회하며 피벗(pivot)보다 큰 값을 찾고, right는 배열을 순회하며 피벗(pivot)보다 작은 값을 선택하여 두 값을 swap한다. 3-1. 3번을 반복하여 left와 right의 위치가 서로 엇갈리는 경우, 피벗(pivot)과 right를 swap한다.
📌 로무토 분할(Lomuto-Partition)기법 1. 피벗(pivot)을 가장 우측의 요소로 초기화한다. 2. left는 (배열의 가장 왼쪽 요소 인덱스) - 1 의 값으로 초기화되고, right는 피벗(pivot) 이전 요소까지 순회한다. 2-1. 만약 right의 요소 값이 피벗(pivot)보다 작은 경우, left 값을 1 증가시키고 left 요소와 right 요소를 swap한다. 3. right의 순회가 종료되면 피벗(pivot)과 left 요소를 swap한다.
▶ 파티셔닝(Partitioning) 알고리즘에는 대표적으로 Hoare-Partition 알고리즘과 Lomuto-Partition 알고리즘이 있는데, Hoarse-Partition 알고리즘이 유리하다.
# 퀵 정렬(Quick-sort)
# 1-1. 분할 과정 (호어 분할, Hoare-Partition 알고리즘)
def partition_Hoare(arr, start, end):
pivot = start
left = start + 1
right = end
while left <= right:
# 피벗보다 큰 데이터를 찾을 때까지 반복함
while left <= end and arr[left] <= arr[pivot]:
left += 1
# 피벗보다 작은 데이터를 찾을 때까지 반복함
while right > start and arr[right] >= arr[pivot]:
right -= 1
# 엇갈렸다면 작은 데이터와 피벗을 교체함
if left > right:
arr[right], arr[pivot] = arr[pivot], arr[right]
# 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체함
else:
arr[left], arr[right] = arr[right], arr[left]
return right
# 1-2. 분할 과정 (로무토 분할, Lomuto Partition 알고리즘)
def partition_Lomuto(arr, start, end):
pivot = end
left = start - 1
for right in range(start, pivot):
if arr[right] <= arr[pivot]:
left += 1
arr[left], arr[right] = arr[right], arr[left]
arr[left + 1], arr[pivot] = arr[pivot], arr[left + 1]
return left + 1 # 최종적으로 pivot이 위치하는 인덱스를 반환함
# 2. 정렬 과정
def quick_sort(arr, start, end):
# 원소가 1개인 경우 종료
if start >= end:
return
# right = partition_Hoare(arr, start, end)
right = partition_Lomuto(arr, start, end)
quick_sort(arr, start, right - 1)
quick_sort(arr, right + 1, end)
arr = [3, 1, 4, 6, 9, 2, 8, 7, 5]
quick_sort(arr, 0, len(arr) - 1)
print(arr) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
