네, 드디어 찐막입니다. 시원섭섭하지는 않고, 굉장히 기분이 좋습니다. 마지막 피날레는 다이나믹 프로그래밍 심화로 장식하려고 합니다. 원래 본 강의에 다이나믹 프로그래밍이 포함되어 있긴 했습니다. 그런데 그 부분에서는 비교적 간단한 문제들만 다뤘기 때문에, 내용 보강이 필요하긴 했습니다.

 

코딩 테스트를 기준으로 하더라도 0x10강에서 다룬 수준보다는 더 어려운 문제가 충분히 출제될 수 있습니다. 그렇다고 해서 다이나믹 프로그래밍을 처음 접한 상황에서 어려운 문제들까지 모두 다루기는 어렵습니다. 그래서 문제집에 문제들만 많이 모아두고, 알아서 풀면서 익혀보라는 방식이었습니다.

 

저는 다이나믹 프로그래밍만큼은 강의에서 엄청 특별한 팁을 드리기 어렵다고 생각합니다. 결국 문제를 보고 테이블을 어떻게 잡고, 식을 어떻게 세울지를 스스로 알아내야 합니다. 이 부분은 특별한 테크닉이 필요한 것이 아니라, 많은 DP 문제를 접하면서 그 감각을 익히는 수밖에 없습니다.

 

그래서 0x10강에서 같이 풀었던 문제들 외에도, 문제집에 있는 문제들을 가지고 고민을 많이 해보시고, 풀이도 찾아보셨다면 자연스럽게 실력이 향상되었을 것입니다. 그럼에도 불구하고 이번에 다이나믹 프로그래밍 심화 단원을 새로 만든 이유는, 자주 등장하는 DP 유형을 다시 한번 정리하고, 좋은 문제들을 추천해드리고 싶었기 때문입니다. 그러면 강의를 시작하겠습니다.

 

 

우선 다이나믹 프로그래밍(DP)이 무엇인지에 대해 조금 더 심화된 내용까지 포함하여 다시 한 번 짚어보겠습니다. 그리고 2차원 DP 문제도 몇 가지 함께 풀어볼 예정입니다. 다음으로는 기존 DP 단원에서는 설명드리지 못했던 Top-down 방식으로 DP를 해결하는 방법에 대해서도 설명드릴 예정입니다. 마지막으로 트리 DP와 위상 정렬을 활용한 DP 문제도 함께 풀어보면 이번 단원이 마무리됩니다. 이번 단원에서도 다양한 문제를 많이 풀어볼 예정이며, 문제집에도 문제를 충분히 수록해둘 예정이니, 열심히 풀어보시기 바랍니다.

 

 

원래 다이나믹 프로그래밍(DP) 단원에서 알고리즘을 소개할 때 사용했던 슬라이드를 다시 가져왔습니다. 이 슬라이드가 무엇을 의미하는지는 기억하시죠? 피보나치 수열을 계산할 때, 중간값을 저장하지 않고 단순히 재귀 호출만 반복하면 중복 계산이 계속 발생하게 되어, 시간 복잡도가 지수적으로 증가합니다. 반면, 배열을 미리 선언하고 중간 결과를 저장하는 방식으로 DP를 적용하면, 의도한 대로 N번째 피보나치 수를 O(N) 시간에 계산할 수 있습니다.

 

처음 강의를 구성하면서 DP를 소개드릴 때에는 "그렇게 어렵지 않다", "구현이 비교적 간단한 편이다"라고 설명드렸습니다. 실제로 저 자신도 DP가 크게 어렵지는 않을 것이라고 생각했었습니다. 그러나 막상 강의를 만들고 나서, 수강하신 많은 분들로부터 "DP가 정말 어렵다"는 후기를 받으면서, 제가 예상했던 것과는 많이 다르다는 점을 느꼈습니다.

 

하지만 한 가지 말씀드릴 수 있는 점은, 적어도 코딩 테스트 수준에서는 오히려 DP가 다른 알고리즘보다 유리할 수도 있다는 점입니다. 예를 들어 그리디나 구현 유형의 문제는 출제자의 의도나 문제 구성 방식에 따라 완전히 새로운 형태로 등장할 수 있기 때문에, 유사한 문제를 찾기가 어렵습니다. 반면 DP 문제는 출제자가 난이도를 비정상적으로 높이지 않는 한, 반드시 일정한 방식으로 테이블을 잡고 점화식을 세우는 패턴이 존재합니다. 그렇기 때문에 제가 계속 강조드리는 부분이기도 하지만, 좋은 문제들을 많이 풀어보면서 다양한 유형을 익히면 충분히 대비할 수 있습니다.

 

 

그리고 처음 다이나믹 프로그래밍을 다뤘을 때와는 달리 지금은 그래프에 대한 내용을 학습한 이후이기 때문에 DP에 대해 좀 더 깊이 있는 설명을 드릴 수 있습니다. 지금 왼쪽에 있는 코드는 피보나치 수열을 DP로 구하는 예제입니다. 그렇다면 오른쪽에 있는 그래프는 무엇을 의미할까요? 아마 금방 눈치채실 수 있을 것 같지만 예를 들어 0과 1에서 화살표가 출발해서 2로 이어지고 있는데, 이 화살표가 뜻하는 것은 출발한 위치의 값이 먼저 계산되어야 도착한 위치의 값을 계산할 수 있다는 의미입니다. 이렇게 되면 자연스럽게 이런 선후 관계를 만족하는 순서로 테이블을 채워야 합니다. 예를 들어 f[0], f[1], f[2]와 같은 순서로 값을 채우면 f[i]를 계산하기 위해 필요한 f[i-1], f[i-2]가 이미 계산되어 있기 때문에 문제가 없습니다. 반대로 f[5], f[4], ..., f[0] 순서로 채우려고 하면 필요한 값이 아직 계산되지 않은 경우가 생기기 때문에 문제가 생깁니다.

 

여기서 방향 그래프와 선후 관계라는 말이 나왔으니 자연스럽게 떠오르는 개념이 있을 겁니다. 바로 위상 정렬입니다. 이전에 위상 정렬 단원에서 배운 내용입니다. 결국 DP에서 테이블을 채운다는 것은 채워야 할 각 칸을 정점으로 보고 그 칸들 사이의 선후 관계를 그래프로 나타냈을 때 위상 정렬 순서에 따라 값을 채워야 한다는 뜻입니다. 쉬운 문제에서는 보통 0부터 차례로 채우는 방식처럼 이 흐름이 직관적으로 드러나기 때문에 이전에는 이렇게까지 깊게 설명드리지는 않았지만 오늘 배울 내용을 이해하는 데에는 지금 말씀드린 이 개념을 알고 있는 것이 도움이 됩니다.

 

 

또 하나 흥미로운 점은 DP의 상황을 그래프로 나타냈을 때 사이클이 생기면 어떻게 될까 하는 부분입니다. 예를 들어 f[0]을 채우기 위해 f[2]가 필요하고 f[2]를 채우기 위해 f[1]이 필요하며 f[1]을 채우기 위해 다시 f[0]이 필요하다면 서로 물고 물리게 되어 어떤 값도 먼저 계산할 수 없게 됩니다.

 

이처럼 셋 중 무엇도 먼저 구할 수 없는 상황이 되면 DP 풀이가 불가능해집니다. 그래서 DP의 테이블을 정의하고 점화식을 세운 뒤 그 구조를 그래프로 표현한다고 했을 때에는 사이클이 존재하면 안 됩니다. 다시 말해 방향 그래프이면서 사이클이 없는 DAG, 즉 Directed Acyclic Graph여야 합니다. 그리고 이 DAG 구조를 기반으로 위상 정렬 순서에 따라 테이블을 채워나가게 되는데 이때 진입 차수, 즉 indegree가 0인 정점들은 초기값이 됩니다. 앞서 본 피보나치 수열의 경우에서 f[0]과 f[1]이 초기값이었던 것과 같은 원리입니다.

 

 

네, 그러면 일단 앞 챕터에서 다뤘던 내용은 잠시 접어두고 2차원 DP 문제들부터 차례로 풀어보겠습니다. 총 네 개의 문제를 함께 볼 예정인데 비록 원래 DP 강의 안에서 같이 다루지는 못했지만 DP의 전형적인 구조를 잘 보여주는 좋은 문제들이기 때문에 만약 이전에 풀어보신 적이 있다면 복습 차원에서 다시 한번 생각해보시고 처음 보는 문제라면 DP가 늘 그렇듯 테이블을 어떻게 정의하고 점화식을 어떻게 세우는지를 중심으로 살펴보면 좋습니다.

 

