Ch8. 다이나믹 프로그래밍
중복되는 연산을 줄이자
최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다.
컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다.
그래서 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.
💡
다이나믹 프로그래밍 : 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
- 다이나믹 프로그래밍 사용 조건
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
- 피보나치 수열을 이러한 조건을 만족하는 대표 문제이다. 이 문제를 메모이제이션 기법을 사용해서 해결할 수 있다.
💡
메모이제이션(캐싱) : 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구현한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
- 탑 다운 방식(재귀함수 사용)에 국한되어 사용하는 표현
- 메모이제이션은 사전(dict) 자료형을 이용할 수도 있다.
- 수열처럼 연속적이지 않은 경우에 유용
- 일부의 작은 문제에 대한 해답만 필요한 경우에 유용
탑 다운 방식(재귀 함수)
💡
탑다운 방식(하향식) : 재귀 함수를 이용하여 다이나믹 프로그래밍 소스 코드를 작성하는 방법, 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
- 피보나치 수열 소스코드(재귀적)
# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수를 재귀함수로 구현(탑 다운 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건
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))
- 피보나치 수열의 시간 복잡도 : O(N)
- 다이나믹 프로그래밍과 메모이제이션은 별도의 개념
- 한 번 계산된 결과를 어딘가에 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.
보텀업 방식(반복문)
💡
보텀업 방식(상향식) : 반복문을 이용하여 소스코드를 작성하는 방법, 작은 문제부터 차근차근 답을 도출하는 방식
- 피보나치 수열 소스코드(반복적)
# 계산된 결과를 저장하기 위한 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])
- 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.
- DP 테이블 : 보텀업 방식에서 사용되는 결과 저장용 리스트
다이나믹 프로그래밍 문제 푸는 방법
- 주어진 문제가 다이나믹 프로그래밍 유형임 파악
- 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분들의 중복 여부 확인하기
- 단순 재귀함수로 비효율적인 프로그램을 작성한 뒤 작은 문제에서 구한 답이 큰 문제에서 그대로 사용된 수 있다면(메모제이션 사용이 가능하다면) 코드 개선하기
- 재귀 함수를 이용하기보다 반복문 사용(보텀업) 권장
- 재귀 함수 깊이 오류 관련 발생 가능 →
sys.setrecursionlimit()함수 호출하여 재귀 제한 완화 가능
- 재귀 함수 깊이 오류 관련 발생 가능 →
Uploaded by Notion2Tistory v1.1.0