Python x 알고리즘 : 다이나믹 프로그래밍(동적 계획법)

🍃 다이나믹 프로그래밍(동적 계획법)

• DP는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘이다.
• DP는 메모리 공간을 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있는 방법이다.
• DP는 2가지 방식(탑다운, 보텀업)으로 구성된다.
  • 탑다운 : 재귀함수를 이용해 큰 문제를 해결하기 위해 작은 문제 호출
  • 보텀업 : 반복문을 이용해 작은 문제를 먼저 해결하고 해결된 작은 문제를 모아 큰 문제 해결

다이나믹 프로그래밍 vs 동적 할당의 다이나믹

프로그래밍에서 다이나믹은 "프로그램이 실행되는 도중"에 라는 의미, 즉 자료구조에서 동적 할당은 프로그램 실행 중 메모리를 할당하는 기법이다. 반면 DP에서 다이나믹은 다른 의미이다.

 

 

DP가 적용되기 위해서는 2가지 조건을 만족해야 한다.

 

1) Overlapping Subproblems(중복되는 부분 문제)

• DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다.
• 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
• 즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다

 

2) Optimal Substructure(최적 부분 구조)

• 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다.( 큰 문제를 작은 문제로 나눌 수 있다.)
• 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다
• 만약, A - B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B가 정답이 된다.

---

 

🍃 다이나믹 프로그래밍 : 피보나치 수열을 효율적으로 해결하기 위한 방법

• 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시이다.
• 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다.

• 점화식이란 인접한 항들 사이의 관계식을 의미한다.
• 피보나치 수열은 아래와 같이 정리할 수 있다
  • a(n) = a(n-1) + a(n-2), a(1) = 1, a(2) = 1
  • n번째 피보나치 수 = (n-1)번째 피보나치수 + (n-2)번째 피보나치수, 1번째 피보나치수 = 1, 2번째 피보나치수 = 1
• 프로그래밍에서는 이러한 수열을 배열이나 리스트를 이용해 표현
• n번째 피보나치 수를 f(n)라고 할 때 4번째 피보나치 수 f(4)를 구하는 과정은 다음과 같다.

# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(4))

 

🍃피보나치 수열의 시간 복잡도

 

• f(n) 함수에서 n이 커지면 수행 시간이 기하급수적으로 늘어난다.
• 세타 표기법: 𝜃(1.618⋯ᴺ)
• 빅오 표기법: O(2ᴺ)
• 빅오 표기법을 기준으로 f(30)을 계산하기 위해 약 10억가량의 연산을 수행해야 한다.

---

🍃 탑다운 vs 보텀업

• 탑다운(메모이제이션) 방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 한다.
• 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식
  • 결과 저장용 리스트는 DP 테이블이라고 부른다
• 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미한다.
  • 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아니다
  • 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.

🍃 탑다운 : 메모이제이션 (Memoization)

• 메모이제이션은 DP를 구현하는 방법 중 한 종류이다.
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법
  • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
  • 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.

 

피보나치 수열 : 탑다운 다이나믹

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

# 피보나치 함수(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(99))

 

피보나치 수열 : 보텀업 다이나믹

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

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

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

print(d[n])

 

 

피보나치 수열: 메모이제이션 동작 분석

• 이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리할 것을 기대할 수 있다.

• 실제로 호출되는 함수에 대해서만 확인해보면 다음과 같이 방문한다.

메모제이션을 이용하는 경우 시간 복잡도는 O(N)이 된다.

d = [0] * 100

def fibo(x):
    print('f(' + str(x) + ')', end=' ')
    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]

fibo(6)

 

피보나치 연습 문제

https://www.acmicpc.net/problem/24416

24416번: 알고리즘 수업 - 피보나치 수 1

---

🍃 다이나믹 프로그래밍 vs 분할 정복

• 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용 가능하다.
  • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
• 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복
  • 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
  • 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

• 분할 정복의 대표적인 예시로 퀵 정렬이 있다.
  • 한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않는다.
  • 분할 이후에 해당 피벗을 다시 처리하는 부분 문제는 호출하지 않는다.