먼저 볼 문제는 BOJ 9251번: LCS 문제입니다. 여기서 테이블을 잘 정의하고 점화식을 찾은 뒤 초기값을 설정하는 것이 이 문제를 DP로 해결하기 위해 우리가 해야 할 일입니다.

 

 

이제 테이블을 정의해야 하는데, 이번 단원이 2차원 DP이기 때문에 직관적으로 떠오르는 형태로 테이블을 먼저 정해보겠습니다. 이렇게 앞의 몇 개 값을 기준으로 테이블을 구성하는 방식은 이전에도 여러 번 사용했던 구조입니다. 물론 지금은 2차원이긴 하지만, 충분히 시도해볼 만한 형태입니다.

 

이제 이 테이블을 기반으로 점화식을 만들 수 있는지를 확인해야 합니다. 점화식을 만든다는 것은 지금 D[i][j]를 구할 때 이전에 계산된 값을 어떻게 활용할 수 있을지를 생각해보는 과정입니다. 이를 위해 첫 번째 문자열의 앞 i글자와 두 번째 문자열의 앞 j글자에서 LCS가 어떤 식으로 나올 수 있을지를 케이스별로 나누어 살펴보겠습니다.

 

 

케이스를 어떻게 나눌 수 있을지에 대해서는 LCS에서 마지막으로 일치하는 글자를 기준으로 생각해보면 됩니다. 예를 들어 문제에 주어진 예시인 ACAYKP와 CAPCAK의 경우 둘의 LCS는 ACAK이고, 마지막으로 일치하는 글자는 K입니다. 이제 이 글자가 각각의 문자열에서 어디에 위치해 있는지를 기준으로 생각해보겠습니다.

 

 

먼저 따져볼 수 있는 케이스는 두 문자열의 마지막 글자가 일치하는 경우입니다. 이 경우에는 이전의 테이블 값을 활용해서 D[i][j]를 계산할 수 있겠다는 느낌이 바로 옵니다. 마지막 글자를 떼어내고 나머지 부분에서 LCS를 구한 뒤, 그 결과에 마지막 글자를 하나 더해주면 되기 때문입니다. 여기서 말하는 나머지 부분은 첫 번째 문자열의 앞 i-1글자와 두 번째 문자열의 앞 j-1글자를 의미하므로, D[i-1][j-1]을 참조하면 됩니다. 따라서 이 경우에는 D[i][j]는 D[i-1][j-1]에 1을 더한 값이 됩니다.

 

 

그리고 두 번째 케이스는 첫 번째 문자열의 마지막 글자가 LCS에 포함되지 않는 경우입니다. 이때 두 번째 문자열의 마지막 글자는 LCS에 포함될 수도 있고 아닐 수도 있습니다. 이런 상황에서는 일치하는 다른 글자를 찾아야 하는 걸까 하는 생각이 들 수 있지만, 훨씬 더 간단하게 접근할 수 있는 방법이 있습니다. 이미 첫 번째 문자열의 마지막 글자가 LCS에 들어가지 않는다고 가정했기 때문에, 이 글자는 LCS를 구성하는 데 아무런 기여를 하지 못합니다. 그렇다면 그냥 이 글자를 제외한 나머지 부분들로만 LCS를 찾으면 됩니다. 즉, 첫 번째 문자열에서 마지막 글자를 뺀 부분과 두 번째 문자열 전체로 구한 LCS가 이 경우의 결과가 되며, 이는 D[i-1][j]로 나타낼 수 있습니다.

 

이제 이 과정을 따라오면서 LCS 문제가 어떻게 DP로 풀리는지 어느 정도 감이 잡히셨을 거라고 생각합니다.

 

 

그리고 마지막 케이스는 두 번째 문자열의 마지막 글자가 LCS에 포함되지 않는 경우입니다. 이 경우에는 앞서 설명한 흐름과 마찬가지로 해당 글자가 LCS에 기여하지 않기 때문에, 나머지 부분으로만 LCS를 구하면 됩니다. 따라서 이 경우에는 D[i][j-1]이 결과가 됩니다.

 

 

D[i][j]에서의 LCS를 생각해보면, 두 문자열의 마지막 글자가 모두 포함되는 경우이거나, 아니면 적어도 하나는 포함되지 않는 경우일 수밖에 없습니다.

 

따라서 이 세 가지 경우를 나누어 보면 모든 상황을 다 처리할 수 있게 됩니다. 그리고 첫 번째 케이스는 두 문자열의 마지막 글자가 같은 경우에만 고려하면 되므로, 최종적으로 D[i][j]는 각 경우의 값 중에서 최댓값을 취하는 방식으로 계산하면 됩니다.

 

 

테이블을 잘 정의하고 점화식도 잡아냈으니, 이제 초기값을 설정하고 테이블을 채우는 순서만 생각하면 됩니다. 일단 초기값은 D[0][...]과 D[...][0]의 값을 0으로 두는 것이 구현을 깔끔하고 편하게 해줍니다.

 

 

그리고 값을 채우는 순서는 1차원 배열에서 자기보다 작은 인덱스만 참고해서 D[0], D[1], D[2], ... 순으로 채우는 것과 비슷하게 생각할 수 있습니다. 지금도 D[i][j]의 값을 구할 때 D[i-1][j-1], D[i-1][j], D[i][j-1]를 참고하므로, 테이블을 보면 필요한 값들은 모두 나보다 왼쪽 혹은 위쪽에 위치한 값들만 필요하다는 것을 알 수 있습니다. 예를 들어 D[4][4]를 구한다고 할 때, 필요한 칸인 D[3][3], D[3][4], D[4][3]은 모두 왼쪽이나 위쪽에 위치한 값들입니다.

 

 

그러면 그냥 이렇게 D[1][1], D[1][2], D[1][3], D[1][4], D[2][1], ..., D[4][4] 순으로 채우면 자연스럽게 각 칸의 값을 구할 때 자신의 왼쪽 혹은 윗쪽에 있는 모든 칸이 채워져 있기 때문에 아무 문제 없이 답을 구할 수 있습니다. 이제 이것들을 종합해서 구현을 한 번 해보세요.

 

 

네, 구현은 크게 특이사항이 없습니다. 처음에 초기값을 D[0][...]과 D[...][0]에 넣어줘야 하지만 사실 D를 전역 변수로 잡으면 알아서 0이 들어갈 테니 괜찮습니다. 그리고 이 문제가 절대 쉬운 문제가 아닙니다. 보통 점화식이 수학적으로 비교적 당연하게 구해지면 문제가 쉽다고 생각할 수 있는데, LCS에서는 D[i][j]의 답의 형태에 따라 케이스를 나누어서 점화식을 이끌어내야 했기 때문에 정말 어려운 문제입니다. 이 문제는 DP를 배울 때 보통 꼭 짚고 가게 되는 유명한 문제여서 소개를 드리긴 했지만, 혹시 좀 헷갈리거나 너무 고통을 받으셨다면 어려운 게 당연하다는 걸로 위안을 삼으시길 바랍니다. 또 한편으로는 이 문제에서 점화식을 이끌어냈던 논리 전개 과정은 꼭 숙지하시기를 추천드립니다. (코드)

 

 

두 번째로 같이 풀어볼 문제는 BOJ 9084번: 동전 문제입니다. 사실 저희가 비슷한 문제를 풀어본 적이 있는데, 10원, 50원, 100원, 500원 이런 식으로 배수 관계가 성립할 때에는 그리디 알고리즘으로 쉽게 풀이가 가능합니다.

 

하지만 지금 문제처럼 동전들 사이에 배수 관계가 없다는 조건이 주어지면, 그리디 알고리즘으로는 해결할 수 없습니다. 한편, 지금 문제처럼 총 경우의 수를 구해야 하고, 심지어 그 경우의 수가 거의 2^31 – 1에 가까운 만큼 많아서 백트래킹 같은 방법으로 해결이 어려울 경우, DP로 풀 수 있는 경우가 많습니다.

 

 

