[Algorithm] 동적 계획법 (Dynamic Programming, DP)

🦄 동적 계획법 (Dynamic Programming, DP)

동적 계획법은 복잡한 문제를 간단한 여러 개의 하위 문제(sub-problem)으로 나누어 푸는 방법이다.

 

같은 하위 문제를 가지고 있는 경우 이 결과값을 저장하여 한 번씩만 계산하도록 하며

이러한 기법을 memoization이라고 한다. 

 

📌 문제를 풀 때 점화식과 함수 호출 과정을 생각해보면서 dp 테이블을 채워나가면 된다. 

 

📌 또한 가능하면 재귀 함수를 이용하는 탑 다운 방식보다는 보텀업 방식으로 구현하는 것을 권장한다.

시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다. 

 

- dp 테이블 : 다이나믹 프로그래밍에서 사용되는 결과 저장용 배열/리스트

     → 한 번 구한 결과는 계속해서 배열/리스트에 저장하고 그것을 이용하여 그 다음 값을 구해나간다. 

 

🦄 Top-Down

재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제들을 호출한다. 

 

피보나치 수 구하기 (Top-Down)

dp = [0] * 100

def fibo(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    if dp[x] != 0:
        return dp[x]
    dp[x] = fibo(x - 1) + fibo(x - 2)
    return dp[x]

print(fibo(99))

 

🦄 Bottom-Up

반복문을 이용하여 작은 문제부터 차근차근 답을 도출한다. 

 

피보나치 수 구하기 (Bottom-Up)

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

# 첫번째 피보나치 수와 두번째 피보나치 수는 1
dp[0] = 0
dp[1] = 1
n = 99

# 피보나치 함수 구현
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2] # 피보나치 함수의 점화식

print(dp[n])

 

🦄 796,796으로 나눈 나머지를 출력하라.

다이나믹 프로그래밍 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라는 내용이 들어가 있는 경우가 많다. 

이는 단지 결괏값이 굉장히 커질 수 있기 때문에 그런 것으로, 값을 계산할 때마다 특정한 수로 나눈 나머지만 취하도록 하면 된다. 

for i in range(3, n + 1):
	d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796

📌 마지막에 최종 계산된 결과에서 나누는 것이 아니라 값을 계산할 때마다 나눈다는 점을 주의하자!!

 

---

Ref.

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24