[Algorithm 개념] Dynamic Programming

DP(동적계획법)란?

- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법.

- 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

- 일반적으로, 구현 방식은 탑다운(Top-down)과 보텀업(Bottom-up) 방식으로 구성된다.

1. DP 를 사용할 수 있는 조건

e.g. 피보나치 수열 : 수열을 배열이나 리스트를 이용해 표현함.

1) 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 

2) 중복되는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 함.

 

2. DP 종류

1) 탑다운 방식 : 메모이제이션 (Memoization)

메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 탑다운 방식입니다. 한번 계산한 결과를 메모리 공간에 메모하는 기법. 

• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옵니다.
• 값을 기록해 놓는 다는 점에서 캐싱이라고도 함. 

2) 보텁업 방식 

DP의 전형적인 형태는 보텁업 방식. 결과 저장용 리스트는 DP 테이블이라고 부름. 

3. DP 예시 : 피보나치 수열

# 한번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
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)

 

4. 다이나믹 프로그래밍 문제에 접근하는 방법

1). 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요. 가장 먼저 그리디, 구현, 완전 탐색등의 아이디어로 문제를 해결할 수 있는지 검토. 없으면, dp 고려.

2). 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에, 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선하는 방법을 사용할 수 있다. 

 

5. 개미 전사 문제 풀이

N = int(input())
arr = list(map(int, input().split()))

d = [0] * 100 #dp table

# ai = i번째 식량 창고까지의 최적의 해
# ki = i번째 식량 창고에 있는 식량의 양
# ai = max(ai-1, ai-2+ki) #i-3은 i-1의 해에서 이미 고려가 됬기 때문에 필요없음.

d[0] = arr[0] #첫번째
d[1] = max(arr[0], arr[1]) # 두번째 
for i in range(2, N):
    d[i] = max(d[i-1], d[i-2]+arr[i])
    
print(d[n-1])

 

6. 백준 1463 : 1로 만들기 

n = int(input())
d = [0] * (n + 1)## d에 계산된 값을 저장. n + 1이라고 한 이유는, 1번째 수는 사실 d[1]이 아니고 d[2]이기 때문

for i in range(2, n + 1):
    # 현재의 수에서 1을 뺄 경우
    d[i] = d[i - 1] + 1
    # 현재의 수에서 5로 나눠지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)
    # 현재의 수에서 3로 나눠지는 경우    
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1) 
    # 현재의 수에서 2로 나눠지는 경우    
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
print(d[n])