[종만북] Dynamic Programming / DP / 동적 계획법

Algorithmic Problem Solving Strategies 

개인적으로 읽고 정리한 요약입니다.

아래 링크에 문제 풀이 예제가 있습니다.

GitHub - chanheki/AlgorithmicProblemSolvingStrategies: Algorithm Book Study

---

동적 계획법

도입

동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나.

최적화 문제를 연구하는 수학 이론에서 파생, 우리가 전산학 전반에서 일반적으로 사용하는 동적(dynamic), 혹은 프로그래밍(programming)이란 단어와는 아무런 관련이 없다.

따라서 DP의 적절한 번역은 동적 계획법이다.

---

중복되는 부분 문제

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

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

어떤 가상의 문제에 대한 두 개의 다른 분할 방식이 어떻게 달라지는지, 그리고 이를 통해 중복되는 부분 문제의 개념을 볼 수 있다.

각 사각형이 전체 문제의 부분 문제를 나타내고, 매 단계마다 입력을 두 조각으로 쪼개 화살표 방향으로 재귀 호출한다고 한다. 좌측에서는 각 문제들이 서로 연관이 없기 때문에, 단순하게 재귀 호출을 통해 문제를 분할해도 한 부분 문제를 한 번만 해결하게 된다. 그러나 우측에서는 나눠진 각 문제들이 같은 부분 문제에 의존한다.

문제에 이런 특성이 있을 경우 단순하게 재귀 호출을 통해 각 문제를 해결하면 중복 계산이 많아진다. 조합 폭발(combinatorial explosion)이 발생.

동적 계획법 알고리즘의 가장 유명한 예 중 하나는 이항 계수 (binomial coefficent)의 계산.

이항 계수은 n개의 서로 다른 원소 중에서 r개의 원소를 순서 없이 골라내는 방법의 수를 나타낸 것
이항 계수에는 다음과 같은 점화식이 성립.
점화식(recurrence)이란 재귀적으로 정의되는 수학적 함수를 의미.

이 점화식을 이용하면 n, r의 값이 주어질 때 (n r)의 값을 반환하는 함수
bino(n, r)를 작성할 수 있다.

func bino(_ n: Int,_ r: Int) -> Int {
    if r == 0 || n == r { return 1 }
    return bino(n-1, r-1) + bino(n-1, r)
}

이 알고리즘의 시간 복잡도는, bino() 내에 어떤 반복문도 없기 때문에, bino(n, r)의 수행 시간은 재귀 호출이 몇 번이나 이루어지는지를 계산하면 파악할 수 있다.

이때 주목할 점은 이항 계수의 특성상 같은 값을 두 번 이상 계산할 일이 빈번하다는 것.

위 그림을 보면 중복되는 함수들이 생긴다는 것을 알 수 있다.

함수의 중복 호출 수는 n과 r이 커짐에 따라 기하급수적으로 증가.

bino(n, n/2)를 계산하기 위해 필요한 함수 호출의 수를 계산해 보면 n이 하나 증가할 때마다 함수 호출의 수가 거의 두 배 증가하는 것을 볼 수 있다.

bino(25, 12)를 이와 같이 계산하게 되면 천만번의 함수 호출이 일어나게 된다.

입력인 n과 r이 정해져 있다면 bino(n, r)의 반환 값이 일정하다는 사실을 이용하면 이 문제에서 중복 계산을 제거할 수 있다. 각 n, r조합에 대해 답을 저장하는 캐시 배열을 만들어서 각 입력에 대한 반환 값을 저장한다면, 함수는 매번 호출될 때마다 이 배열에 접근해 값이 저장되어 있는지 확인한 뒤, 저장되어 있다면 이것을 즉시 반환한다. 만약 계산이 되어 있지 않다면 직접 계산해서 배열에 써넣고 반환한다.