일단 테이블을 먼저 정의해보면, D[i]를 i원을 만드는 방법의 수로 두어 보겠습니다. 그런 다음 점화식을 구해야 하는데, 제일 마지막에 더하는 수를 가지고 점화식을 세울 수 있겠다는 느낌이 오시나요? 사실 원래 DP 단원에서 비슷한 문제를 같이 풀어봤습니다. BOJ 9095번: 1, 2, 3 더하기 문제를 확인해 보세요.

 

 

9095번 문제의 느낌을 살려서 점화식을 구해본다면, N가지 동전의 가치가 c[1], c[2], ..., c[N]이라고 할 때 마지막에 추가되는 동전이 c[1]인지, c[2]인지, ..., c[N]인지를 가지고 지금 적힌 식과 같은 형태를 떠올릴 수 있습니다. 예를 들어 마지막에 추가되는 동전이 c[1]이라면 D[i-c[1]]로 i-c[1]원을 만들고 거기에 c[1] 동전을 더하는 방식으로 생각할 수 있습니다.

 

그리고 초기값을 바로 이어서 생각해 보면, 초기값을 어떻게 정해야 할지 막연할 수 있는데 이 문제에서는 D[0], 즉 0원을 만드는 경우의 수가 1개라고 정하는 것이 가장 깔끔합니다. 이 부분은 마치 2^0이 왜 1인 것과 비슷하게 직관적으로 잘 받아들여지지 않을 수 있습니다. 그러나 이런 방식으로 생각할 수 있습니다. j번째 동전 1개만을 써서 c[j]원을 만드는 경우가 D[c[j]]에 추가되어야 합니다. 이 경우는 i = D[c[j]]일 때 점화식에서 D[i-c[j]]에서 처리가 될 텐데, 이 값이 경우의 수 1가지로 D[i]에 더해지려면 D[0] = 1인 것이 자연스럽습니다.

 

 

그러면 이제 바로 코딩에 들어가면 되는 것 아닌가? 라는 생각을 하기 전에, 작은 테스트 케이스를 직접 한번 계산해보겠습니다. N = 2이고 동전이 1원, 2원일 때 D[3]까지 구해보면, 여기 적힌 것과 같이 계산되고 D[3] = 3이 나옵니다. 그런데 사실 3원을 만드는 방법은 1원짜리 3개 혹은 1원 1개와 2원 1개를 쓰는 방법 이 2가지밖에 없습니다. 어? 뭔가 좀 이상한 점이 있죠? 분명 D[3]은 2여야 할 텐데, 이게 어디서부터 잘못된 걸까요?

 

 

각 D[i] 값이 어떤 경우들을 포함하는지를 따져보면, 무엇이 잘못되었는지가 쉽게 보입니다. 일단 D[1]부터 살펴보면, D[0]부터 온 값은 1원짜리 동전을 1개 쓰는 경우입니다.

 

 

그리고 D[2]를 보면 D[2] = D[1] + D[0]에서 D[1]에 대응되는 경우는 1원을 만드는 방법에다가 1원짜리 동전을 추가한거니 1+1이고

 

 

D[0]에 대응되는 경우는 0원을 만드는 방법에 2원짜리 동전을 추가한 것이므로 2가 대응됩니다. 이렇게 1 + 1과 2 두 가지 방법이 존재하니, D[2] = 2가 맞습니다.

 

 

다음으로 D[3] = D[2] + D[1]이라는 식에서, D[2]는 2원을 만드는 방법에 1원짜리 동전을 추가하는 경우이므로 1원짜리 3개와 2원 1개, 1원 1개를 쓰는 방법 이 2가지에 해당합니다.

 

 

그리고 D[1]은 1원을 만드는 방법에 2원짜리 동전을 추가하는 경우여서 1원짜리 1개와 2원짜리 1개를 쓰는 경우를 D[3]에 더하겠다는 것인데, 이제 명확하게 현재의 DP 식이 틀린 이유가 무엇인지 감이 오실 겁니다. 이 지점이 사실 이 문제와 9095번 문제의 차이점이기도 합니다. 9095번 문제에서는 1 + 2와 2 + 1을 다른 경우로 분류하지만 이 문제에서는 1 + 2와 2 + 1은 모두 1원짜리 1개와 2원짜리 1개를 쓰는 경우로 취급됩니다. 그래서 현재의 DP 식이 틀린 이유는 이 식대로 진행하면 1 + 2와 2 + 1을 다른 경우로 취급하게 되기 때문입니다. 그러므로 다시 초심으로 돌아가서 테이블과 점화식을 새로 정해봐야 할 필요가 있습니다.

 

 

기존의 테이블과 식에서는 동전을 추가하는 순서가 중구난방이었습니다. 예를 들어 1원짜리도 추가했다가 2원짜리도 추가했다가 이런 식으로 하면 앞서 본 것처럼 1+2와 2+1을 자칫 다른 경우로 세버릴 수 있습니다. 이를 해결하기 위한 좋은 방법은 첫 번째 동전만을 이용해 0원부터 M원까지를 채운 후, 그다음 두 번째 동전을 추가하는 식으로 동전을 순차적으로 적용하는 방법입니다. 이렇게 하면 2+1과 같은 경우는 경우의 수에 포함되지 않게 됩니다. 즉 1원을 쓴 후에 2원을 써야 하므로 동전 사용 순서를 강제하게 되어 같은 방법을 여러 경우로 세는 것을 방지할 수 있습니다. 그래서 테이블을 1차원으로 만드는 대신, "i번째 동전까지 썼을 때"라는 조건을 추가하여 2차원 테이블로 만들게 됩니다.

 

 

다음으로 식을 찾아야 하는데, i번째 동전을 몇 개 썼냐를 가지고 이렇게 접근할 수 있습니다. i번째 동전을 사용한 개수를 지정한 후, 나머지 금액은 i-1번째 동전까지만으로 해결해야 하므로 자연스럽게 식을 도출할 수 있습니다. 예를 들어 i번째 동전을 1개 썼다면 j - c[i]원을 i-1번째 동전까지만으로 채워야 하기 때문에 식은 D[i - 1][j - c[i]]가 됩니다. 이 방식으로 점화식을 유도할 수 있습니다.

 

 

그리고 여기서 한 단계 더 발전시켜서 식을 더 간단하게 줄일 수 있는데, i번째 동전을 쓰는지 안 쓰는지로만 나누면 됩니다. i번째 동전을 안 쓴 경우는 당연히 D[i-1][j]이고, 1개 이상 쓴 경우는 i번째 동전을 먼저 1개 써서 전체 j원 중 c[i]원을 해결하고, 나머지 j - c[i]원을 채울 때 1번부터 i-1번째 동전까지를 쓰는 게 아니라 1번부터 i번째 동전까지 모두 쓸 수 있습니다.

 

따라서 이전처럼 i번째 동전을 1개 썼다, 2개 썼다 이렇게 경우를 나눌 필요 없이, 1개 이상 쓴 경우는 D[i][j - c[i]]로 표현할 수 있습니다. 이렇게 되면 c[i]가 1일 때 아까는 j+1개의 값을 더해야 D[i][j]를 구할 수 있었지만, 지금은 j와 c[i]의 값에 관계없이 2칸만 더하면 되므로 시간 복잡도를 더 효율적으로 줄일 수 있습니다.

 

 

여기서 한 가지 분명히 말씀드리고 싶은 점은, 이 점화식이 조금 어려운 건 맞습니다. 직관적으로 식이 잘 안 보일 수도 있고, 심지어 앞의 설명을 듣고도 이게 맞나 하고 잘 납득이 안 가는 게 매우 정상입니다. 이해를 돕기 위해 점화식이 맞는지 헷갈릴 때 확인할 수 있는 방법을 알려드리면, D[i][j]에 대응되는 경우의 수 중에서 해당 점화식이 혹시 빼먹은 케이스가 있는지, 아니면 점화식에서 중복으로 센 게 있는지를 고민해볼 수 있습니다. 그렇게 반례를 만들려고 고민하다 보면, "아, 정말로 지금의 식이 D[i][j]에 대한 모든 경우를 다 포함하는구나" 하고 납득할 수 있을 것입니다.

 

 

초기값을 설정하는 방법은 간단합니다. 각 i에서 0원을 만드는 방법은 1가지로 정의하면 됩니다. 즉, D[i][0] = 1입니다. 그리고 테이블을 채울 때는 LCS 문제처럼 i 순으로, 그리고 각 i에서 j 순으로 채우면 됩니다. 이 방법으로 구현을 진행하면 됩니다.

 

 

