알고리즘/문제 풀이 비법

동적 계획법 (Dynamic Programming)

Leo.K 2023. 6. 26. 15:38

※ 소개

오늘은 오랜만에 코딩테스트 문제풀이를 위한 알고리즘을 정리해보고자 한다. 
평소에도 문제풀이를 할때 논리가 부족해서 그런지 정렬이나 탐색 알고리즘보다 그리디나 동적 계획법쪽이 많이 어려웠는데 이번기회에 마리오 형의 강의를 참고해서 확실히 개념정리를 하고 문제를 풀어보면서 연습해보고자 한다. 

알고리즘 기법의 명명 과정을 웃고 넘어갈 겸 살펴보니 다이나믹은 멋있어 보여서 붙였다고 한다... (괜히 있어보이긴 함)
프로그래밍이라는 단어는 컴퓨터 언어로 코딩을하는 것이 아니라 어떤 것을 계획하는 것을 의미하는 바가 크다. 
즉, 문제가 있으면 특수한 형태로 변형시켜 쉽게 풀어내기 위한 일련의 과정이다. 

입문하기는 쉽지만 마스터하기는 아주 어려운,,, 하지만 대회에서도 자주 출제되어 거의 뭐 알고리즘 학문에서는 기본 소양으로 취급되는 기법이라고 한다. 따라서 처음 입문할 때 쉬운 문제부터 풀어보면서 문제를 풀이하는 감을 익혀야 한다.
이러한 동적 계획법을 잘 파악하고 연습이 잘 된다면 풀 수 있는 문제가 상당히 많아지기 때문에 DP를 통해서 알고리즘에 재미를 붙이는 사람이 많다고 한다. 나도 그랬지만,,, 조금 더 어려운 문제를 맞닥뜨리니 벽느끼고 다시 공부를 한다..

※ 개념

동적계획법이란...? 

주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푸는 것이다. 
정의만 들어보니 분할 정복과 굉장히 비슷한 것 같은 느낌이 있지만 결정적인 차이점이 존재한다. 바로 부분 문제들끼리 겹치는 문제가 있느냐 없느냐의 차이다.

분할정복은 동일한 규칙이 부분 문제에 적용되기 때문에 문제를 분할하여 해결하지만, 각 부분 문제가 겹치지 않는다.
하지만 동적계획법은 분할한 부분문제가 겹치는 부분이 있기 때문에 메모이제이션을 사용하며 이를 통해 실행시간 단축의 효율성을 얻을 수 있다.

또한 모든 경우를 별도의 메모리까지 소비하여 샅샅이 뒤진다는 점에서 실행시간이 그리디 알고리즘에 비해서는 떨어지지만, 눈 앞의 이익만을 쫓는 그리디 보다는 좀 더 폭넓은 범위에서 근사치가 아닌 정확한 값을 찾을 수 있다. 

※ 예시

동적 계획법을 설명하기 위한 가장 쉬운 예시로 일반인에게도 익숙한 피보나치 수열이 있다.

피보나치 수열의 점화식은 위와 같다. n이 1이하인 경우에는 값이 정해져 있고, 2 이상인 경우에는 이전 항들의 값으로 결정된다. 이런식으로 이전항이 현재항에 결과를 미치는 수열은 아주 다양한데, 그 중에서도 피보나치 수열의 경우는 바로 전 2개의 항의 값에 영향을 받는 특수한 형식이다.

 

위의 점화식을 재귀함수로 구현하면 아래와 같은 코드를 구성할 수 있다. 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        System.out.println("fibonacci(N) = " + fibonacci(N));
    }

    private static int fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

n번째 피보나치 수열의 항을 구하기 위해서는 n보다 작은 항들의 정보가 반드시 필요한 구조이다. 
일단 이렇게 코드를 짜고 N을 입력하면 N번째 피보나치 항을 잘 구해주지만 N값이 조금 커져서 40만 넘어가도 연산횟수가 N에 기하급수적으로 비례하게 증가하여 실행시간이 오래 걸리게 되고, 웬만한 컴퓨터에서는 바로 답을 구하지 못한다. 