n	2	3	4	5	6	...	18	19	...	24	25
bino() 호출 횟수	3	5	11	19	39	...	97239	184755	...	5408311	10400599
bino2() 호출 횟수	3	5	8	11	15	...	99	109	...	168	181

이와 같이 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법을
메모이제이션(memoization)이라고 한다.

var cache = Array(repeating: Array(repeating: -1, count: 30), count: 30)

func bino2(_ n: Int, _ r: Int) -> Int {
    if r == 0 || n == r { return 1 }
    if cache[n][r] != -1 { return cache[n][r] }

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

메모이제이션을 사용하면 모든 부분 문제가 한 번씩만 계산된다고 보장할 수 있기 때문에 함수 호출 횟수가 엄청나게 감소한다는 것을 예상할 수 있다. 실제로 n이 증가할 때 두 배씩 증가하던 bino의 호출 횟수가 bino2에서는 n의 제곱꼴로 증가하게 되는 것을 볼 수 있다.

이와 같이 두 번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법을 동적 계획법이라고 한다.

---

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

함수의 반환 값이 그 입력 값만으로 결정되는지 여부를 참조적 투명성(referential transparency)라고 부릅니다. 입력이 고정되어 있을 때 결과가 항상 같은 함수들을 참조적 투명 함수라고 부른다.(Referential Transparent Function)

당연하게도 메모이제이션은 참조적 투명 함수의 경우에만 적용할 수 있다. 입력이 같은데도 외부 요소에 따라 다른 값이 반환된다면 캐싱할 수 없기 때문이다.

---

메모이제이션 구현 패턴

DP는 가장 흔한 문제 유형 중 하나이기 때문에 메모이제이션은 굉장히 자주 구현된다.

그런 만큼 한 가지 패턴을 정해두고 항상 같은 형태로 구현하기로 하면 작성하기도, 버그를 찾기도 쉬워진다. 이 책에서는 항상 한 가지 형태로 메모이제이션을 구현한다.

// a와 b는 각각 Array(0..<2500)
// 반환 값은 항상 int형 안에 들어가는 음이 아닌 정수
func someObscure (_ a: Int, _ b: Int) -> Int {}

someObscure은 한 번 계산하는 데 굉장히 시간이 오래 걸리는 참조적 투명 함수라고 가정하고 이 함수를 어떻게 메모이제이션으로 바꿔 구현할 것인지.

• 항상 기저 사례를 제일 먼저 처리합니다. 입력이 범위를 벗어난 경우 등을 기저 사례로 처리하면 매우 유용한데, 기저 사례를 먼저 확인하지 않고 cache[]에 접근하면 범위를 벗어나는 등의 오류가 존재할 수 있으니 조심할 것.
• 함수의 반환 값이 항상 0 이상이라는 점을 이용해 cache[]를 모두 -1로 초기화.
  cache[]의 해당 위치에 적혀 있는 값이 -1이라면 이 값은 계산된 반환값일리 없음.
  만약 함수의 반환 값이 음수일 수도 있다면 이 방법은 사용 불가능.
• ret가 cache[a][b]에 대한 참조형(refence)이라는 데 유의. 참조형 ret의 값을 바꾸면 cache[a][b]의 값도 변하기 때문에 답을 저장할 때도 매번 귀찮게 cache[a][b]라고 쓸 필요가 없어짐. 이 트릭은 특히 cache가 다차원 배열일 때 유용합니다. 인덱스 순서를 바꿔 쓸 때 실수할 가능성을 없애줌.

// 전부 -1로 초기화. 선언할 때 초기화와 선언을 동시에 한다.
var cache = Array(repeating:Array(repeating: -1, count: 2500), count: 2500)
// a와 b는 각각 Array(0...2500)
// 반환 값은 항상 int형 안에 들어가는 음이 아닌 정수
func someObscure (_ a: Int, _ b: Int) -> Int {
    // 기저 사례를 처음에 처리한다.
    if ... {return ...}
    // (a,b)에 대한 답을 구한 적이 있으면 곧장 반환
    var ret = cache[a][b]
    if ret != -1 {return ret}
    // 여기서 답을 계산
    ...
    return ret
}

해당 패턴을 그대로 따를 필요는 없지만, 자신이 가장 좋다고 생각하는 방식을 하나 정해 일관되게 사용하는 것이 좋다.

---

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

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

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

위 식을 이항계수 bino2에 적용해 보면. r의 최대치는 n이니 bino2(n, r)을 계산할 때 만날 수 있는 부분 문제의 수는 최대 O(n²). 각 부분 문제를 계산할 때 걸리는 시간은 반복문이 없으니 O(1). 그러면 위 식에 따라 bino2(n, r)을 계산하는 데 걸리는 시간 복잡도는 O(n²) X O(1) = O(n²)

---

예제: 외발 뛰기

간단한 예제를 토대로 dp알고리즘을 설계하는 과정을 알아보자.

n X n 크기의 격자에 1 ~ 9까지의 정수를 쓴 게임판에서 왼쪽 위칸에서 시작해서 게임판의 맨 오른쪽 아래 칸에 도착하는 것이 목적. 이때 각 칸에 적혀있는 숫자만큼 아래쪽이나 오른쪽으로 이동할 수 있음, 중간에 게임판 밖으로 벗어나면 안 된다.
문제는 게임판이 주어질 때 시작점에서 끝점으로 도달하는 방법이 존재하는지 확인하는 것.

재귀 호출에서 시작하기

동적 계획법 알고리즘을 만드는 첫 단계는 해당 문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만드는 것. 완전 탐색 알고리즘은 맨 왼쪽 윗 칸에서 시작하는 모든 경로를 하나씩 만들어 보면서 마지막 칸에 도달할 수 있는지 검사.

jump(y, x) = (y, x)에서부터 맨 마지막 칸까지 도달할 수 있는지 여부를 반환

jump()는 한 번 호출될 때마다 여기서 아래로 뛸지 오른쪽으로 뛸지 선택하면 된다.
게임판의 (y, x) 위치에 있는 수를 jumpsize라고 하면 각 경우 아래쪽으로 뛸 경우 마지막 칸에 도달할 수 있는지를 jump(y + jumpsize), 오른쪽으로 뛸 경우 jump(y, x + jumpsize)로 표현 가능. 이 두 경우 하나만 성공해도 상관없으니 jump(y, x)는 다음과 같이 재귀적으로 표현 가능

jump(y, x) = jump(y + jumpsize, x) || jump(y, x + jimpsize)

기저 사례를 확인하는 부분을 제외하고 점화식과 완전히 똑같음을 알 수 있다.

var n: Int
var board = Array(repeating: Array(repeating: 0, count: 100), count: 100)
func jump(_ y: Int, _ x: Int) -> Bool {
    // 기저 사례: 게임판 밖을 벗어난 경우
    if y >= n || x >= n { return false }
    // 기저 사례: 마지막 칸에 도착한 경우
    if y == n-1 && x == n-1 { return true }
    jumpsize = board[y][x]
    return jump(y + jumpsize, x) || jump(y, x + jumpsize)
}

메모이제이션 적용하기

"원하는 답이 존재하는가?"라는 질문을 완전 탐색으로 구할 때 흔히 가장 문제가 되는 것은, 원하는 답은 없는데 전체 답의 개수는 무지막지하게 많은 경우.

외발 뛰기 문제의 최악의 입력.

끝에 인접한 칸들에 2가 쓰여 있기 때문에 아무리 노력해도 끝에 도달할 수 없음.
하지만 완전 탐색은 이 중 어떤 경로는 마지막 칸에 도달할지도 모른다고 생각하고 수없이 많은 경로들을 일일이 탐색. 완전 탐색이 포기하기 전까지 만들어야 하는 경로의 개수는 n에 대해 지수적으로 늘어나므로, n = 100이면 제한시간을 초과.

여기서 주목할 것은 완전 탐색이 만드는 경로의 수는 엄청나게 많지만 jump()에 주어지는 입력의 개수는 100 X 100 = 10000개뿐이라는 사실.

이는 비둘기집의 원리에 의해 중복으로 해결되는 부분 문제들이 항상 존재함. jump()는 참조적 투명 함수 이므로 메모이제이션을 적용해서 중복된 연산을 없앨 수 있음.

반환값이 Int형이라는데 유의할 것.

var n: Int
var board = Array(repeating: Array(repeating: 0, count: 100), count: 100)
var cache = Array(repeating: Array(repeating: 0, count: 100), count: 100) 
func jump2(_ y: Int, _ x: Int) -> Int {
    // 기저 사례 처리
    if y >= n || x >= n { return false }
    if y == n-1 && x == n-1 { return true }
    // 메모이제이션
    var ret = cache[y][x]
    if ret != -1 { return ret }
    var jumpsize = board[y][x]
    return ret = jump(y + jumpsize, x) || jump(y, x + jumpsize)
}

---

다른 해법

이 문제는 사실 그래프로 모델링해보면 아주 간단한 도달 가능성 문제가 된다.

---

동적 계획법 레시피

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

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

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

---

다른 구현 방법에 관하여

물론 재귀 호출을 이용하지 않고도 동적 계획법 알고리즘을 구현할 수 있다.
이런 방법을 반복적 동적 계획법이라고 부른다. 반복적 동적 계획법에도 많은 장점이 있지만, 메모이제이션을 통한 접근이 좀 더 직관적이기 때문에 이 장에서는 기본적으로 모든 동적 계획법 알고리즘을 재귀 호출을 통해 구현.

---

예제: 와일드카드

와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법.
이때 사용하는 문자열을 와일드카드 패턴이라고 한다.
패턴은 일반적인 파일명과 비슷하지만 특수 문자 *나?를 포함할 수 있는 문자열.

와일드카드 패턴을 앞에서 한 글자씩 파일명과 비교해서 모든 글자가 일치했을 때 해당 와일드카드 패턴이 파일명과 대응된다고 말한다. 단 와일드카드 패턴에 포함된? 는 어떤 글자와도 대응된다고 가정하며, _는 0 글자 이상의 어떤 문자열에도 대응된다고 가정. 예를 들어 와일드카드 he? p는 파일명 help에도, heap에도 대응되지만, helpp에는 대응되지 않음, 반면 와일드카드 `_p*`는 파일명 help에도, papa에도 대응되지만 hello에는 대응되지 않습니다.

와일드카드 패턴과 함께 파일명의 집합이 주어질 때, 그중 패턴에 대응되는 파일명들을 찾아내는 프로그램을 작성

시간 및 메모리 제한

프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합 니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(l <=C <=10)가 주어집니다. 각 테스트 케이스의 첫 줄에는 와일드카드 패턴 W가 주어집니다. 그다음 줄에 파일명의 수n(1<=n<=50)이 주어지고, 그 후 n줄에 하나씩 각 파일명이 주어집니다. 와일 드카드 패턴은 알파벳 대소문자, 숫자와 *, ?만으로 구성되며, 파일명은 알파벳 대소문자와 숫자만으로 이루어집니다. 모든 문자열의 길이는 1 이상 100 이하이며, 공백을 포함하지 않습니다.

출력

각 테스트 케이스마다 주어진 패턴에 대응되는 파일들의 이름을 한 줄에 하나씩 알파벳 순서대로 출력합니다.

예제 입력

3 he?p
3
help
heap
helpp
*p*
3
help
papa
hello
*bb*
1
babbbc

예제 출력

heap
help
help
papa
babbbc

풀이

*가 문제

이 문제를 어렵게 만드는 것은 *가 몇 글자에 대응되어야 하는지를 미리 알 수 없다는 점.
단순하게는 * 다음에 출현하는 글자가 나올 때까지 대응시킬 수 있습니다만, 이래서는 입력의 세 번째 예제를 제대로 해결할 수없음. 이럴 때 우리가 할 수 있는 가장 쉬운 방법은 완전탐색.

주어진 패턴이 m개의 *을 포함한다고 했을 때, 이 패턴을 *가 나타날 때마다 쪼개면 이 패턴이 문자열에 대응되는지 확인하는 문제를 m+1조각으로 나눌 수 있다.

주어진 패턴이 m개의 *을 포함한다고 했을 때, 이 패턴을 *가 나타날 때마다 쪼개면 이 패턴이 문자열에 대응되는지 확인 하는 문제를 m+1조각으로 나눌 수 있다.

예를 들어 *t*l?*o*r?ng*s*는 [t*, l?*, o*, r?ng*, s]의 다섯 조각으로 쪼갤 수 있다. 문자열 thelordoftherings가 주어질 때 우리의 완전 탐색 함수는 이 문자열 중 모두 몇 글자가 첫 번째 조각에 대응될지를 찾아 내기 위해 모든 경우의 수를 다 시도해본다. 만약 첫 번째 조각에 세 글자가 대응된다면, 나머지 문자열 lordoftherings가 나머지 네 개의 패턴 조각들에 대응되는지 여부를 재귀 호출로 파악 가능

// 완전탐색

// 와일드 카드 패턴 w가 문자열 s에 대응되는지 여부를 반환
func match(_ W: String, _ S: String) -> Bool {
    // w[pos]와 s[pos]를 맞춰나간다.
    let w = W.map{String($0)}
    let s = S.map{String($0)}
    var pos = 0
    while pos < s.count && pos < w.count && (w[pos] == "?" || s[pos] == w[pos]) {
        pos += 1
    }
    // 더이상 대응할 수 없으면 왜 while문이 끝났는지 확인한다.
    // 2. 패턴 끝에 도달해서 끝난경우: 문자열도 끝났어야 대응됨
    if pos == w.count { return pos == s.count }
    // 4. *을 만나서 끝난 경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다.
    if w[pos] == "*" {
        for skip in pos...s.count {
            if match((w[pos+1..<w.count]).joined(), (s[skip..<s.count]).joined()) {
                return true
            }
        }
    }
    return false
}

// 메모이제이션 기법을 사용해서 푼 풀이

func match(_ w: String, _ s: String) -> Bool {
    // w[pos]와 s[pos]를 맞춰나간다.
    let W = w.map{String($0)}
    let S = s.map{String($0)}

    return matchMemoized(0, 0) != 0 ? true : false

    // 와일드카드 패턴 W[w...]가 문자열 S[s...]에 대응되는지 여부를 반환합니다.
    func matchMemoized(_ w: Int, _ s: Int) -> Int {
        // 메모이제이션
        var ret = cache[w][s]
        if ret != -1 { return ret }
        // W[w]와 S[s]를 맞춰 나간다.
        while s < S.count && w < W.count && (W[w] == "?" || W[w] == S[s]) {
            ret = matchMemoized(w+1, s+1)
        }
        // 더이상 대응할 수 없으면 왜 while문이 끝났는지 확인.
        // 2. 패턴 끝에 도달해서 끝난경우: 문자열도 끝났어야 대응됨(참)
        if w == W.count {
            if s == S.count { ret = 1 }
            return ret
        }
        // 4. *을 만나서 끝난경우 *에 몇글자를 대응해야 할지 재귀 호출 하면서 확인한다.
        if W[w] == "*" {
//            for skip in s...S.count {
            if (matchMemoized(w+1, s) != 0) || (s < S.count && (matchMemoized(w+1, s) != 0)) {
                    ret = 1
                    return ret
                }
//            }
        }
        // 3. 이 외의 경우에는 모두 대응되지 않는다.
        ret = 0
        return ret
    }
}