[TAVE/이코테] ch08 다이나믹 프로그래밍 | 개념 정리

참고자료: 이것이 코딩테스트다

중복되는 연산을 줄이자

📌동적 계획법이라고도 하며 메모리 공간을 약간 더 사용해 연산 속도를 비약적으로 증가시키는 방법이다.

👉🏻다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 파이썬에서 이러한 수열을 배열이나 리스트로 표현할 수 있다.

피보나치 수열

📌피보나치 수열: 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열

👉🏻점화식: \( a_{n+2} = f(a_{n+1}, a_n) = a_{n+1}, a_n )\

• n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
• 단, 첫번째와 두번째 피보나치 수 = 1

👉🏻위의 점화식을 프로그래밍을 표현하려면 재귀 함수를 사용하면 간단하다. 

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

print(fibo(4))

👉🏻피보나치 함수 소스코드이다. 이 함수코드의 문제점은 n이 커질수록 수행 시간이 기하급수적으로 늘어난다.

👉🏻동일한 함수가 반복적으로 호출되는 것을 알 수 있다. f(3)만 해도 총 3번 호출되었다. 호출할 때마다 계산하므로 시간복잡도가 올라간다. 때문에 이를 효율적으로 해결하기 위해 다이나믹 프로그래밍을 사용해야 한다.

👉🏻다이나믹 프로그래밍을 사용할 수 있는 조건은 다음과 같다.

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

👉🏻다이나믹 프로그래밍 소스코드를 작성하는 방법은 2가지가 있다.

• 탑다운 방식: 큰 문제를 해결하기 위해 작은 문제를 호출, 재귀 함수를 이용
• 보텀업 방식: 작은 문제부터 차근차근 답을 도출, 단순히반복문 이용

 

1️⃣재귀 함수 사용

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

#피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
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(99))

👉🏻메모이제이션 기법으로 작성된 코드이다. 한 번 구한 정보를 리스트 d에 저장했다.

👉🏻해당 코드를 보면 알겠지만 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

📌메모이제이션: 다이나믹 프로그래밍 구현 방법 중 하나로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. 메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.

👉🏻따라서 메모이제이션 기법을 활용하면 위 그림처럼 색칠된 노드만 방문하게 된다. 호출하더라도 계산된 노드를 가져오거나 1을 반환하기 때문이다.

👉🏻다이나믹 프로그래밍으로 피보나치 수열을 풀면 시간 복잡도는 O(N)이다. 

 

2️⃣반복문 사용

d = [0] * 100

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

#피보나치 함수 반복문으로 구현(보텀업)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

👉🏻반복문(보텀업 방식)을 사용하면 오버헤드를 줄일 수 있다. 이 때 시간 복잡도는 O(N)이다.

👉🏻보텀업 방식에서 사용되는 결과 저장용 리스트를 DP 테이블이라고 부른다.