[코딩테스트] 5. 다이나믹 프로그래밍(1) - 개념

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

- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

- 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운, 보텀업)

 

* 탑다운(하향식-위에서부터 아래려)

  보텀업(상향식-아래에서부터 위로)

 

* 자료구조에서 동적할당이란? 

    프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미한다.

 

2. 다이나믹 프로그래밍 사용 문제

1) 최적 부분 구조

- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결할 수 있다.

 

2) 중복되는 부분 문제

- 동일한 작은 문제를 반복적으로 해결해야 한다. 

 

3. 대표 예제

 

피보나치 수열

 

* 피보나치 함수 구현 

- 반복이 발생하여 비효율적

# 피보나치 함수를 재귀 함수로 구현
def fibo(x):
    # 종료 조건
    if x == 1 or x == 2:
        return 1
    # 점화식(재귀)
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

 

* 피보나치 수열의 시간 복잡도 분석

- 중복되는 부분이 발생하므로 비효율적

- 시간복잡도 O(2^n)

4. 다이나믹 프로그래밍 문제 풀이 - 탑답운(하향식) VS  보텀업(상향식)

 

- 탑다운(메모이제이션) 방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 한다.

- 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.

-> 결과 저장용 리스트는 DP 테이블이라고 부른다.

 

* 메모이제이션(Memoization)

- 다이나믹 프로그래밍을 구현하는 방법 중 하나

- 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.(이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념)

-> 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.

-> 값을 기록해 놓는다는 점에서 "캐싱" 이라고 한다.

- 한 번 계산된 결과를 담아놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.

 

* 피보나치 수열 코드(재귀적)

- 계산된 적 있는 부분(중복) 처리하기

# 피보나치 함수를 재귀함수로 구현(탑다운 방식 - 재귀)
def fibo2(x):
    # 종료 조건
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if dp[x] != 0:
        return dp[x]
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    dp[x] = fibo2(x-1) + fibo2(x-2)
    return dp[x]

print(fibo2(4))

 

* # 피보나치 함수를 재귀함수로 구현(보텀업 방식 - 반복문)

- 메모리제이션 기법을 이용하여 시간복잡도 O(N)

# Python

# 피보나치 함수를 재귀함수로 구현(보텀업 방식 - 반복문)
# 앞에서 계산된 결과를 저장하기 위한 DP 테이블 초기화
dp = [0] * 100

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

for i in range(3, n+1):
    dp[i] =  dp[i-1] + dp[i - 2]
    
print(dp[n])

# java

import java.util.*;

public class main{

    public static long[] dp = new long[100];

    public static void main(String[] args){
        // 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
        dp[1] = 1;
        dp[2] = 1;
        int n = 50; // 50번째 피보나치 수 계산

        // 피보나치 함수
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        System.out.println(dp[n]);
    }
}

결론) 다이나믹 프로그래밍을 이용하여 시간복잡도 O(2^n) 에서 O(n)으로 향상

 

5. 다이나믹 프로그래밍 VS 분할 정복

- 다이나믹 프로그래밍과 분할정복의 공통점?  "최적 부분 구조"를 가질 때 사용할 수 있다.

-> 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 상황

 

- 다이나믹 프로그래밍과 분할정복의 차이점?  "부분 문제의 중복"

-> 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다. 

     분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

6. 문제풀이 TIP

- 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하다.

    1) 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토한다.

    2) 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려한다.

    3) 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤(탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면,

        코드를 개선하는 방법을 사용할 수 있다.

 

*일반적인 코딩테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다.