그렇다면 각각의 현재 항을 구하기 위해 이전 항들을 몇 번 호출하게 되는지 Map을 추가하여 특정 항이 호출되는 횟수를 살펴보자. 

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    private static Map<Integer, Integer> call;
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        call = new HashMap<>();
        System.out.println("f("+ N + ") = " + " " + fibonacci(N));

        System.out.println("호출 횟수");
        for (int i=0; i<= N; i++){
            System.out.println("f("+ i + ") = " + call.get(i) + "회 호출");
        }
    }

    private static int fibonacci(int n) {
        call.put(n, call.getOrDefault(n, 0) + 1);
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fibonacci(n-1) + fibonacci(n-2);
    }
}
더보기

10
f(10) =  55
호출 횟수
f(0) = 34회 호출
f(1) = 55회 호출
f(2) = 34회 호출
f(3) = 21회 호출
f(4) = 13회 호출
f(5) = 8회 호출
f(6) = 5회 호출
f(7) = 3회 호출
f(8) = 2회 호출
f(9) = 1회 호출
f(10) = 1회 호출

 

위와 같은 결과를 확인할 수 있는데, 간단히 살펴 보면 n이 0을 제외한 작은 수로 다가갈수록 더 많이 호출된다는 것을 확인할 수 있고, 마찬가지로 0을 제외하면 각 항들 또한 피보나치 수열을 이루고 있음을 확인할 수 있다. (55 = 34 + 21, 34 = 21 + 13 ...)
이렇게 호출횟수가 불필요하게 증가하는 이유를 파악해보기 위해 피보나치 수열의 프로그램 실행  상황을 한 번 살펴보자.

fib(7)의 값을 구하기 위해서는 바로 그 이전의 두 개항 fib(6)과 fib(5)의 값을 알아야 한다. 그런데 fib(6)의 값을 구할 때도 fib(5)와 fib(4)의 값을 구해야 하기 때문에, fib(7)의 값을 구하기 위해 fib(6)을 계산한 시점에 프로그램은 이미 fib(5)의 값이 무엇인지도 계산을 했다. 하지만, 뒤에 fib(5)를 다시 계산할 때 프로그램은 자신이 연산한 값은 잊어버리고 이미 구한 값을 구하기 위해 또 같은 연산을 진행하고 있다. 
이 때문에 n의 값이 작아질수록 반복적으로 호출되는 횟수가 증가하는 것이다. 

 

그림이 너무 복잡해지는 것을 방지하기 위해 가장 큰 단위의 두 개의 연산만 같은 색으로 표시했다. 
표시한 부분을 보면 구조가 완전히 동일하고 당연히 해당 구조에서 계산되는 값 역시 동일할 것이다. 
즉, 한 번만 계산하면 충분할 연산을 위의 소스 코드는 호출시마다 계속 부르면서 중복 연산을 통해 불필요한 시간 낭비를 하고 있다는 것이다. 

 

※ 메모이제이션

이러한 불필요한 시간 낭비를 줄이기 위해 동적계획법의 꽃이라고 불리우는 메모이제이션 기법을 사용해야 한다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int[] call;

    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        call = new int[N+1];
        Arrays.fill(call, -1);
        System.out.println("fibonacci(N) = " + fibonacci(N));

    }

    private static int fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if(call[n] != -1) return call[n];
        else call[n] = fibonacci(n-1) + fibonacci(n-2);

        return call[n];
    }
}

위의 코드를 한 번 살펴보자 

call이라는 전역 배열을 만들었다. 자료구조는 무엇을 사용하던 상관없지만 가장 보편적인 배열을 정의해서 사용해보자. 그리고 피보나치 수열에서 절대 나올 수 없는 값으로 입력받은 크기 N의 배열의 각 요소를 초기화한다. 

그 후에 피보나치 함수에서는 먼저 call[n]의 값을 확인하여 이미 계산한 적이 있는 값인지의 여부(-1인지 아닌지)를 확인한다. 계산한 적이 있다면(-1이 아니라면) 추가적인 재귀호출 없이 값을 바로 리턴해버린다. 
계산한 적이 없다면 값을 계산해서 초기화해준다.

