[Algorithm] 동적 계획법(DP) / 탐욕법(그리디)

Algorithm

[Algorithm] 동적 계획법(DP) / 탐욕법(그리디)

mxruhxn 2024. 11. 26. 00:35

728x90

본 게시글은 '알고리즘 문제 해결 전략 1'을 읽고 단순히 정리한 내용입니다.

동적 계획법

동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 동적 계획법을 사용하는 알고리즘들 또한 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문이다.

동적 계획법과 분할 정복의 차이가 발생하는 부분은 '문제를 나누는 방식'이다. 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있다. 그러기 위해서는 각 문제의 답을 메모리에 저장해둘 필요가 있다. 이때 이미 계산한 값을 저장해 두는 메모리의 장소를 캐시(cache)라고 부르며, 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제(overlapping subproblems)라고 부른다.

분할 정복에서는 문제를 분할할 때 각 부분 문제들이 서로 연관이 없도록 나누기 때문에, 단순하게 재귀 호출을 통해 문제를 분할해도 한 부분 문제를 한 번만 해결하게 된다. 반면에 동적 계획법에서는 문제를 분할할 때, 각 문제들이 같은 부분 문제에 의존하도록 나눈다. 문제에 이런 특성이 있을 경우 단순하게 재귀 호출을 통해 각 문제를 해결하면 중복 계산이 많아진다. 그리고 계산의 중복 횟수는 분할의 깊이가 깊어질 수록 지수적으로 증가하게 된다. 다음 그림은 재귀 호출을 통한 이항 계수의 계산을 수행할 때, 수많은 중복되는 부분 문제들이 생김을 보여준다.

// 재귀 호출을 이용한 이항 계수의 계산
public int bino(int n, int r) {
    // 기저 사례: n=r(모든 원소를 다 고르는 경우) 혹은 r=0(고를 원소가 없는 경우)
    if (r == 0 || n == r) return 1;
    return bino(n-1, r-1) + bino(n-1, r);
}

함수의 중복 호출 수는 n과 r이 커짐에 따라 기하급수적으로 증가하게 된다. 위 그림을 보면, bino(8,4)를 계산하기 위해 bino(1, 0)과 bino(1, 1)을 굉장히 여러 번 반복적으로 호출하게 된다. 이를 해결하기 위해서 위에서 언급한 '캐시'를 도입할 수 있다. 입력인 n과 r이 정해져있을 때 bino(n, r)의 반환 값이 항상 일정하기 때문에 각 n, r 조합에 대해 답을 저장하는 캐시 배열을 만들어서 각 입력에 대한 반환 값을 저장하기로 하자. 함수는 매번 호출될 때마다 이 배열에 접근해 값이 저장되어 있는지를 확인한 뒤, 저장되어 있다면 이것을 즉시 반환한다. 만약 계산되어 있지 않을 경우엔 직접 계산하여 배열에 써넣고 반환한다. -> 캐시 동작 원리

이를 구현하면 다음과 같다.

// 메모이제이션을 이용한 이항 계수의 계산

// cache 배열의 모든 요소를 -1로 초기화해두자
static int[][] cache = new int[30][30];

public int binoMemo(int n, int r) {
    // 기저 사례
    if (r == 0 || n == r) return 1;

    // -1이 아니라면 한 번 계산했던 값이니 곧장 반환
    if(cache[n][r] != -1) return cache[n][r];

    return cache[n][r] = binoMemo(n-1, r-1) + binoMemo(n-1, r);
}

위처럼 함수의 결과를 저장하는 장소를 마련해두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법을 '메모이제이션(memoization)'이라고 한다. 메모이제이션을 사용하면 모든 부분 문제가 한 번씩만 계산된다고 보장할 수 있으며, 이를 통해 함수 호출 횟수가 엄청나게 감소하게 된다.

