[이것이 취업을 위한 코딩 테스트다 with 파이썬] 6. 다이나믹 프로그래밍

다이나믹 프로그래밍

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장 -> 다시 계산하지 않도록 함
• 다이나믹 프로그래밍의 구현 -> 2가지 방식(탑다운 / 보텀업)

조건

1. 최적 부분 구조(Optimal Substructure)
   • 큰 문제 -> 작은 문제 나눌 수 있음, 작은 문제의 답 모아 -> 큰 문제 해결할 수 있음
2. 중복되는 부분 문제(Overlapping Subproblem)
   • 동일한 작은 문제를 반복적으로 해결해야 함

---

피보나치(Fibonacci) 수열

• 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
• 다이나믹 프로그래밍으로 효과적으로 계산할 수 있음
• 피보나치 수열 -> 점화식으로 표현: $a_n = a_{n-1} + a_{n-2}, a_1 = 1, a_2 = 1$
  점화식: 인접한 항들 사이의 관계식
• 계산되는 과정 표현
  • 수열 -> 배열 or 리스트 이용해 표현
  • n번째 피보나치 수를 f(n), 4번째 피보나치 수 f(4) 구하는 과정

Python - 단순 재귀

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

print(fibo(4)) # 3

 

시간 복잡도

• 단순 재귀 함수로 피보나치 수열 해결 -> 지수 시간 복잡도
• f(2)가 여러 번 호출(중복되는 부분 문제)

• 세타 표기법: $\theta(1.618...^N)$
• 빅오 표기법: $O(2^N)$

-> 빅오 표기법 기준으로 f(30) 계산 -> 약 10억 가량의 연산 수행

해법: 다이나믹 프로그래밍

다이나믹 프로그래밍의 사용 조건을 만족하는지 확인

---

탑다운 vs 보텀업

• 탑다운(메모이제이션) 방식 = 하향식 / 보텀업 방식 = 상향식
• 다이나믹 프로그래밍의 전형적인 형태: 보텀업 방식
  • 결과 저장용 리스트: DP 테이블
• 메모이제이션: 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미
  • -> 다이나믹 프로그래밍에 국한된 개념 X
  • 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수 있음

메모이제이션(Memoization)

• 다이나믹 프로그래밍을 구현하는 방법 중 하나
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법
  • 같은 문제 다시 호출하면 메모했던 결과 그대로 가져옴
  • 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 함

Python - 탑다운 다이나믹 프로그래밍

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

# 피보나치 수열 -> 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
	# 종료 조건(1 or 2 -> 1)
    if x == 1 or x == 2:
    	return 1
    # 이미 계산한 적 있는 문제 -> 그대로 반환
    if d[x] != 0:
    	return d[x]
    # 아직 계산 X -> 점화식에 따라 피보나치 결과 반환
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

print(fibo(99)) # 21822995834555169026

보텀업 다이나믹 프로그래밍

# 앞서 계산된 결과 저장하기 위한 DP 테이블 초기화
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])

C++  - 보텀업 다이나믹  프로그래밍

#include <bits/stdc++.h>
using namespace std;

long long d[100];

int main(void) {
	d[1] = 1;
    d[2] = 1;
    int n = 50;
    
    for (int i = 3; i <= n; i++) {
    	d[i] = d[i - 1] + d[i - 2]
    }
    cout << d[n] << '\n';
    return 0;
}

Java

import java.util.*;

public class Main {
	public static long[] d = new long[100];
    public static void main(String[] args) {
    	d[1] = 1;
        d[2] = 1;
        int n = 50;
        
        for (int i = 3; i <= n; i++) {
        	d[i] = d[i - 1] + d[i - 2];
        }
        System.out.println(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) # f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

---

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

• 공통점: 최적 부분 구조를 가질 때 사용할 수 있음
  • 큰 문제 -> 작은 문제로 나눌 수 있음, 작은 문제 답 모아 -> 큰 문제 해결할 수 있는 상황
• 차이점: 부분 문제의 중복
  • 다이나믹 프로그래밍 문제: 각 부분 문제들이 서로 영향 미치며 부분 문제 중복됨
  • 분할 정복 문제: 동일한 부분 문제가 반복적으로 계산 X

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

---

다이나믹 프로그래밍 문제에 접근하는 방법

• 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요
• 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토
  • 다른 알고리즘 풀이 방법이 떠오르지 X -> 다이나믹 프로그래밍 고려
• 일단 재귀 함수로 비효율적인 완전 탐색 프로그램 작성(탑다운)
  -> (작은 문제에서 구한 답 -> 큰 문제에서 그대로 사용) => 코드 개선하는 방법
• 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제 출제되는 경우 ↑

---