다이나믹 프로그래밍이란

개요

• 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함
• 완전탐색과 같이 비효율적인 시간복잡도를 가지는 문제라고 하더라도 다이나믹 프로그래밍으로 시간복잡도를 획기적으로 줄일 수 있다.
• 다이나믹 프로그래밍의 구현은 일반적으로 두가지 방식(탑다운, 보텀업)으로 구성됨
• 동적 계획법이라고도 부른다.

  ✅참고 : 일반적인 프로그래밍 분야에서의 동적(Dynamic)의 의미
  - 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미
  - 반면 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어이다.

사용 조건

1. 최적 부분 구조
큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결 할 수 있다.

2. 중복되는 부분 문제
동일한 작은 문제를 반복적으로 해결해야 한다.

예제 : 피보나치 수열

피보나치 수열은 다음과 같다.
1 1 2 3 5 8 13 21 34 55 89 ...

✅ 점화식
인접한 항들 사이의 관계식을 의미

✅ 피보나치 수열의 점화식 표현
재귀함수를 이용해 점화식 형태 그대로 구현 가능

비효율적으로 구현

public class Main {

    // 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
    public static int fibo(int x) {
        if (x == 1 || x == 2) {
            return 1;
        }
        return fibo(x - 1) + fibo(x - 2);
    }

    public static void main(String[] args) {
        System.out.println(fibo(4));
    }

}

문제점

• 단순 재귀함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 된다. (비효율적)

  ✅ 참고 : 피보나치 재귀함수의 지수 시간 복잡도
  O(2^트리높이N)

• 다음과 같이 f(2)가 여러번 호출된다. (중복되는 부분 문제)

다이나믹 프로그래밍으로 구현

피보나치 수열은 다이나믹 프로그래밍의 사용 조건을 만족하므로 다이나믹 프로그래밍으로 효과적으로 계산할 수 있다.

✅ 피보나치 수열의 다이나믹 프로그래밍 사용 조건 충족
1. 최적 부분 구조
큰 문제(ex. f(4))를 작은문제(ex. f(3)+f(2))로 나눌 수 있다.

2. 중복되는 부분문제
동일한 작은 문제를 반복적으로 해결 (ex. f(2)의 중복)

탑다운

• 구현 과정에서 재귀함수 사용
  큰 문제를 해결하기 위해 작은 문제들을 재귀적으로 호출
  (작은 문제가 모두 해결 되었을 때 큰 문제에 대한 답을 얻을 수 있다)
• 재귀호출 과정에서 메모이제이션(DP) 이용하여 중복되는 부분 문제 해결

  ✅ 메모이제이션
  - 한번 계산한 (작은문제에 대한) 결과를 메모리 공간에 메모하는 기법
  - 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
  - 엄밀히 말하면 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념이므로 다이나믹 프로그래밍에 국한된 개념은 아니다.
  - 동작분석
  a.단순 재귀함수와 비교b. 실제 호출
  - 파란색 : 호출 + 연산 및 값 저장
  - 실선 : 호출 + 바로 return
  => 파란f(3)에서 앞서 값 저장되었기 때문에 실선f(3)은 호출되었지만 바로 return되고 따라서 더 깊게 들어가지 않는다.
  => 상수시간(return)을 무시하여 O(N)

import java.util.*;

public class Main {

    // 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열 초기화
    public static long[] d = new long[100];

    // 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
    public static long fibo(int x) {
        // 종료 조건(1 혹은 2일 때 1을 반환)
        if (x == 1 || x == 2) {
        	// 상수시간 소요
            return 1;
        }
        // 이미 계산한 적 있는 문제라면 그대로 반환
        if (d[x] != 0) {
            // 상수시간 소요
            return d[x];
        }
        // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
        d[x] = fibo(x - 1) + fibo(x - 2);
        return d[x];
    }

    public static void main(String[] args) {
        System.out.println(fibo(50));
    }
}

보텀업

다이나믹 프로그래밍의 전형적 형태이다.

• 구현 과정에서 반복문 사용
  아래쪽에서부터 작은 문제를 하나씩 해결해 나가면서 먼저 계산한 문제들의 값을 활용해서 그 다음 문제까지 차례로 해결

  ✅ 재귀함수를 사용하지 않으므로 중복되는 부분문제가 발생하지는 않음 Bottom - Up은 아래에서 위로 올라가면서, 이미 그 자체만으로도 반복되는 부분문제들에 대한 메모이제이션을 진행하며 풀어나가게 된다.(참고)

• 반복문 과정에서 결과 저장용 리스트(DP) 이용

public class Main {

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

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

        // 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
        for (int i = 3; i <= n; i++) {
            d[i] = d[i - 1] + d[i - 2];
        }
        System.out.println(d[n]);
    }
}

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

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

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

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