구현은 적당히 잘 하시면 되고, 점화식 자체는 d[i][j] = d[i-1][j] + d[i][j-coin[i]]입니다. 하지만 실제로 코딩할 때는 22~27번째 줄에서 작성한 것처럼 인덱스가 음수로 가지 않도록 주의해야 합니다. 또한 이 문제와 관련하여 한 가지 더 말씀드릴 점이 있는데, 다른 사람들의 풀이를 보다 보면 2차원 배열을 사용하지 않고 1차원 배열로 풀어낸 코드를 볼 수 있습니다. 제 코드와 동일한 점화식을 사용하되, d를 d[22][10002] 대신 d[10002]로 사용해도 해결이 가능한데, 이 기법을 토글링이라고 합니다. 토글링을 알면 당연히 유용하지만, 이 기법은 공간 복잡도를 줄일 수는 있지만 시간 복잡도는 그대로이고, 일반적으로 공간 복잡도보다 시간 복잡도가 더 중요한 경우가 많기 때문에 이번 강의에서는 토글링에 대해서 별도로 설명하지 않습니다.

 

혹시 풀이를 찾아보다가 1차원 배열을 사용한 코드를 보고 이건 어떻게 한 거지? 라는 의문이 들 수 있기 때문에 언급한 것이며, 점화식 자체는 동일하기 때문에 굳이 신경 쓸 필요는 없습니다. (코드)

 

 

두 번째 문제는 BOJ 12865번: 평범한 배낭 문제입니다. 그리디 단원에서 이 문제를 그리디 알고리즘으로 풀면 반례가 있다는 내용을 소개한 적이 있는데, 이 문제는 다이나믹 프로그래밍을 통해 해결할 수 있습니다. 여기서 이 문제의 느낌이 앞의 문제와 비슷하다는 생각을 하셨다면, 상당히 센스가 있다고 할 수 있겠습니다. 혹시 그런 느낌을 받으셨나요?

 

이 문제에서도 단순히 직관적으로 d[j]를 무게가 j일 때의 최대 가치라고 정의한다고 해도, 식을 세울 방법이 쉽게 떠오르지 않습니다. i번째 물건의 무게와 가치를 각각 W[i], V[i]로 두었을 때, d[j] = d[j - W[i]] + V[i]와 같은 형태로, i번째 물건을 선택했을 때의 상황을 식으로 표현할 수 있을 것 같지만 이 식을 바탕으로 d[0]부터 채워나가려고 하면 각 물건은 1개만 있다는 조건을 추가할 방법이 없습니다. 이 상황은 저번 문제에서의 상황과 유사하고 해결책도 비슷합니다. 테이블을 2차원으로 두고 i번째 물건까지 고려했을 때의 최대 가치를 관리하는 방식으로 문제를 풀 수 있습니다.

 

 

따라서 테이블을 D[i][j] = i번째 물건까지 고려했을 때, 무게 j로 만들 수 있는 최대 가치로 정의합니다. 그다음 점화식을 찾아 초기값을 설정하고 순서를 정해야 하는데, 앞서 푼 문제의 느낌을 살려서 직접 시도해보는 것을 권장합니다. 구현까지 한번 도전해보셔도 좋습니다. 저는 다음 슬라이드에서 설명을 계속 이어가겠습니다.

 

 

점화식을 보면 D[i][j]를 구할 때 i번째 물건을 사용한 경우와 사용하지 않은 경우로 나눌 수 있습니다. i번째 물건을 사용한 경우, 즉 i-1번째 물건까지 고려했을 때 j-W[i]의 무게를 만들 수 있는 최대 가치에 i번째 물건의 가치를 더한 값이 됩니다. 이때 가치는 D[i-1][j-W[i]] + V[i]가 됩니다. 반대로 i번째 물건을 사용하지 않았다면, 그저 D[i-1][j]를 가져오면 됩니다.

 

초기값은 각 i에 대해 D[i][0] = 0으로 두면 되고, D[i][j]를 채울 때 필요한 값들이 모두 왼쪽 혹은 위쪽에 위치하므로 테이블을 채우는 순서는 특별히 고민할 필요 없이 이중 for문을 돌며 차례대로 채우면 됩니다.

 

 

역시 마찬가지로 배열 인덱스가 음수로 가지 않게 주의해서 구현을 하면 되고, 전역 변수를 사용하면 0이 기본값으로 들어간다는 점을 인지한 상태로 코드를 보면 이해에 도움이 될 것입니다. (코드)

 

 

마지막으로 다룰 문제는 BOJ 1915번: 가장 큰 정사각형입니다. 이 문제는 지금까지 다룬 문제들과는 약간 다른 성격을 가지고 있어서 만약 비슷한 문제를 본 적이 없다면 풀이 방법을 쉽게 떠올리기 어려울 수 있습니다. 이 문제에서는 풀이 접근 방식에 너무 매몰될 필요가 없고 그냥 풀이를 바로 확인한 다음 비슷한 문제가 나왔을 때 비슷한 느낌으로 접근을 해야겠다 정도의 깨달음을 얻고 가면 충분합니다.

 

 

그래서 바로 테이블의 정의를 보면 D[i][j]를 위에서 언급한 것처럼 정의합니다. 이해를 돕기 위해 예시를 하나 가져왔습니다. 예를 들어 D[3][3]을 생각하면 크기가 3인 정사각형을 만들 수 있으니 D[3][3] = 3이 됩니다. 나머지 값들도 눈으로 한번 쓱 보면 그렇게 어렵지 않게 값이 맞는지 확인할 수 있을 겁니다. 왜 테이블을 이런 형태로 정의하는지 궁금할 수 있지만 앞에서 말한 것처럼 그 발상 과정을 이해하려고 하기보다는, 그냥 테이블을 이렇게 잡으니 문제가 풀리더라는 점을 받아들이고 일단 넘어가는 것이 좋습니다.

 

 

테이블을 정했으니 이제 점화식을 잘 찾기만 하면 끝인데 그게 참 어렵습니다. 이 문제에서 점화식을 찾으려면 LCS 문제와 약간 비슷한 느낌으로 D[i][j]가 특정 값일 때의 형태를 생각하면서 어떻게 다른 테이블의 값을 이용할 수 있을지를 고민해야 합니다. 물론 말이 쉽지, 이렇게 말하면 무슨 소린지 하나도 이해가 안 갈 수도 있습니다. 그래서 발상을 조금 도와드리기 위해 그림을 하나 준비했습니다.

 

 

D 테이블에서 어느 칸 (i, j)의 값이 k라고 가정해봅시다. 그러면 그 칸을 오른쪽 아래 모서리로 두는 길이가 k인 정사각형이 존재한다는 뜻입니다. 즉, D[i][j]의 값은 해당 위치에서 끝나는 정사각형의 크기를 나타내는 것이죠.

 

 

D 테이블에서 어느 칸 (i, j)의 값이 k라면 그 칸을 오른쪽 아래 모서리로 두는 길이가 k인 정사각형이 있다는 뜻입니다. 주황색으로 표시한 영역은 D[i][j-1]의 값과 관련이 있습니다. 주황색 영역의 오른쪽 아래가 (i, j-1)이기 때문입니다. D[i][j] = k라면 D[i][j-1]은 최소 k-1이어야 합니다. 값이 k-1보다 더 클 수도 있다는 점을 꼭 유념하고,  다음 그림을 보겠습니다.

 

 

다음으로는 D[i-1][j]와 관련 있는 영역을 가져왔습니다. 같은 논리로 따지면 D[i-1][j]도 k-1 이상이어야 합니다.

 

 

마지막으로 D[i-1][j-1]도 마찬가지 논리로 k-1 이상입니다.

 

 

지금까지 얘기한 내용을 한데 모아보면, D[i][j] = k일 때 D[i][j-1], D[i-1][j], D[i-1][j-1] 이 3개 칸의 값은 반드시 k-1 이상입니다. 그럼 여기서 점화식을 확정짓기 위해 추가로 생각해봐야 하는 것은 D[i][j-1], D[i-1][j], D[i-1][j-1]의 최솟값이 k-1일 때 D[i][j]는 k가 되는지 여부입니다. 머릿속으로 상황을 생각해보면 그렇게 어렵지 않게 맞다는 걸 알 수 있습니다. 일단 (i, j) 칸이 1일 때 세 노란색 영역을 합치면 (i, j)를 오른쪽 아래로 두는 크기 k짜리 정사각형이 다 채워지게 됩니다. 그러니까 D[i][j]는 k 이상인 게 맞고, 여기서 추가로 값을 확정하려면 D[i][j]가 k보다 클 가능성은 없다는 것을 봐야하는데 이건 직관적으로 이해할 수 있습니다.

 

 

