[Algorithms]Dynamic Programming

다이나믹 프로그래밍 공부

Photo by Michał Parzuchowski on Unsplash

퀵 정렬 vs 다이나믹 프로그래밍

• 퀵 정렬: 분할정복 알고리즘, 한 번 피벗이 자리를 잡게되면 그 기준 원소의 위치는 더 이상 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않음
• 다이나믹 프로그래밍: 한 번 해결했던 문제를 다시금 해결한다는 특징을 지님

다만! 아래의 조건들에서만 사용 가능함

1. 큰 문제를 작은 문제로 나눌 수 있다
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

피보나치로 차이점 알아보기

• 그냥 재귀사용시

def fibo(x):
	if x == 1 or x == 2:
		return 1
	return fibo(x - 1) + fibo(x - 2)
print(fibo(4))

• memoization(이전에 계산된 결과를 일시적으로 기록해 놓는 개념 /= dp) — top down

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100
#피보나치 함수를 재귀로 구현(탑 다운 다이나믹 프로그래밍)
def fibo(x):
	# 종료 조건(1 혹은 2일 때 1을 반환)
	if x == 1 or x == 2:
		return 1
	# 이미 계산한 적 있는 문제라면 그대로 반환
	if d[x] != 0:
		return d[x]
	
# 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
	d[x] = fibo(x - 1) + fibo(x - 2)
	return d[x]
print(fibo(99))

• bottom-up, dp 테이블(결과 저장용 리스트), 다이나믹 프로그래밍의 전형적 형태

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수 반복문으로 구현(보텀 업 다이나믹 프로그래밍)
for i in range(3, n - 1):
	d[i] = d[i - 1] + d[i - 2]
print(d[n])