[알고리즘] 동적 프로그래밍(Dynamic Programming) 알고리즘

 

 

동적 프로그래밍(Dynamic Programming)알고리즘이란?

---

동적 프로그래밍이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.  기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.

 

DP를 사용하는 이유

---

DP는 일반적인 재귀 방식과 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작운 문제들이 여러번 반복 되어 비효율적인 계산이 될 수 있다는 것이다.

 

또한 분할정복과 비슷하다고도 생각할 수 있는데 이는 작은 문제가 중복이 일어나는지 안일어나는지 차이점이 있다. 분할정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법이지만 동적프로그래밍은 작은 부분문제들이 반복되는것을 이용해 풀어나간다.

 

DP의 사용 조건

---

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

1. Overlapping Subproblems(부분 반복 문제)
2. Optimal Substructure(최적 부분 구조)

- Overlapping Subproblems(부분 반복 문제)

DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.

 

예를 들어 피보나치 수열이 있다.

위 그림을 보면 fibo(5), fibo(4)등등 이미 진행했던 연산임에도 불구하고 재귀되며 반복적으로 연산하는 것을 볼 수 있다.

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

- Optimal Substructure(최적 부분 구조)

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

그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다. 

fibo(n) = fibo(n-1) * fibo(n-2)

위의 피보나치 수열의 식을 보면 큰 문제의 답인 fibo(n)이 최적의 답이 되려면, 작은 부분의 문제인 fibo(n-1), fibo(n-2)이 최적의 답이어야만 한다.  여기서 fibo(n-1)을 구하기 위해서는 다시 fibo(n-2) + fibo(n-3)이 되고, fibo(n-2)가 중복되게 된다. 그리고 최적 부분 구조를 만족한다면 문제의 크기에 상관없이 fibo(n-1)은 언제나 일정한 값을 가진다.

Memoization(메모이제이션)

---

위의 피보나치수열을 계산하면서 알 수 있듯이 중복되는 연산과정이 많다. 이러한 중복되는 연산과정을 해결하기 위해서는 Memoization(메모이제이션)이라는 동적프로그래밍의 개념이 도입되게 된다.

 

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

즉, 메모리에 계산한 값을 저장해 나감으로써 수행될 대 연산 없이 저장한 값을 사용한다는 것이다.

 

동적프로그래밍의 2가지 접근 방법

---

• Bottom - Up
• Top - Down

- Bottom - Up 

말그대로, 아래에서 위로 접근하는 방법으로 문제를 해결하여 점차 큰 문제를 풀어나가는 방식이다. 메모를 위해서 dp라는 배열을 만들었고 이것이 1차원이라 가정했을 때, dp[0]가 기저 상태이고 dp[n]을 목표 상태라고 하자. Bottom-up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.

 

- Top-Down

말그대로, 위에서 아래로 접근하는 방법으로 큰 문제에서 부분 문제로 쪼개가면서 재귀 호출을 통해 문제를 푸는 방법이다.  피보나치의 예시처럼, f(n) = f(n-2) + f(n-1)의 과정에서 함수 호출 트리의 과정에서 보이듯, n=5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나오게 된다.

이 때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다. 그래서 가장 최근의 상태 값을 메모해 두었다고 하여 Memoization 이라고 부른다.

 

참고 예제

---

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

2839번: 설탕 배달

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int N = s.nextInt();

        if(N == 4 || N == 7)
            System.out.println(-1);

        else if(N % 5 == 0)
            System.out.println(N / 5);

        else if(N % 5 == 1 || N % 5 == 3)
            System.out.println((N / 5) + 1);

        else if(N % 5 == 2 || N % 5 == 4)
            System.out.println((N / 5) + 2);
    }
}

해당 문제는 설탕 5kg을 최대한 써야지 주머니의 갯수가 줄어든다. 그러므로 각 무게를 5kg으로 나누 나머지를 생각해 보면 1, 3이 나오는 경우에는 +1개를, 2, 4가 나오는 경우에는 +2 개가 된다는 규칙이 발견된다. 이를 바탕으로 코드를 만들어주면 된다.

 

참고 자료

---

https://didu-story.tistory.com/220

[알고리즘] Dynamic Programming (동적 계획법, DP) (feat. Swift 스위프트)

https://galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)

https://kangworld.tistory.com/48

[Algorithm] 동적 프로그래밍 (DP, 동적 계획법) 이해하기 (+ 예제 코드)