예를 들어 D[i][j]가 k보다 커서 (i, j)를 오른쪽 아래로 하는 크기 k+1의 정사각형이 있다고 가정해 봅시다. 그러면 그림에서 볼 수 있듯이 D[i][j-1], D[i-1][j], D[i-1][j-1]이 모두 k 이상이므로, D[i][j-1], D[i-1][j], D[i-1][j-1]의 최솟값은 k-1이라는 처음의 가정과 모순이 발생하게 됩니다. 따라서 D[i][j]는 k보다 클 수 없고, 앞에서 확인한 대로 D[i][j]가 k 이상인 것은 맞으므로 종합적으로 보면 D[i][j-1], D[i-1][j], D[i-1][j-1]의 최솟값이 k-1일 때 D[i][j]가 k라는 결론을 얻을 수 있습니다. 이를 바탕으로 점화식을 세울 수 있습니다.

 

 

식은 이렇게 나눌 수 있습니다. 우선 (i, j) 칸이 0인지 1인지에 따라 다르게 처리합니다. 만약 (i, j) 칸이 0이면 고민할 필요 없이 바로 D[i][j]를 0으로 두면 됩니다. 반면 (i, j) 칸이 1이라면 D[i-1][j], D[i][j-1], D[i-1][j-1] 이 세 칸의 값을 확인하고 그 중 최솟값을 구한 후, 그 값에 1을 더한 값이 D[i][j]가 됩니다.

 

 

다음으로 초기값을 설정하는 데 있어 특별히 어려운 부분은 없습니다. D[i-1][j], D[i-1][j-1], D[i][j-1] 칸들이 잘 정의되지 않는 가장 윗쪽과 왼쪽의 칸들에 대해서 미리 값을 채워주면 됩니다. 테이블을 채우는 순서도 일반적인 방식대로, 즉 위에서 아래로 / 왼쪽에서 오른쪽으로 채워주면 됩니다. 이제 구현을 진행하면 됩니다.

 

 

이 문제가 DP 식을 찾아내는 것이 어려운 건 맞지만, 구현은 별다를 것이 없습니다. 앞에서 살펴본 내용을 그대로 코드로 옮기면 됩니다. 이 문제를 통해 테이블을 정의하는 방법을 새롭게 배운 셈인데, 사실 이 방법이 완전히 새로운 것은 아닙니다. BOJ 8958번: OX 퀴즈와 비슷한 느낌으로 "OOXXOOXOO"라는 문자열이 주어졌을 때 연속된 O의 최대 길이를 구하는 문제를 풀 때, 해당 글자가 끝나는 연속된 O의 최대 길이를 구하는 방법으로 점화식을 세울 수 있습니다. 이 문제는 그 방식을 2차원 배열로 확장한 문제입니다. 앞으로 비슷한 문제를 만나면 이 문제에서 테이블과 점화식이 어떻게 정의되었는지 떠올려보는걸 추천드립니다.

 

 

네, 상당히 많은걸 한 것 같은데 이제 2차원 DP 챕터 하나가 끝났네요. 계속 달려봅시다. 이번 챕터는 top-down DP에 대한 내용입니다. DP를 풀 때는 테이블을 정의하고, 점화식을 찾고, 초기값을 정하는 과정이 필요합니다. 이 세 가지는 초반 강의에서 언급된 내용인데, 여기에 하나를 더 추가하자면 테이블을 채우는 순서도 잘 정해야 한다는 점입니다.

 

기본적으로 1차원 DP에서는 거의 다 가장 작은 인덱스부터 혹은 가장 큰 인덱스부터 채우면 되기 때문에 크게 복잡할 게 없었지만, 2차원 DP에서는 초기값을 정하고 테이블을 채우는 순서를 정하는 것이 조금 헷갈릴 수 있습니다. 이 점이 bottom-up 방식의 단점입니다. 앞서 살펴본 DAG에서 간선끼리의 선후 관계에 문제가 없도록 채우는 순서를 신중하게 설정해야 합니다. 만약 채우는 순서를 어렵지 않게 정할 수 있다면 계속해서 bottom-up 방식으로 해결할 수 있습니다. 반면 테이블과 점화식은 잘 보이지만 채우는 순서가 까다롭다면 top-down 방식을 고려해볼 수 있습니다.

 

 

top-down 방식은 이름에서 유추할 수 있듯이, 위에서부터 시작해 내려오는 방식을 의미합니다. DP에서 이것이 어떤 것을 의미하는지 이해하기 위해 피보나치 수열을 예로 들어보겠습니다.

 

 

피보나치 수열을 bottom-up 방식으로 구할 때에는 f[0], f[1]이 초기값이 되고, 그 후 f[2]부터 차례대로 값을 계산하여 넣습니다. 즉, bottom-up 방식에서는 밑에서부터 값을 하나씩 채워가며 위로 올라갑니다. 반면, top-down 방식으로 해결할 때의 코드는 어떻게 작성되는지 살펴보겠습니다.

 

 

 

당연히 같은 식과 테이블을 사용해 DP를 푼다면, bottom-up 방식이든 top-down 방식이든 시간 복잡도는 동일합니다. 예를 들어, 8번째 줄에서처럼 값을 구하는 과정은 각 테이블의 칸에 대해 한 번씩만 이루어집니다. bottom-up에서는 테이블을 차례대로 채워가며 값을 계산하고, top-down에서는 한 번 값이 들어가면 그 후에는 재귀 호출이 발생해도 이미 계산된 값이 반환되기 때문에 다시 계산하지 않습니다.

 

따라서 시간 복잡도는 두 방식 모두 동일하고 기본적으로 그냥 둘의 차이는 구현 방식의 차이인건데, 각 방식의 장단점을 살펴보겠습니다.

 

 

먼저 시간 복잡도는 이전에 설명한 것처럼 두 방식이 동일하지만 실제 실행 시간에서는 bottom-up 방식이 더 빠릅니다. 왜냐하면 bottom-up은 단순히 반복문을 통해 테이블을 차례대로 채워가기 때문에 함수 호출이 없어 효율적입니다. 반면, top-down 방식은 재귀 호출을 사용하기 때문에 반복문보다 무거운 함수 호출 연산이 발생하게 됩니다. 하지만 top-down 방식이 느리다고 해서 시간 초과가 발생할 정도로 문제가 생기지는 않기 때문에, 꼭 top-down을 사용해야 하는 상황이 아니라면 bottom-up 방식으로 문제를 푸는 것이 더 효율적입니다. 개인적인 취향에 따라 top-down을 써도 크게 문제가 되지 않지만, 테이블을 채우는 순서가 어렵지 않다면 bottom-up 방식을 사용하는 것이 더 유리합니다.

 

그리고 top-down 방식이 효과적인 상황은 테이블을 일부만 채워야 하거나 테이블을 채우는 순서가 복잡할 때입니다. 이러한 경우에는 top-down 방식이 더 유용할 수 있고 각각이 어떤 상황인지는 직접 문제를 풀면서 확인해보겠습니다.

 

 

BOJ 1351번: 무한 수열 문제를 살펴보면 테이블과 초기값, 그리고 점화식까지 모두 제공된 것을 확인할 수 있습니다. 하지만 이 문제를 bottom-up 방식으로 해결하기는 어렵습니다. A[0], A[1]처럼 순차적으로 값을 채워나가기에는 N의 크기가 무려 10^12이기 때문입니다.

 

 

그런데 A[0]부터 A[N]까지 모든 값을 실제로 계산할 필요는 없습니다. 예제 1에서 주어진 N, P, Q 값을 기준으로 A[N]을 구하는 데 필요한 값들만 따로 추려 그래프로 나타내보면, A[4], A[5], A[6]과 같은 값들은 굳이 계산하지 않아도 된다는 것을 확인할 수 있습니다. 또한 주어진 N에 대해 top-down 방식으로 계산을 진행하면 필요한 값들만 재귀적으로 호출하면서 계산이 이루어지게 됩니다. 그리고 공간을 절약하기 위해 A를 배열로 선언하는 대신 맵을 사용하는 것이 효과적입니다. 이제 바로 구현을 진행해보겠습니다.

 

 

