파티션함수에서 파라미터를 받을 때 3가지를 받는다. 리스트, start, end 로, 리스트는 파티션을 실행할 리스트고, start와 end는 파티션하려는 범위를 나타낸다.
처음엔 i와 b 포인터 모두 start인덱스에서 시작한다.
그리고 아직 아무 값도 판별하지 않았기 때문에 모든 값은 unknown 그룹에 존재한다.
[16(i, b), 11, 6, 13, 1, 4, 10, 7(pivot)]
이렇게 있을 때 첫 번째로 16을 판별하게 되면 pivot 인 7보다 크므로 big 그룹에 들어가야 한다.
그럼 i 포인터가 가리키는 인덱스만 1 증가하게 된다.
그럼 이렇게 된다.
[16(b), 11(i), 6, 13, 1, 4, 10, 7(pivot)]
b 전까지가 small 그룹,
b부터 i전까지가 big 그룹,
i부터 p전까지가 unknown 그룹,
p가 pivot그룹이라고 유추할 수 있겠다.
다음으로 11을 판별하게 되면 6은 pivot보다 작으므로 16과 6의 자리를 바꿔줘 6이 small그룹에 들어갈 수 있게 해준 뒤 i와 b의 인덱스를 모두 1씩 증가시켜 준다.
[6, 11(b), 16, 13(i), 1, 4, 10, 7(pivot)]
i의 인덱스가 pivot 까지 온 다음에는 b가 가리키는 값과 pivot을 바꿔준다. 그러면
[6, 1, 4, 7(b, p), 11, 16, 10, 13(i)]
이렇게 되고 첫 번째 pivot에 대한 파티션이 끝난다.
그럼 퀵 정렬은 어떻게 구현하면 될까?
파티션을 구현했으면 그 다음은 간단하다.
재귀적으로 구현하기만 하면 된다. 재귀적 구현의 두 가지 필수 요소인 1. base case와 2. recursive case 만 염두하면 된다.
내 코드:
# 두 요소의 위치를 바꿔주는 helper function
def swap_elements(my_list, index1, index2):
# 이전 과제에서 작성한 코드를 붙여 넣으세요!
temp = my_list[index1]
my_list[index1] = my_list[index2]
my_list[index2] = temp
# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
# 이전 과제에서 작성한 코드를 붙여 넣으세요!
pivot = my_list[end]
i, b = start, start
while i < end:
if my_list[i] >= pivot:
i += 1
else:
swap_elements(my_list, b, i)
i += 1
b += 1
swap_elements(my_list, b, end)
return b
# 퀵 정렬
def quicksort(my_list, start, end):
# 코드를 작성하세요.
if end - start < 1:
return
else:
pindex = partition(my_list, start, end)
quicksort(my_list, start, pindex - 1)
quicksort(my_list, pindex + 1, end)마지막 부분에 주목하면 재귀적으로 구현됐다는 것을 알 수 있다.
다이나믹 프로그래밍의 조건으로는 두 가지가 있다.
-
최적 부분 구조(Optimal Substructure)
-
중복되는 부분문제(Overlapping Subproblems)
최적 부분 구조가 있다는 건 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것
중복되는 부분 문제는 피보나치 수 구하기 같은 문제에서 쉽게 찾아 볼 수 있는데, 예를 들어 7번째 피보나치 수를 구하기 위해 3번째 피보나치 수를 10번 이상 계산해야 한다고 하면, 그것은 굉장히 비효율적인 일이 될 것이다. 이런 것을 중복되는 부분 문제라고 한다.
또 다이나믹 프로그래밍을 구현하는 방법은 두 가지가 있다.
-
Memoization : 중복되는 계산은 한 번만 계산 후 메모
-
Tabulation : bottom-up 으로 table을 채워나가기
내 코드:
def fib_memo(n, cache):
# 코드를 작성하세요.
if n in cache:
return cache[n]
elif n < 3:
cache[n] = 1
return cache[n]
else:
cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache)
return cache[n]
def fib(n):
# n번째 피보나치 수를 담는 사전
fib_cache = {}
return fib_memo(n, fib_cache)내 코드:
def fib_tab(n):
# 코드를 작성하세요.
l = []
l.append(1)
l.append(1)
i = 2
while n > len(l):
l.append(l[i-1] + l[i-2])
i += 1
return l[n-1]