🤢DP (Dynamic Programming)

---

여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

→ 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘

• DP란 '동적 계획법'이라고도 불리는 알고리즘
• 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말 / 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
• DP는 다음의 조건을 만족할 때 사용할 수 있음
  1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우를 의미
  2. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 하는 경우

피보나치 수열

---

피보나치 수열은 DP로 해결할 수 있는 문제들 중 하나이다.

• 피보나치 수열이란 이전 두 항의 합을 현재의 항으로 설정하는 특징을 가진 수열이다.

  (Ex) 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

피보나치 수열을 점화식으로 표현해보자.

수학적 점화식을 프로그래밍으로 표현하려면 단순 재귀함수를 사용하면 간단하다. Python 코드로 작성해보자.

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(4))
>> 3

재귀함수의 호출을 그림으로 표현하면 아래와 같다.

피보나치 수열을 단순 재귀함수로 구현했을 때의 문제점

위와 같이 코드를 작성하게 되면 심각한 문제가 생길 수 있다. f(n)함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 아래 그림을 보자.

f(6)을 계산할 때에 그림과 같이 f(2)가 여러 번 호출되는 것을 확인할 수 있다. (중복되는 부분 문제) 
즉, 같은 연산을 여러 번 수행하므로 시간 복잡도가 엄청 커지게 된다.

피보나치 수열의 시간 복잡도는 O(2 ** N)이다.
예를 들어 f(30)을 계산하기 위해 약 10억번의 연산을 수행해야 한다.

우리는 DP를 사용하면 이러한 문제를 효율적으로 해결할 수 있다.

DP로 피보나치 수열 계산하기

DP는 항상 사용할 수 없기 때문에 DP의 사용 조건을 만족하는지 확인해보자.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 위 2가지 조건을 만족하므로 DP를 사용할 수 있다!
이 문제를 메모이제이션 (Memoization) 기법을 사용해서 해결해보자.

※ 메모이제이션 (Memoization) 이란?

• DP를 구현하는 방법 중 한 종류이다.
• 한 번 구한 결과를 메모리 공간에 메모해두고 --> 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법이다. (값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.)

# 메모이제이션하기 위한 리스트 초기화
memoization = [0] * 100

# 피보나치 함수를 재귀함수로 구현 (Top-down DP)
def fibo(x):
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있으면 그대로 반환
    if memoization[x] != 0:
        return memoization[x]
    # 계산한 적 없으면 점화식에 따라 피보나치 결과 반환
    memoization[x] = fibo(x - 1) + fibo(x - 2)
    return memoization[x]

print(fibo(6))

메모이제이션을 사용하여 f(6)을 구하는 과정은 아래의 그림과 같다.

메모이제이션을 사용하게 되면 그림의 색칠된 노드만 방문하게 된다.

실제 코드에서 호출되는 함수만 보게되면 아래의 그림과 같이 방문한다.

f(6) -> f(5) -> f(4) -> f(3) -> f(2) -> f(1) -> f(2) -> f(3) -> f(4)

DP를 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 O(N)이다.
왜냐하면 f(1)을 구한 다음 그 값이 f(2)를 구하는 데 사용되고, 
f(2)의 값이 f(3)을 푸는 데 사용되는 방식으로 이어지기 때문이다.
또한, 메모이제이션 때문에 한 번 구한 결과는 다시 구해지지 않는다.

TIP

---

• 주어진 문제가 DP 유형인지 파악하는 것이 중요

  • 먼저 그리디, 시뮬레이션, 완전탐색 등의 알고리즘으로 문제를 풀 수 있는지 검토한 후 풀 수 없다고 생각이 들면 DP를 사용해보자!

• 수열은 배열이나 리스트로 표현할 수 있다고 했는데, 메모이제이션은 때에 따라서 다른 자료형, 예를 들어 딕셔너리 자료형을 이용할 수도 있다. --> 사전 자료형은 수열처럼 연속적이지 않을 때 유용하다.

• DP를 사용할 때, 일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (Top-Down) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 방법이다.

  • 위의 피보나치 수열의 예제 코드처럼 재귀 함수를 작성한 뒤에 나중에 메모이제이션 기법을 적용해 소스코드를 수정하는 것도 좋다!!