구현 자체는 매우 간단합니다. 테이블과 점화식을 정한 뒤 재귀적으로 함수를 작성하면 A[N]을 구하기 위해 필요한 값들을 따라가며 계산이 이루어집니다. 결국 재귀 호출을 거치다 보면 초기값인 go(0)에 도달하게 되고 이 값이 재귀의 기본 조건, 즉 base condition 역할을 해서 결과를 올바르게 도출할 수 있습니다. 이처럼 테이블의 모든 값을 채우는 것이 아니라 일부 값만 필요할 경우에는 top-down 방식을 사용하면 자연스럽게 필요한 값만 계산하게 됩니다.

또한 구현의 디테일을 또 한 하나 짚어보자면, map a에서 이전에 키 k가 존재하지 않았을 때 a[k]를 호출하면 기본값으로 0이 설정된다는 특성을 이용해서 아홉 번째 줄에서는 a[k]가 0이 아닌 경우 이미 해당 값이 계산된 것으로 판단하고 처리를 진행하였습니다.

 

 

두 번째로 확인해볼 부분은, 테이블을 채우는 순서가 복잡한 경우에 대한 예시입니다. BOJ 1937번: 욕심쟁이 판다 문제를 살펴보면, 테이블의 정의나 점화식 자체는 비교적 쉽게 유추할 수 있습니다. D[i][j]를 (i, j) 칸에서 출발했을 때 이동할 수 있는 칸의 수라고 정의하면 단순히 상하좌우를 확인하면서 대나무 양이 더 많은 방향으로 이동한다고 생각하면 되니 점화식도 그 방향의 D 값에 1을 더해주는 방식으로 쉽게 구성할 수 있습니다.

하지만 여기서 중요한 점은, 테이블을 어떤 순서로 채워야 하는가입니다. 지금까지는 대부분 2중 반복문을 사용하여 D[0][0]부터 순서대로 값을 채워나가면 문제가 없었습니다. 그러나 이 문제에서는 상황이 다릅니다. 문제에서 제시된 예제만 보더라도, D[0][1]의 값을 구하려면 D[0][0], D[0][2], D[1][1]이 이미 계산되어 있어야 합니다. 이처럼 특정 위치의 값을 구하기 위해서는 그보다 앞서 다른 위치들이 먼저 계산되어야 하므로, 테이블을 채우는 순서가 복잡해집니다.

 

 

이러한 상황에서 테이블을 어떤 순서로 채워야 할지를 파악하기 위해 D[a][b]를 구할 때 D[c][d]의 값이 필요하다면, (c, d)에서 (a, b)로 향하는 간선을 그어 그래프를 구성해보았습니다. 예를 들어 D[0][1]을 계산하기 위해 D[0][0]이 필요하다면, (0, 0)에서 (0, 1)로 가는 간선을 하나 추가하는 식입니다. 그런데 이렇게 봐도 눈에 잘 안들어오는건 매한가지입니다.

 

 

그래서 조금 더 알아보기 쉽게 그래프 상에서 각 위치를 조정해보았습니다. 물론 이 방식도 완전히 만족스럽지는 않지만 현 시점에서는 이 정도가 최선인 것 같습니다. 이때 이 문제를 동적 계획법으로 해결하려면 해당 그래프에 사이클이 없어야 하는데, 다행히 간선이 항상 값이 더 큰 정점에서 더 작은 정점으로만 연결되기 때문에 사이클이 생길 가능성은 없습니다.

그리고 14, 15, 12, 16, 13과 같은 정점들은 indegree가 0입니다. 이는 인접한 칸 중 자신보다 대나무의 양이 많은 칸이 없다는 뜻이므로 해당 위치의 D 값은 곧바로 1로 정해질 수 있습니다. 이런 값들이 초기값이 되고 이후 그래프에서 위상 정렬된 순서대로 동적 계획을 진행해나가면 문제를 해결할 수 있습니다. 이것이 bottom-up 방식의 접근입니다.

만약 구현을 더 간단하게 하고 싶다면 각 칸을 대나무의 양을 기준으로 정렬한 후 내림차순으로 테이블을 채워나가는 방식도 사용할 수 있습니다. 앞서 설명했듯이 간선은 반드시 값이 더 큰 정점에서 더 작은 정점으로 연결되기 때문에, 대나무가 많은 칸부터 차례로 값을 계산해도 올바른 결과를 얻을 수 있습니다.

이처럼 문제는 해결 가능하지만 어쨌든 테이블을 채우는 순서가 단순하지 않다는 점은 여전히 남아 있습니다. 어느 정도 고민을 통해 적절히 순서를 정해줘야 하고, 위상 정렬 방식은 구현이 다소 복잡한 반면 정렬을 사용하는 방식은 구현은 간단하지만 시간 복잡도에 불필요한 log N이 추가된다는 단점이 있습니다.

이제 이 문제를 top-down 방식으로 접근하면 어떻게 될지 살펴보겠습니다.

 

 

top-down 방식에서는 재귀적인 형태로 코드를 작성해두고, 어떤 값을 호출하면 그에 필요한 값들을 자동으로 호출하면서 base condition까지 내려가게 됩니다. 여기서 정말 흥미로운 점은, 호출 순서에 대해 전혀 신경 쓸 필요가 없다는 사실입니다.

이게 무슨 의미인지 함께 살펴보겠습니다. 앞서 top-down 방식으로 문제를 구현했을 때의 흐름대로 코드가 구현되어 있다고 생각하고 보면 되는데, 만약 아직 그 감이 잘 잡히지 않는다면 언제나처럼 이 문제에 대한 코드를 제가 뒤쪽에 작성해두었으니 그것을 함께 보면서 설명을 이해해보셔도 좋습니다.

 

 

go(i, j) 함수가 D[i][j] 값을 구하는 함수라고 하고, 그냥 편하게 우리가 익숙한 순서대로 go(0, 0), go(0, 1)처럼 순서대로 호출한다고 가정해보겠습니다. 먼저 go(0, 0)을 호출하면, 대나무 양이 14인 칸의 D 값을 구하려는 상황이 됩니다. 그래프로도 확인할 수 있듯이 D[0][0]을 계산하기 위해 미리 구해져 있어야 할 값이 따로 없습니다. 따라서 이 경우 D[0][0]은 1이라는 사실을 바로 알 수 있습니다. 이렇게 계산이 완료된 정점은 시각적으로 구분하기 위해 주황색으로 표시하겠습니다.

 

 

다음으로 go(0, 1)을 호출하면, 대나무 양이 9인 정점에 해당하게 됩니다. 이 값을 구하려면 D[0][0], D[0][2], D[1][1]의 값이 모두 필요합니다. 그러면 구조적으로 자연스럽게 go(0, 0), go(0, 2), go(1, 1) 세 함수가 모두 호출됩니다.

이 중 go(0, 0)은 이미 D[0][0]이 계산되어 있기 때문에 해당 값을 그대로 반환하게 됩니다. 그리고 go(0, 2)의 경우에도 D[0][2]가 1이므로 바로 계산이 끝납니다. go(1, 1)을 호출하면, 이 함수는 내부에서 다시 go(1, 2)를 호출하게 됩니다.

이러한 호출 과정을 계속 따라가다 보면, 결국 9인 정점에 도달할 수 있는 모든 경로에 있는 정점들의 값이 전부 계산되게 됩니다. 함수 호출 도중 그 칸들을 자동으로 호출하면서 D 값을 하나씩 채워나가기 때문입니다.

결과적으로 이미 계산되어 있던 14에 더해, 9, 11, 15, 12의 값이 새롭게 계산되어 저장됩니다.

 

 

다음으로 go(0, 2)는 이미 값이 있으니 별 일이 안생기고

 

 

go(0, 3)은 10인 정점을 계산할 때 12가 필요한데 이미 계산되어 있으니 자연스럽게 또 D[0][3]을 구할 수 있습니다.

 

 

다음은 go(1, 0)을 호출하는 경우입니다. 이 함수가 D[1][0]을 계산하려면 D[0][0], D[1][1], D[2][0]의 값이 필요합니다. 그런데 D[0][0]과 D[1][1]은 이미 앞서 계산이 완료된 상태이므로 go(0, 0)과 go(1, 1)은 더 이상 깊이 들어가지 않고 바로 해당 값을 반환하게 됩니다.

