[알고리즘] DP (Dynamic Programming, 동적 계획법)

➤ DP 알고리즘이란?

하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결하는 방식을 사용하여, 여러 번 반복되는 동일한 문제를 계산할 때의 비효율성을 방지하는 해결 방법이다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다.

위의 그림을 보면 같은 함수들이 여러번 호출되는 것을 볼 수 있다. 컴퓨터 상에서 연산을 할 때 같은 함수를 여러 번 호출하고 사용하다 보면 메모리 낭비가 되고, 연산 속도도 늘어나기 때문에 비효율적이다. 이러한 문제를 해결하기 위해서 사용하는 것이 동적 계획법이다. 

 

 

DP 알고리즘으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치 수열은 다음과 같은 형태로 이어진다.

위를 수식으로 표현하면, n 번째 피보나치 수 = (n - 1)번째 피보나치 수 + (n - 2)번째 피보나치 수

단,  1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1

 

프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 파이썬에서는 리스트 자료형을, C/C++와 자바에서는 배열을 이용하여 처리한다. (필자는 파이썬으로) 

---

구현 방법 - ① Top-Down (하향식, Memoization 방식)

dp = [0] * (n+1)

def fibo(n):
    if n == 1 or n == 2:
        return 1
        
    if dp[n] == 0:
        dp[n] = fibo(n - 1) + fibo(n - 2)
    return dp[n]
    
print(fibo(n))

✔ Memoization(메모이제이션)은 이전에 확인했던 문제를 메모하겠다는 뜻이다. 하향식은 하위 문제에 대한 정답을 계산했는지 확인해 가면서 풀어나간다.

구현 방법 - ②  Bottom-Up (상향식, Tabulation 방식)

dp = [0]*(n + 1)
dp[1] = 1

def fibo(n):
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
    
print(fibo(n))

✔ Tabulation(타뷸레이션)은 도표라는 뜻인데 도표식으로 저장하는 걸 말한다. 상향식은 더 작은 하위 문제부터 살핀 후 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나간다. 

 

➤ DP 사용 조건

• Overlapping Subproblems(겹치는 부분 문제)

   - 동일한 작은 문제들이 반복하여 나타나는 경우에 사용

• Optional Substructure(최적 부분 구조)

   - 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우에 사용

 

➤ DP 문제 풀어보기

2748번: 피보나치 수 2

 

풀이

https://dev-cloud.tistory.com/171

---

↓ DP에 대한 더 많은 설명 ↓

알고리즘 - Dynamic Programming(동적 계획법)