동적 계획법(Dynamic Programming)

GilLog·2020년 10월 7일

DP 개념 알고리즘

알고리즘

목록 보기

1/8

💥❗ 주의사항 ❗💥

본 게시글의 최 우선 목적은 작성자 본인의 학습을 위함이라 부족한 점, 틀린 부분 등이 많습니다. 선생님들의 따뜻한 조언과 피드백 부탁드립니다! 감사합니다! 🙇‍♂️

1. 동적 계획법이란?

DP라고 불리는 동적 계획법은 코딩 테스트에 단골 문제 유형으로 나오고 있다.

코딩 테스트 문제를 풀다보면 아래와 같은 제한사항이 종종 나오곤 한다.

간혹 제한사항에 주어지는 숫자의 범위가 크고 경우의 수가 엄청난 값의 문제들이
대부분 DP를 이용해서 풀어야 하는 것이라고 알게 되었다.

그렇다면 동적 계획법은 무엇일까?

동적 계획법(dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
- wikipedia

2. 동적 계획법의 조건

동적 계획법을 적용하려면 위 정의에서 본 것 처럼 두 가지 속성을 만족 시켜야 하는데,

부분 반복 문제(Overlapping Subproblem)
최적 부분 구조(Optimal Substructure)

위 두 가지 속성을 만족 시켜야 한다.

그렇다면 이 두 가지 속성은 어떤 것 일까?

2.1 부분 반복 문제(Overlapping Subproblem)

동적 계획법의 등장은 피보나치 수열에서 시작되었다고 하는데,
피보나치 수열은 대표적인 재귀 함수로 아래와 같이 표현 할 수 있다.

fib(1) = 1; fib(2) = 1;
fib(n) = fib(n-1) + fib(n-2);

// 메소드로 표현한 피보나치 수열
int fib(int n)
  {
    if (n <= 2) 
      return 1;
    else
      return fib(n-1) + fib(n-2);
  }

만약 fibo(7)을 구하는 과정을 도식화 해보면 아래 이진 트리와 같은데

7번째 값을 구하기 위해 25번의 함수 호출이 진행된다.
이 과정에서 fib(5), fib(4), fib(3) 들이 이미 진행했던 연산임에도 재귀되며
반복적으로 연산 하는것을 볼 수 있다.

이러한 반복적인 연산을 부분 반복 문제(Overlapping Subproblem) 라 한다.
이는 어떤 문제가 여러개의 부분 문제(Subproblem)으로 쪼개질 수 있을때 사용하는 용어이다.

이때 부분 문제(Subproblem)란 항상 새로운 부분 문제를 생성해내기 보다는 계속해서 같은 부분 문제가 여러번 재사용되거나 재귀 알고리즘을 통해 해결되는 문제를 가리킨다.

예를 들어 설명 해보면 먼저 N 번째 피보나치 수 구하기 문제는 아래처럼 부분 문제로 쪼개질 수 있고,

문제 : N 번째 피보나치 수 구하기
부분 문제 : N-1 번째 피보나치 수 구하기, N-2 번째 피보나치 수 구하기

다시 또 N-1 번째 피보나치 수 구하기로 돌아가보면 아래처럼 부분 문제로 쪼개질 수 있다.

문제 : N-1 번째 피보나치 수 구하기
부분 문제 : N-2 번째 피보나치 수 구하기, N-3 번째 피보나치 수 구하기

이 부분 문제들은 기저 사례에 해당하는 1 번째, 2번째 피보나치 수를 구하는 문제를 제외하고

모든 문제를 부분 문제로 쪼갤 수 있고, 재귀 함수를 통해 해결 할 수 있다.

2.2 최적 부분 구조(Optimal Substructure)

최적 부분 구조란, 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다는 것이다.

아래 피보나치 수열의 식에서

fib(n) = fib(n-1) + fib(n-2);

큰 문제의 답인 fib(n)이 최적의 답이 되려면 작은 부분 문제인 fib(n-1)과 fib(n-2)이 최적의 답이어야 한다.
작은 부분 문제의 최적의 답으로 큰 문제의 최적의 답을 구할 수 있는 것이다.

fib(n-1)을 구하기 위해서 다시 fib(n-2) + fib(n-3)이 되고, 이 때 fib(n-2)가 중복이 된다.
그리고 최적 부분 구조를 만족한다면, 문제에 크기에 상관없이 어떤 한 문제의 답은 일정하다.

예를 들어 설명 해보면

fib(7)에서 구한 fib(4)
fib(6)에서 구한 fib(4)
fib(5)에서 구한 fib(4)
fib(4)에서 구한 fib(4)

이 fib(4)의 값들이 항상 같은 값인 것이다.

그렇다면 fib(4)를 반복해서 연산하는 것은 의미가 없다.

이 반복되는 연산 과정을 줄이기 위해서는 어떻게 해야 할까?

3. 메모이제이션(Memoization)

이를 해결하기 위해서 메모이제이션(Memoization) 이라는 동적 프로그래밍의 개념이 도입되게 되는데

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.
- wikipedia

다시 말해 메모리에 계산한 값을 저장해 나감으로써
다음 반복 수행때는 연산 없이 저장된 값을 불러와 주는 방법이다.

앞서 살펴본 피보나치 수열의 재귀 함수를 메모이제이션을 적용하면 아래와 같다.

// 최대 범위 N보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
int memo[101];

memo[1] = 1;
memo[2] = 1;

// 메소드로 표현한 피보나치 수열
int fib(int n)
  {
    if (memo[n] != 0) 
      return memo[n];
    
    memo[n] = fib(n-1) + fib(n-2);
    
    return memo[n];
  }

위 처럼 구하고자 하는 숫자의 크기 만큼 배열을 생성하고 계산한 값을 저장하고
저장된 값일 경우(초기값 0이 아닌 경우) 배열의 값을 리턴하는 방식으로 구현하면
중복되던 연산 과정을 줄일 수 있게 된다.

✋이때 저장해 두는 메모리(배열)을 캐시(Cache)라고 부른다.

4. 동적 계획법 접근 방법

동적 계획법으로 문제를 해결 할때는 크게 2가지 접근 방법을 들 수 있다.

Top-Down 방법과 Bottom-Up 방법이 있다.

4.1 Top-Down

Top-Down 방법은 말 그대로 위에서 아래로 접근하는 방법으로
큰 문제에서 부분 문제로 쪼개가며, 재귀 호출을 이용하여 푸는 방법이다.

아래 방식처럼 재귀 호출을 통해 피보나치 수 구하는 방식에 해당한다.

// 최대 범위 N보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
int memo[101];

memo[1] = 1;
memo[2] = 1;

// 메소드로 표현한 피보나치 수열
int fib(int n)
  {
    if (memo[n] != 0) 
      return memo[n];
    
    memo[n] = fib(n-1) + fib(n-2);
    
    return memo[n];
  }

4.2 Bottom-Up

Bottom-Up 방법은 말 그대로 아래에서 위로 접근하는 방법으로
부분 문제에서 부터 문제를 풀어가며 점차 큰 문제를 풀어가는 방법이다.
for문을 이용하여 푸는 방법에 해당한다.

// 최대 범위 N보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
int memo[101];

memo[1] = 1;
memo[2] = 1;

// 메소드로 표현한 피보나치 수열
int fib(int n)
  {
    
    for(int i = 3; i <=n; i++){
      memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[n];
  }