이제 남은 go(2, 0)을 호출하면, 이 함수는 다시 D[2][1] 값을 활용해서 D[2][0]을 계산하게 됩니다. 이 흐름대로 계산이 진행되면 결국 새롭게 1과 7에 해당하는 칸의 값이 채워지게 됩니다.

 

 

이 정도 보여드렸다면 대충 눈치를 챘을 것이라고 생각합니다. 특정 정점을 호출하면 해당 정점을 조상으로 두는 아래 정점들의 값도 자연스럽게 구해집니다. 그리고 top-down에서 가장 중요한 메모이제이션 덕분에 이미 값을 구한 정점에 대해 다시 계산하는 일은 절대 발생하지 않습니다. 그래서 DP 테이블을 채우고 싶은 입장에서는 이 그래프가 어떻게 생겼는지 전혀 신경 쓸 필요 없이 go(0, 0)부터 go(3, 3)까지 모두 한 번씩 호출만 해주면 테이블이 자동으로 채워집니다.

다시 한 번 강조하지만 각 칸에서 상하좌우 칸을 살펴보고 최대값을 구하는 등의 DP 식을 계산하는 과정은 단 한 번만 발생하므로 시간 복잡도는 O(N^2)입니다. 아마 시간 복잡도에서 혼동이 있을 수 있는데, BOJ 1926번: 그림 문제에서 2중 for문을 돌면서 방문 표시를 남기고 현재 방문하지 않은 점을 모두 BFS의 시작점으로 삼는 방식도 전체 시간 복잡도는 O(NM)였던 것과 상황이 똑같습니다.

즉, BFS에서는 방문 표시를 통해, DP에서는 메모이제이션을 통해 중복 계산을 막아서 각 칸마다 DP 식을 한 번만 계산하는 구조입니다. 이 점을 이해하시면 됩니다. 이제 바로 구현을 시작하겠습니다.

 

애매하게 길어서 한 장에 다 담기 어려운 부분이 있겠지만, 일단 go 함수까지만 보면 특별히 설명이 필요한 부분은 없습니다. 그냥 말한 그대로입니다. (코드)

 

 

그리고 main 함수도 그냥 자연스럽게 go를 go(0, 0)부터 go(n-1, n-1)까지 한 번씩 다 호출하고 max를 구하면 그게 답입니다. 이렇게 채우는 순서가 복잡할 때는 top-down을 이용하면 순서를 내가 신경 쓸 필요 없이 재귀적으로 알아서 해결되는 예시를 살펴봤습니다.

 

 

이제 남은 것은 트리 DP와 위상 정렬 DP인데, 미리 살짝 스포를 하자면 트리나 위상 정렬이나 그것을 그래프로 표현하면 DAG(Directed Acyclic Graph)가 되기 때문에 자연스럽게 그 안에서 DP가 잘 정의됩니다. 그래서 개념 자체는 그렇게 어렵지 않습니다. 물론 이를 응용할 여지는 무궁무진하지만, 이번 강의에서는 트리 DP 혹은 위상 정렬 DP가 어떤 것인지 알 수 있도록 대표적인 문제 한 가지를 다룰 예정입니다.

먼저 트리 DP부터 보면, 트리 단원에서는 트리 DP를 깊게 다루지 않았습니다. 그러나 문제집의 응용 문제에는 몇 가지를 포함시켰습니다. 기본적으로 트리 DP는 트리에서 DP를 하는 문제입니다. 트리 DP의 느낌을 잡아보려면 주어진 트리에서 각 정점에 가중치가 있고, 이 정점이 속한 서브트리에서 가중치 합이 최대인 서브트리를 찾는 문제를 생각해볼 수 있습니다.

이 예시에서는 3이 루트인 트리가 가중치 합이 3+4=7로 최대입니다. 그럼 모든 정점에 대해 자기 자신과 자기 자식들의 가중치 합을 구해서 그 중 최대를 찾으면 되겠지만, 이렇게 구현하면 시간 복잡도가 얼마나 될까요?

 

 

만약 진짜 정직하게 각 노드마다 거기서 BFS나 DFS를 시작해서 그 노드를 루트로 하는 서브트리를 다 순회하는 전략을 취한다면, 정점이 N개일 때 시간 복잡도는 O(N^2)가 될 것입니다. 왜냐하면 각 정점마다 최대 N번 순회를 해야 하기 때문입니다. 그런데 지금 이 방법은 최적화할 여지가 너무 뻔하게 보입니다. 예를 들어, 루트가 2인 서브트리를 순회해서 (2, -9, 5)의 합이 -2라는 걸 이미 알았다면 루트가 0인 서브트리를 계산할 때 굳이 (2, -9, 5)를 다시 순회할 필요는 없습니다. 그냥 바로 -2라는 값만 가져오면 되기 때문입니다.

D[i]를 가중치가 i인 정점에 대해 서브트리의 가중치의 합이라고 한다면, D[1]을 구하기 위해 모든 정점을 다 보는 게 아니라, D[1] = 1 + D[3] + D[-7] + D[0] 이런 방식으로 계산할 수 있습니다. 이렇게 하면 각 D 값을 구할 때 자기 자식들의 D 값만 가져오면 되고, 다른 관점에서 보면 각 D 값은 자신의 부모에게만 딱 한 번 더해지니까 전체적으로 시간 복잡도는 O(N)이 됩니다. 이처럼 트리에서 메모이제이션을 활용하면 시간 복잡도를 줄일 수 있습니다.

 

 

이렇게 트리 DP의 느낌은 대충 잡았으니 문제를 하나 풀어보겠습니다. 너무 뻔한 것 말고 적당히 어려워서 "아, 이게 트리 DP구나" 하고 음미할 수 있는 수준의 문제를 준비했습니다.

일단 BOJ 1949번: 우수 마을 문제를 보면 어렵습니다. 어려운 것은 맞지만 아예 밑도 끝도 없이 새로운 것은 아닙니다. BOJ 1149번: RGB거리나 BOJ 9465번: 스티커 문제를 한 번 다시 보고 오시면, 일단 트리는 배제하고 마을이 만약 일자로 생겨 있다고 했을 때 대충 맥락은 알 수 있을 것입니다. 차례차례 구해나가면서 각 정점이 우수 마을일 때와 아닐 때의 주민 수의 총합 중 최대를 계속 관리해 나가면 될 것 같습니다.

일단 이 정도까지는 알겠고, 여기서 3번 조건이 약간 함정인데 3번 조건을 무시하고 총합이 최대가 되게 선택을 한다면 어떻게 될까요? 총합이 최대가 되게 선택을 했는데 3번 조건에 모순이 생길 수 있을지 생각해봅시다.

 

 

다행히 3번 조건을 무시하고 총합이 최대가 되게 선택을 했을 때, 모순이 발생할 수 없습니다. 지금 이 그림에서 4개 정점이 모두 우수 마을이 아니라고 가정해 봅시다. 그러면 가운데 정점은 3번 조건에 위배되는 셈입니다. 그런데 그럴 경우, 그냥 저 가운데 정점을 우수 마을로 선택해 버리면 됩니다. 인접한 정점 중에 우수 마을이 없으니까 가운데 정점을 우수 마을로 선택해도 2번 조건을 잘 만족하고 심지어 주민 수의 총합은 늘어나게 됩니다.

따라서 우수 마을 주민 수의 총합을 최대로 택했다면 3번 조건은 자동으로 만족된다는 결론을 얻을 수 있습니다. 그렇다면 1번과 2번 조건만을 가지고 식을 잘 세우면 되고, RGB거리나 스티커 문제에서의 느낌처럼 지금 보는 정점이 우수 마을일 때의 최댓값과 일반 마을일 때의 최댓값을 관리하는 방식으로 DP 식을 이끌어낼 수 있습니다.

 

 

주어진 그래프가 트리 구조라고 되어 있으니 아무 정점이나 루트로 올립니다. 그리고 D1 테이블을 i번 정점이 우수 마을일 때 서브 트리에서 우수 마을 주민 수의 총합의 최대값으로 정의하고, D2 테이블을 i번 정점이 우수 마을이 아닐 때 서브 트리에서 우수 마을 주민 수의 총합의 최대값으로 정의합니다.

