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