이와 같이 두 번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법을 동적 게획법이라 한다. 동적 계획법에서는 이러한 캐시를 최대한 활용할 수 있게, 중복되는 문제들이 최대한 많아지도록 설계하는 것이 좋다.

메모이제이션을 쓰면 속도가 빨라지는 건 알겠다..

그렇다면 메모이제이션은 아무때나 적용할 수 있을까?

메모이제이션을 적용할 수 있는 경우

함수의 반환 값이 그 입력 값만으로 결정되는 지의 여부를 '참조적 투명성(referential transparency)'라고 한다.

입력이 고정되어 있을 때 그 결과가 항상 같은 함수들을 '참조적 투명 함수'라고 부른다.

그리고, 메모이제이션은 참조적 투명 함수의 경우에만 적용할 수 있다.

메모이제이션 구현 패턴

동적 계획법은 가장 흔한 문제 유형이기 때문에 메모이제이션은 굉장히 자주 구현하게 된다. 때문에 한 가지 패턴을 정해두고 항상 같은 형태로 구현하는 연습을 하자. 그래야 작성하기도 편하고 디버깅하기도 쉽다.

다음을 유의하여 구현 패턴을 알아보자.

항상 기저 사례를 먼저 처리하자. 기저 사례를 먼저 확인하지 않고 cache[]에 접근하면 범위를 벗어나는 등의 오류가 있을 수 있다.
cache[]를 모두 -1로 초기화하자. -1은 해당 값이 '아직 계산되지 않았음'을 의미하는 값이다. 하지만 함수의 반환 값이 음수일 수도 있다면 이 방법은 써먹을 수 없다. 다른 방법을 찾아보자.
cache[a][b]에 대한 변수를 하나 선언한 후 이 값을 사용하자. 그리고 함수의 종료(반환)에서 해당 cache 값을 업데이트하자.

static int cache[2500][2500]; // main 함수에서 전부 -1로 초기화해두자

int solve(int a, int b) {
    // 기저 사례를 처음에 처리
    if(...) return ...;

    // (a, b)에 대한 캐시값 확인
    int ret = cache[a][b];
    if(ret != -1) return ret; // 구한 적이 있다면 곧장 반환

    // 재귀 호출을 통한 답 계산

    ...

    return cache[a][b] = ret; // 마지막에 cache 값 업데이트
}

메모이제이션의 시간 복잡도

메모이제이션은 각 입력에 대해 함수를 처음으로 호출할 때와 다음으로 호출할 때 걸리는 시간이 다르기 때문에 시간 복잡도 분석이 헷갈릴 수 있다. 그러나 메모이제이션을 사용하는 알고리즘의 시간 복잡도를 간단히 구하는 방법이 있다. 다음 식을 이용하는 것이다.

