[이것이코딩테스트다with파이썬] 다이나믹 프로그래밍

 

 

다이나믹 프로그래밍

 

큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

 

조건)

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

 

메모이제이션 기법 (캐싱)

 

다이나믹 프로그래밍을 구현하는 방법 중 한 종류

한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

 

 

# 피보나치 수열 소스코드 - 메모이제이션의 예 [탑다운]

 

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

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

 

 

 

퀵 정ㅇ렬은 정렬을 수행할 때 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다.

이는 분할 정복 알고리즘으로 분류된다.

다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.

 

퀵 정렬은 한 번 기준 원소가 자리를 변경해서 자리를 잡게 되면 그 기준 원소의 위치는 더 이상 바뀌지 않고

그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다.

반면, 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결한다는 점이 특징이다.

그렇기 때문에, 이미 해결된 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결이 됐던 것이니까

다시 해결할 필요가 없다고 반환하는 것이다.

 

 

재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을 "탑다운 방식"이라고 한다.

반면, 단순히 반복문을 이용하여 소스코드를 작성하는 방법을 "보텀업 방식"이라고 한다.

 

 

# 피보나치 수열 소스코드 [보텀업]

 

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
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])

 

 

 

* 메모이제이션은 때에 따라서 다른 자료형, 예를 들어 사전(dict) 자료형을 이용할 수도 있다.

사전 자료형은 수열처럼 연속적이지 않은 경우에 유용하다.

 

* 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있으므로

재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식을 사용하는 것이 권장된다.

(sys 라이브러리에 포함된 setrecursionlimit() 함수를 호출하여 재귀 제한을 완화시킬 수 있다.)