이렇게 정의한 뒤, D1[1]과 D2[1]을 구할 때, D1[2], D1[3], D1[4], D2[2], D2[3], D2[4]를 어떻게 써먹을 수 있을지 고민해 보겠습니다.

 

 

먼저 D1[1]을 보면, 1번 정점을 우수 마을로 두었으므로 1번 조건에 따라 2, 3, 4번 마을은 반드시 우수 마을이 아니어야 합니다. 그러면 D1[1]의 식은 바로 도출이 가능합니다. 1번 마을의 주민 수를 A라고 하면 A는 당연히 더해져야 하고 2, 3, 4번 마을에서는 각 마을이 우수 마을이 아닐 때 총합의 최대값을 가져오도록 D2[2], D2[3], D2[4]를 더해주면 됩니다.

 

 

다음으로 D2[1]에서는 1번 정점을 우수 마을로 두지 않으므로 2, 3, 4번 마을은 우수 마을이어도 상관없고 아니어도 상관없습니다. 이 경우에는 D1과 D2 중에서 최댓값을 더해주면 됩니다. 그래서 식은 저기 적힌 것처럼 구할 수 있습니다.

여기서 만약 max를 구한 결과 3개 마을 모두에서 D2[2], D2[3], D2[4]가 선택되면 세 마을 모두 우수 마을이 아니라는 뜻이 되므로 3번 조건과 모순이 될 수 있다는 의문이 생길 수 있습니다. 여기서 다시 한 번 정리해 드리겠습니다. 앞에서 본 것처럼 총합을 최대로 한다면 3번 조건은 자동으로 만족되므로 고려할 필요가 없다고 했습니다. 그런데 이 DP 식으로만 따지면 부분적으로는 3번 조건에 모순이 될 수 있는 경우가 있을 수 있습니다.

 

 

예를 들어, 지금처럼 트리가 1-1-5처럼 생겨 있으면 D1과 D2 값은 저렇게 됩니다. 그런데 루트의 D2 값은 제일 밑의 값이 5인 정점만 포함되므로, 이 D2 값의 상황에서는 3번 조건이 만족하지 않게 됩니다. 하지만 상관없는 것이 어차피 총합을 최대로 하면 3번 조건은 자동으로 만족한다는 것을 알기 때문에 저 D2 값은 답을 구할 때 사용되지 않습니다. 이처럼 DP를 계산하는 중간에는 3번 조건이 만족하지 않을 수 있습니다. 하지만 최종 답에는 어차피 3번 조건이 만족되므로, 이 조건을 신경 쓸 필요는 없습니다. 3번 조건은 그냥 없는 조건으로 생각하고 문제를 풀면 됩니다.

그리고 DP에서는 항상 테이블 정의와 식을 찾을 뿐만 아니라, 초기값과 채우는 순서도 생각해야 합니다. 식의 특성상 자식의 DP 값이 먼저 구해져야 하므로 밑에서부터 값을 채워나가면 됩니다. 또한 초기값은 리프 정점들에서 자명하게 정해지니까 이것들을 어떻게 처리할지는 코드를 보면서 이해해 보면 됩니다.

 

 

어쩌면 잊고 있을 수도 있는 트리에서의 DFS 순회를 이용한 구현은 좀 더 편리할 수 있습니다. 이는 사실상 top-down 방식이라고 볼 수도 있습니다. 1번을 루트로 잡고 DFS를 돌면서 계속 자식으로 내려갑니다. 리프 정점까지 도달하면 더 이상 자식이 없으므로, 그 시점에서 d1[cur] = a[cur], d2[cur] = 0으로 설정한 뒤 함수가 끝납니다.

그리고 트리에서 DFS의 특성상 DFS 함수 호출이 일어날 때마다 각 정점은 처음 방문한 상태이기 때문에, 원래 top-down에서 하던 것처럼 d1[cur]이 이미 계산된 것인지 확인할 필요가 없습니다. 만약 이 DFS 코드가 헷갈린다면, 트리 단원을 다시 보고 오시는 것을 추천드립니다.

이렇게 계산을 마친 후에는 d1[1]과 d2[1] 중 최대값을 반환하면 그것이 바로 답입니다.

 

드디어 마지막 위상 정렬 DP입니다. 위상 정렬이 무엇인지 기억을 되새겨보면, 방향 그래프, 구체적으로는 DAG에서 선후 관계에 모순이 없게 나열하는 정렬입니다. 그리고 이 선후 관계에 따라 DP 식이 정해지는 상황에서는 위상 정렬을 하는 과정에서 테이블도 함께 채워나가는 방식으로 위상 정렬 DP를 수행할 수 있습니다. 이제 문제를 보면서 상황을 이해해보겠습니다.

 

 

BOJ 1005번: ACM Craft 문제를 보면 스타가 하고 싶습니다. 문득 드는 생각이 아무래도 강의를 듣는 사람들의 나이대는 계속 비슷하니까 시간이 지나면 지날수록 시청자층과 저의 나이 차이가 점점 커지게 됩니다. 그러면 저희 세대야 캐리어 뽑으면 이긴다 이런 표현을 하면 대부분 알아듣지만 몇 년 지나면 시간이 지나면 이 말이 무슨 뜻인지 모르는 사람들의 비율이 더 커지겠죠? 급 슬픕니다.

 

아무튼 문제를 보면, 식이 쉽게 감이 옵니다. 슬라이드의 그림처럼 건물 번호가 붙어 있다고 할 때 D[i]를 i번째 건물이 지어지기 위해 필요한 최소 시간이라고 정의할 수 있습니다. 여기서 D[5]를 계산하려면 4번과 6번 건물이 지어져 있어야 합니다. 문제 조건에서 건설을 동시에 할 수 있다고 하니 4번과 6번 각각 최소 시간으로 지은 후 둘 중 더 오래 걸리는게 지어지는 즉시 5번을 지으면 됩니다. 5번 건물을 짓는 데 걸리는 시간을 A라고 하면, D[5] = A + max(D[4], D[6])라는 식을 얻을 수 있습니다.

나에게 들어오는 정점들 중에서 최댓값을 구하기만 하면 되고, 초기값은 indegree가 0인 정점, 이 그림에서는 1번과 6번 정점에서 채울 수 있습니다. 테이블을 채우는 순서는 위상 정렬을 직접 수행하는 대신 top-down 방식으로 알아서 처리되게끔 할 수 있습니다. 이제 코드를 보며 더 구체적으로 이해해 보겠습니다.

 

 

코드를 보면 참 깔끔하게 잘 짰네요. 누가 짰는지..ㅎㅎ 기본적인 흐름은 top-down DP에서 설명한 상황과 완전히 똑같습니다. adj[x]에는 x로 들어오는 정점들의 목록을 두고, go(x)에서 d[x]를 구하는데 adj[x]를 쭉 보면서 그 d 값들을 참고하면 됩니다. 그리고 10, 11번째 줄의 처리로 중복된 계산을 막아줍니다.

시간 복잡도를 따지면, 각 정점에서 d 값은 한 번만 계산되고, d 값을 구할 때 자식의 개수만큼 시간이 걸립니다. 그러면 전체 정점들에서 자식의 개수의 합은 간선의 개수와 똑같으니, 시간 복잡도는 O(V + E)입니다. 물론 이걸 위상 정렬을 수행하고 위상 정렬 순서대로 테이블을 채워 나가는 방식으로 해결할 수도 있지만, 그것보다는 지금처럼 top-down 방식으로 푸는 것이 코드가 훨씬 간결하므로 이렇게 푸는 걸 추천드립니다.

그리고 응용력이 굉장히 좋은 분이라면 이 방식을 보고, "어, 그럼 반대로 위상 정렬을 원래 하던 대로 큐를 쓰는 것이 아니라 top-down으로 짜면 더 간결하지 않을까?"라는 생각을 할 수도 있을 것 같습니다. 실제로 이렇게 top-down 방식으로 위상 정렬을 수행할 수도 있고, 또 코드가 기존 방식보다 더 간결하다는 장점이 있습니다. 이건 그냥 살짝 TMI 느낌으로, "아, 그렇구나" 정도로 언급드린 걸로 끝내겠습니다.

 

 

정말 수고 많으셨습니다! 작성하다보니 이것도 설명하고 싶고 저것도 설명하고 싶고 해서 분량이 상당히 길어졌습니다. 아무튼 도움이 되셨길 바라며 이만 마치겠습니다. 행복하세요~~