알고리즘 - 다이나믹 프로그래밍

mauz·2022년 3월 3일

TIL

TIL - Today I Learned

목록 보기

4/10

다이나믹 프로그래밍 문제들을 풀고있지만 계속해서 어려움을 느끼고있기에 다시한번 개념을 정리하려 한다.

Dynamic programming

직번역 하면 "동적 계획법" 그런데 dynamic이 붙은 특별한 이유는 없다고한다.
그러니 뜻보단 풀이 방법이 중요한 것 같다.

다이나믹 프로그래밍은 다음의 조건을 만족할 때 사용할 수 있다고 한다.

최적 부분 구조 (Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
중복되는 부분 문제 (Overlapping Subproblem)
동일한 작은 문제를 반복적으로 해결해야 한다.

피보나치 수열

대표적인 예시로 피보나치 수열을 살펴보면

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

수열의 각 항은 아래와 같은 규칙으로 만들어 진다고 볼 수 있다.

1+1 = 2 , 1+2 = 3 , 2+3 = 5 , 3+5 = 8, ...

수열은 1, 1로 시작하며
구하고자 하는 항은 이전 이전항과 이전항의 합으로 만들어지는 것이 반복된다.

따라서 다음과 같은 관계식이 성립한다.

이를 통해 피보나치 수열의 n번째 항의 값을 알아낼 수 있다.

코드로 한번 구현해보자.

#단순재귀 코드
n = int(input())

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

fibo()는 재귀함수이다. 함수내에서 자기 자신을 호출한다.

가령 피보나치 수열의 4번째항을 알고싶어서 n에 4를 입력하면

fibo()는 4를 전달받아 함수를 실행한다.
1 또는 2가 아니니 넘어간다.
fibo(3) + fibo(2)을 반환해준다고 한다. 여기서 fibo함수가 호출되었으니 새로운 fibo함수 두개가 실행된다.
새로운 fibo()는 3을 전달받아 함수를 실행한다.
4-1. 1 또는 2가 아니니 넘어간다.
4-2. fibo(2) + fibo(1)을 반환해준다고 한다 새로운 fibo함수 두개가 실행된다.
4-2-1. fibo()는 2를 전달받아 함수를 실행한다.
4-2-2. 1 또는 2를 전달받았으니 1을 반환한다.
4-3-1. fibo()는 1을 전달받아 함수를 실행한다.
4-3-1. 1또는 2를 전달받았으니 1을 반환한다. 이제 4-2로 올라가서 연산한다.
새로운 fibo()는 2를 전달받아 함수를 실행한다.
5-1. 1 또는 2가 맞으니 1을 반환한다. 다시 3으로 되돌아가 연산한다.

적다가 보니 이상해 졌는데.. 재귀함수는 정해진 조건까지 자기 자신을 호출하면서 마치 액자식 구성처럼 점점 속으로 들어간다. 마지막 재귀함수가 종료되면 하나씩 빠져나오면서 필요했던 값들을 돌려준다.

Dynamic programming 에서 단순 재귀함수 사용의 단점은
모든 경우의 수를 연산한다는 것이다. 위 과정에서도 fibo(2)의 값을 알고있는데 또 연산을 했다.
n의 값이 늘어날수록 지수함수적으로 연산갯수가 늘어나 O(2^n)의 시간 복잡도를 가지게 된다.

DP에서 연산을 줄이려면 어떻게 해야할까?

메모이제이션 (Memoization)

한번 계산했던 결과를 메모리 공간에 메모하는 기법이다.

이전에 재귀함수 코드에 메모이제이션 기법을 적용하면

n = int(input())

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * n+1

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건(1 혹은 2일 때 1을 반환)
    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(n))

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

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

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])