Computer Science/Algorithm
[파이썬으로 배우는 알고리즘 기초] 2. 분할 정복법 (1)
조코링
2022. 6. 1. 23:26
2-0. 분할 정복
- 분할-정복 두 단계로 문제를 해결하는 알고리즘 설계 기법
- 분할(Divide): 문제의 입력사례를 둘 이상의 작은 입력사례로 분할
- 정복(Conquer): 작은 입력사례들을 각각 정복, 충분히 작지 않을 경우 재귀 호출
- 통합: 필요할 경우, 작은 입력사례의 해답을 통합하여 원래 입력사례의 해답을 도출 - 하향식(Top-Down) 방식
2-1. 이분 검색(Binary Search)
- 순차 탐색: 정렬되지 않은 리스트에서 주어진 키가 존재하는가?
- 이분 검색: 정렬된 리스트에서 주어진 키가 존재하는가?
- 분할: 정가운데 원소를 기준으로 리스트를 두 개로 분할
정복: 키 값이 정가운데 원소보다 크면 오른쪽, 작으면 왼쪽을 재귀 호출
획득: 선택한 리스트에서 얻은 답을 리턴 - 재귀 함수로 구현
lst = [1, 2, 5, 8, 13]
target = 13
def bs(start, end):
if start > end:
return -1
else:
mid = (start + end) // 2
if lst[mid] == target:
return mid
elif lst[mid] > target:
return bs(start, mid - 1)
else:
return bs(mid + 1, end)
result = bs(0, len(lst) - 1)
print(result)
- 반복문으로 구현
lst = [1, 2, 5, 8, 13]
target = 13
start = 0
end = len(lst) - 1
result = -1
while start <= end:
mid = (start + end) // 2
if lst[mid] == target:
result = mid
break
elif lst[mid] > target:
end = mid - 1
else:
start = mid + 1
print(result)
2-2. 합병 정렬(Merge Sort)
- 분할: 원소 n개인 리스트를 n/2개의 원소를 가진 두 개의 리스트로 분할
정복: 왼쪽 리스트와 오른쪽 리스트를 각각 재귀적으로 합병 정렬
통합: 각각 정렬된 두 개의 리스트를 정렬된 하나의 리스트로 합병하여 리턴 - 재귀 함수로 구현 --- 리스트 left, right를 추가로 사용하여 메모리 낭비
lst = [98, 11, 65, 3, 24, 7]
def merge(left, right):
temp = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
temp.append(left[i])
i += 1
else:
temp.append(right[j])
j += 1
if i < len(left):
temp += left[i:]
else:
temp += right[j:]
return temp
def mergesort(arr):
n = len(arr)
if n <= 1:
return arr
else:
mid = n // 2
left = mergesort(arr[0:mid])
right = mergesort(arr[mid:])
return merge(left, right)
result = mergesort(lst)
print(result)
- 리스트를 추가적으로 사용하지 않고 구현
lst = [98, 11, 65, 3, 24, 7]
def merge(start, mid, end):
temp = []
i = start
j = mid + 1
while i <= mid and j <= end:
if lst[i] < lst[j]:
temp.append(lst[i])
i += 1
else:
temp.append(lst[j])
j += 1
if i <= mid:
temp += lst[i:mid+1]
else:
temp += lst[j:end+1]
for k in range(start, end + 1):
lst[k] = temp[k - start]
def mergesort(start, end):
if start < end:
mid = (start + end) // 2
mergesort(start, mid)
mergesort(mid + 1, end)
merge(start, mid, end)
mergesort(0, len(lst) - 1)
print(lst)
2-3. 퀵 정렬(Quick Sort)
- 추가적인 리스트를 사용하지 않는 내부 정렬
- 분할: 기준 원소(pivot)를 정해서 이를 기준으로 좌우로 분할
정복: 왼쪽 리스트와 오른쪽 리스트를 각각 재귀적으로 퀵 정렬
통합: 정렬된 리스트를 리턴 - 재귀 함수로 구현 1
lst = [98, 11, 65, 3, 24, 7]
def partition(start, end):
pivot = lst[start]
j = start
for i in range(start + 1, end + 1):
if lst[i] < pivot:
j += 1
lst[i], lst[j] = lst[j], lst[i]
pivot = j
lst[start], lst[j] = lst[j], lst[start]
return pivot
def quicksort(start, end):
if start < end:
pivot = partition(start, end)
quicksort(start, pivot - 1)
quicksort(pivot + 1, end)
quicksort(0, len(lst) - 1)
print(lst)
- 재귀 함수로 구현 2 --- 널리 사용하는 방법
lst = [98, 11, 65, 3, 24, 7]
def partition(start, end):
pivot = lst[start]
i = start + 1
j = end
while i <= j:
while i <= j and lst[i] < pivot:
i += 1
while lst[j] > pivot:
j -= 1
if i < j:
lst[i], lst[j] = lst[j], lst[i]
pivot = j
lst[start], lst[pivot] = lst[pivot], lst[start]
return pivot
def quicksort(start, end):
if start < end:
pivot = partition(start, end)
quicksort(start, pivot - 1)
quicksort(pivot + 1, end)
quicksort(0, len(lst) - 1)
print(lst)
※ 강의 링크: https://inf.run/v8Rn