(존재하는 부분 문제의 수) * (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

이항 계수를 계산하는 binoMemo를 대상으로 적용해보자. r의 최대치는 n이므로 binoMemo(n ,r)을 계산할 때 만날 수 있는 부분 문제의 수는 최대 O(n^2)이다. 각 부분 문제를 계산할 때 걸리는 시간은 반복문이 없으니 O(1)이다. 따라서 위의 식에 따라 binoMemo(n, r)을 계산하는 데 걸리는 시간은 O(n^2) * O(1) = O(n^2)이다.

동적 계획법 레시피

대개 동적 계획법 알고리즘의 구현은 다음과 같은 두 단계로 이루어진다.

주어진 문제를 '완전 탐색'을 이용해 해결한다.
중복된 부분 문제를 한 번만 계산하도록 '메모이제이션'을 적용한다.

물론 이는 대단히 단순화한 것이다. 이후 설명에서 동적 계획법을 적용할 수 있는 문제 유형별로 유의해야 할 점과 알고리즘을 고안하는 데 필요한 과정을 소개하겠다.

바텀-업 vs 탑-다운

종류	특징	장점	단점
탑다운(Top-Down) 방식	큰 문제를 해결하기 위해 작은 문제를 호출하는 방식	작은 문제들의 결과값을 저장함으로써 동일한 계산을 반복하지 않아 시간 복잡도 감소	스택 오버플로우 발생 가능성
바텀업(Bottom-Up) 방식	작은 문제부터 차례대로 해결해 나가는 방식	부분 문제의 해를 저장하고 이를 활용하여 다음 문제를 해결함으로써 시간 복잡도 감소	초기값을 설정해줘야 하고, 작은 문제들의 결과값을 임시적으로 저장해 둘 공간이 필요

탑 다운 방식
- 재귀적으로 호출하여 문제를 해결하는 방식
- 재귀 호출을 사용하므로 스택 오버플로(Stack Overflow)문제가 발생 할 수 있음
- 큰 문제를 작은 문제로 나누어 푸는 분할정복(Divide and Conquer) 방식과 비슷하다. 다만, 중복되는 작은 문제들을 한 번만 푸는 것이 특징
- 메모이제이션을 사용하여 이전에 구한 값을 저장하고 중복 계산을 방지하기에 효율적

탑 다운 방식을 이용한 피보나치 수열 계산

public class TopDownDP {
    static int[] cache = new int[100]; // -1로 초기화

    public static int fibo(int n) {
        if (n <= 1) return n;

        int ret = cache[n];
        if (ret != -1) return ret;

        return cache[n] = fibo(n - 1) + fibo(n - 2);
    }

    public static void main(String[] args) {
        int n = 10;

        for(int i = 0; i < 100; ++i) {
            cache[i] = -1;
        }

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

바텀 업 방식
- ‘작은 문제’부터 해결하여 ‘큰 문제’까지 해결하는 알고리즘 방식
- 이 알고리즘의 핵심은 이전에 ‘계산한 부분 문제’의 결과를 저장해두고 나중에 같은 부분 문제가 나타날 때 다시 계산하지 않고 저장된 값을 사용하여 시간을 절약
- 재귀적으로 수행하지 않고 ‘반복문’을 통하여서 문제를 해결해 나아가는 방식
- 작은 문제들의 결과값을 임시적으로 저장해 둘 공간 배열이 필요하고, 초기값을 설정해줘야 함.

바텀 업 방식을 이용한 피보나치 수열 계산

public int fibo(int n) {
    if (n <= 1) return n;

    int[] memo = new int[n+1];

    // 초기값 설정
    memo[0] = 0;
    memo[1] = 1;

    for (int i = 2; i <= n; i++) {
        memo[i] = memo[i-1] + memo[i-2];
    }

    return memo[n];
}

전통적 최적화 문제

동적 계획법의 가장 일반적인 사용처는 최적화 문제의 해결이다. 최적화 문제를 동적 계획법으로 푸는 것 또한 완전 탐색에서 시작하지만, 최적화 문제에 특정 성질이 성립할 경우에는 단순히 메모이제이션을 적용하기보다 '좀 더 효율적'으로 동적 계획법을 구현할 수 있다.

여기서 '특정 성질'은 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우를 말하는데, 이를 '최적 부분 구조(optimal substructure)'가 성립한다고 한다. 이는 효율적인 동적 계획법 알고리즘을 적용하기 위해 아주 중요한 조건이다. 반면, 더 작은 문제의 최적해만으로는 전체 문제의 최적해를 구할 수 없다면 해당 문제에는 최적 부분 구조가 존재하지 않는다고 말한다.

많은 문제에서 최적 부분 구조는 굉장히 직관적으로 이해할 수 있어서 증명이 따로 필요하지 않지만, 직관적이지 않은 경우 대개 '귀류법' 혹은 '대우'를 이용해 증명한다.

최적화 문제 동적 계획법 레시피

다음은 최적화 문제의 동적 계획법을 설계하기 위한 과정을 간략하게 정리한 것이다. 물론 이 과정이 항상 모든 문제를 해결해주는 것은 아니지만, 동적 계획법에 익숙해지기 전에 어떤 식으로 생각해야 할지에 대한 대략적인 지침은 될 수 있을 것이다.

모든 답을 만들어보고 그중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계
전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾼다.
재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다.
- 문제에 최적 부분 구조가 성립할 경우, 이전 선택에 관련된 정보를 완전히 없앨 수도 있다.
- 우리의 목표는 가능한 한 중복되는 부분 문제를 '많이' 만드는 것이다. 입력의 종류가 줄어들면 줄어들 수록 더 많은 부분 문제가 중복되고, 따라서 메모이제이션을 최대한도로 활용할 수 있게 된다.
입력이 배열이거나 문자열인 경우, 가능하다면 적절한 변환을 통해 메모이제이션 할 수 있도록 한다.
- 배열이나 문자열 대신 인덱스, 시작 위치, 끝 위치 등으로 변환할 수 있는지 확인하자
메모이제이션을 적용한다.

경우의 수와 확률

동적 계획법은 애초에 최적화 문제를 풀기 위해 고안되었긴 하지만, 경우의 수를 세거나 확률을 계산하는 문제에도 흔하게 사용된다. 경우의 수를 계산하는 문제는 많은 경우 재귀적인 특성을 가지고 있기 때문이다.

경우의 수를 세는 문제에서 답은 입력의 크기에 대해 지수적으로 증가하는 것이 보통인데, 많은 경우 답이 일반적으로 사용하는 32비트 정수형의 한계를 초과하기 십상이다. 물론 큰 정수 구현을 요구할 수도 있지만, 큰 정수를 구현하기가 매우 번거롭다보니 보통 문제에서는 답을 어떤 수 M으로 나눈 나머지를 출력하기를 요구하는 식으로 이런 오버플로 현상을 해결한다. 때문에, '모듈러 연산'에 관련된 식을 미리 알아두는 것이 필수이다.

확률과 경우의 수에는 밀접한 관련이 있기 때문에 많은 경우 확률을 계산하는 문제에도 동적 계획법을 적용할 수 있다. 경우의 수를 구하는 문제와 크게 다를 것이 없어서 부분 문제의 구조는 그대로 유지하되, 경우의 수 대신 확률을 직접 계산하여 반환해주기만 하면 된다.

경우의 수 계산하기 레시피

모든 답을 직접 만들어서 세어보는 완전 탐색 알고리즘을 설계한다. 이때, 경우의 수를 제대로 세기 위해서는 재귀 호출의 각 단계에서 고르는 각 선택지에 다음과 같은 속성이 성립해야 한다.
- 모든 경우는 이 선택지들에 포함됨
- 어떤 경우도 두 개 이상의 선택지에 포함되지 않음
최적화 문제를 해결할 때처럼 이전 조각에서 결정한 요소들에 대한 입력을 없애거나 변형해서 줄인다. 재귀 함수는 앞으로 남아 있는 조각들을 고르는 경우의 수만을 반환해야 한다.
메모이제이션을 적용한다.

탐욕법(그리디)

탐욕법을 이용한 알고리즘, 혹은 '탐욕적인 알고리즘'은 우리가 원하는 답을 재귀호출과 똑가이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없다. 그러나, 모든 선택지를 고려해보고 그중 전체 답이 가장 좋은 것을 찾는 두 방법과 달리, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 즉, 탐욕법은 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다.

탐욕적 알고리즘은 그 방법이 너무 단순해서 많은 경우 최적해를 갖지 못한다. 따라서 탐욕적 알고리즘이 사용되는 경우는 크게 다음 두 가지로 제한된다.

탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다.
시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면 최적해 대신 적당히 괜찮은 근사해를 찾는 것으로 타협할 수 있다. 탐욕법은 이럴 때 최적은 아니지만 임의의 답보다는 좋은 답을 구하는 용도로 유용하게 사용된다.

위 두 가지 용도 중 보통 첫번째 용도로만 사용된다. 탐욕법의 개념은 간단하지만 매우 어렵기도 한데, 한 문제를 탐욕적으로 해결하는 방법이 무엇인지, 그 방법이 여러 개라면 이 중 어느 방법을 선택해야 최적해를 구할 수 있을지를 알아내기가 어렵기 때문이다. 실제로 최적해를 얻을 수 있는 접근이 직관적이지 않은 경우도 많기 때문에 실수에 더 유의해야 한다. 그러니 탐욕적 알고리즘 연습 문제를 풀 때는 알고리즘의 정당성을 증명하는 과정을 항상 연습하는 것이 좋다.

탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제란 무엇일까? 어떤 조건을 만족해야 하는걸까?

탐욕적인 알고리즘이 항상 최적해를 찾아낼 수 있다는 것을 다음 두 가지의 속성을 증명함으로써 보일 수 있다.

탐욕적 선택 속성 -> for 부분 문제의 최적해
- 탐욕적으로만 선택하더라도 최적해를 구할 수 있다는 것
- 탐욕적 선택 속성을 만족한다면, 각 단계에서 탐욕적인 선택은 항상 최적해로 가는 길 중 하나임을 보장한다.
- 탐욕적인 선택을 해서 '손해'를 볼 일이 없다는 것을 알 수 있다.
- 보통 일정한 패턴을 통해 증명할 수 있다.
  1. 항상 우리가 선택한 방법을 포함하는 최적해가 있음을 증명하기 위해, 우선 우리가 선택한 방법을 '포함하지 않는' 최적해의 존재를 가정한다.
  2. 그리고 이것을 적절히 조작하여 우리가 선택한 방법을 '포함하는' 최적해를 만든다.
최적 부분 구조 -> for 전체 문제의 최적해
- 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 의미한다.
- 이 속성은 대개 매우 자명해서 따로 증명할 필요가 없는 경우가 대부분이다.

탐욕법으로 최적해를 찾을 수 있는 많은 문제들은 동적 계획법으로도 풀 수 있다. 그도 당연한 것이, 탐욕법으로 최적해를 찾을 수 있다는 말은 지금 한 단계만을 고려해도 답을 찾을 수 있다는 의미이다. 모든 단계를 고려하는 동적 계획법이 답이 틀릴 이유가 없다.

많은 경우 동적 계획법이 아니라 탐욕법을 사용하는 이유는 동적 계획법에 필요한 메모리나 시간이 과도하게 크기 때문이다. 즉, 동적 계획법으로 풀기에는 시간이 너무 오래 걸리거나 공간이 부족하다면 탐욕법을 떠올려보자

탐욕적 알고리즘 레시피

문제의 답을 만드는 과정을 여러 조각으로 나눈다.
각 조각마다 '어떤 우선순위'로 선택을 내려야 할지 결정한다. 이에 대한 직관을 얻기 위해서는 예제 입력이나 그 외의 작은 입력을 몇 개 손으로 풀어보는 것이 효율적이다.
어떤 방식이 동작할 것 같으면, 두 가지의 속성을 증명해본다.
- 탐욕적 선택 속성: 항상 각 단계에서 선택한 답을 포함하는 최적해가 존재함을 보이면 된다. 이 증명은 대개 우리가 선택한 답과 다른 최적해가 존재함을 가정하고, 이것을 조작해서 우리가 선택한 답을 포함하는 최적해로 변경할 수 있음을 보이는 형태(패턴)로 이루어진다.
- 최적 부분 구조: 각 단계에서 항상 최적의 산택만을 했을 때 전체 최적해를 구할 수 있는지 여부를 증명한다. 다행히도 대개의 경우 이 속성이 성립하는지 아닌지는 따로 증명없이 자명하게 알 수 있다.

728x90