중요한 것은 이러한 메모이제이션을 구현하는 기법은 문제를 풀이하기 위한 점화식을 해석하기 나름이라 메모이제이션 기법 자체라는 것이다. 
위와 같이 재귀함수를 사용하여 동적 계획법을 구현하는 방식을 Top-Down 방식이라고 한다. 

동적 계획법은 재귀함수가 아닌 반복문을 통해서도 구현이 가능한데, 이는 Bottom-Up방식이라고 부르며 아래 코드를 보자

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int[] call;

    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        call = new int[N+1];
        Arrays.fill(call, 0);
        call[1] = 1;
        for(int i=2; i<=N; i++){
            call[i] = call[i-1] + call[i-2];
        }
        System.out.println("call[N] = " + call[N]);
    }
}

문제에 따라 재귀함수를 호출하는 것이 더 쉬울 수도 있고, 반복문을 사용하는 것이 더 쉬울수도 있다. 
중요한 것은 문제를 정확하게 분석해서 점화식을 올바르게 세우고, 재귀나 반복이나 시간복잡도가 O(N)으로 동일한 것을 인지하여 적당한 풀이방법을 구현하는 것이다. 
이는 특별한 지름길이 있다기 보다는 연습만이 살길이다..

※ 정리

피보나치 문제의 경우, F(N)을 구하기 위해 풀어야 하는 부분 문제가 F(N-1)과 F(N-2)인 셈이다. 
base case인 문제들부터 차근차근 풀어 나가며 원래 풀려던 문제의 답까지 계산해 나가는 것이다. 
모든 항을 한 번씩은 계산하기 때문에 F(N)을 구할 때 풀어야 하는 문제의 개수는 O(N)개이고, 따라서 이 답을 모두 저장할 O(N)의 메모리가 필요하며, 각각의 문제를 푸는데 걸리는 시간이 O(1)이므로, N개의 문제를 푸는 데 걸리는 시간은 O(N)이다. 

Top_Down : 재귀 호출로 구현을 하며, 가장 먼저 호출하는 문제가 가장 큰 문제 이기 때문에 이렇게 명명되었다.
    가독성이 좋고, 본래의 점화식을 이해하기 쉽다는 장점이 있다. 

Bottom_Up : 반복을 사용해 구현하며, 작은문제들로부터 차례 차례 쌓아올려가며 큰 문제를 풀기에 이렇게 명명되었다.
    재귀와 달리 함수를 호출하지 않아 시간과 메모리를 소량 절약할 수 있다는 장점이 있다.

 

※ 연습문제

  • BOJ 1463
    • 메모이제이션을 사용하지 않고 전역변수 count를 사용해 연산이 일어날 때마다 카운트를 증가시키고자 했는데
    • 조건분기가 제대로 되지도 않을 뿐더러 동적계획법의 취지와 어긋난다.
    • 전역배열을 선언하고, 각 인덱스에는 인덱스 값을 1로 만들기 위해 필요한 최소 연산횟수를 메모이제이션.
    • 현재 값(N)에서 1을 뺀 결과 {F(N-1) + 1}와 3 또는 2로 나눈 결과{F(N/3 or 2) + 1} 중에서 최솟값을 저장한다.
    • +1을 하는 이유는 재귀 호출을 함과 동시에 연산이 진행되었다고 판단하여 연산횟수를 증가시키는 것이다.
  • BOJ 2193
  • BOJ 1904
  • BOJ 11726
  • BOJ 11727
  • BOJ 9465
  • BOJ 2294
  • BOJ 1699
  • BOJ 11052
  • BOJ 10844
  • BOJ 11057
  • BOJ 11051
  • BOJ 12865
  • BOJ 16500
  • BOJ 11055

 

## Reference

저작자표시

'알고리즘 > 문제 풀이 비법' 카테고리의 다른 글

Do it! 코딩테스트-기초편. 3_자료구조  (0) 2023.03.13
알고리즘 선택의 기준_시간복잡도  (0) 2023.03.06
조합 Combination  (0) 2022.11.02
최소공통조상  (0) 2022.10.26
트리  (0) 2022.09.21
Leo.K | To become a cooler Developer
프로필사진

티스토리툴바