나는 왜 DP에 실패하는가?
1.
DP란 무엇인가?
•
개념
•
적용 방식
2.
나는 왜 실패하는가?
1) 중복 대상 파악 실패
2) 자료구조 설계 실패
3.
결론
1. DP란 무엇인가?
이하는 스스로의 이해를 위해 정리한 내용이므로, 본론이 급하다면 2번 항목부터 읽어도 된다.
1) 개념
프로그래머의 작업을 이해하는 데에는 다양한 방식이 있겠지만, 나의 경우에는 제품을 설계하는 엔지니어와 본질적으로 같다고 생각한다. 그저 외형이 다를 뿐, 자원을 적절하게 배분하여 목표를 달성하는 점이 같다. 그렇다면 프로그래머에게 주어진 자원은 무엇일까? 바로 공간(메모리)와 시간이다.
두 자원을 균형적으로 운용할 수 있었다면 이상적이지만, 현대 컴퓨터 환경에서는 이러한 자원에 불균형이 발생했다. 메모리는 소재의 발전과 규모의 경제로 풍부해진 반면, 시간은 SW수요의 급증과 인간의 근본적인 한계로 인해서 더 부족해진 것이다. DP는 이러한 불균형을 해소하기 위해서 등장했다.
DP란 동적 계획법(Dynamic Programming)의 약자로, 상대적으로 풍부한 메모리를 더 투입하고, 사용을 극대화 하여 시간의 부족함을 보완하는 프로그래밍의 패러다임이다. DP라는 이름은 사실 개념과는 아무런 관련이 없으며, 개인적으로는 MMR(Maximize Memory Reuse)이라 이름 붙이고 싶다. DP는 각종 코딩 테스트 및 여러 프로그래밍 대회의 단골 소재로 나를 괴롭힌다.
2) 적용 방식
기본적으로 컴퓨터의 미덕은 반복작업을 극도로 빠르게 수행함에 있다. 따라서 컴퓨터를 활용하는 가장 근본적인 방법은 노가다, 즉 Brute-Force이다. 그러나 이러한 방식에는 필연적으로 시간이 많이 든다는 단점이 있다. 상황에 따라서는 O(N!)이나 O(a ^ N) 등 상식적으로는 수행이 불가능한 시간 복잡도를 갖게 된다. DP는 이러한 문제에 대하여 불필요한 중복 연산을 과거에 기록해둔 메모리에 대한 참조(즉 변수로 재활용)로 대체하여 시간 복잡도를 다항 시간으로 끌어내리는 것을 목표로 한다.
2. 나는 왜 실패하는가?
그렇다면 나는 왜 dp에 대한 글을 쓰게 되었는가? 그건 내가 이 dp를 정말 못하기 때문이다. 알고리즘을 공부하고, 문제풀이를 시작한지 어연 6개월, 여전히 나는 dp에서 고전을 면치 못한다. 자신에 대한 분노와 dp에 대한 원한을 담아 이 글을 쓴다.
1) 중복 대상 파악 실패
DP 문제를 실패하는 가장 큰 사유. 문제를 읽었고, 평범한 풀이 방식으로 접근해서는 도저히 답이 없는 시간 복잡독 도출되는 경우(지수, 팩토리얼, 등) 우리는 DP의 도입을 고려한다. 그러나 문제의 풀이 과정에서 어떤 부분이 중복될 수 있는지 분석에 실패한다면 DP는 적용할 수 없다.
// Naive Fibonacci.
// F(n) = F(n - 1) + F(n - 2)
int fibonacci(int n)
{
if (n == 1 || n == 2)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
C++
복사
DP라는 개념을 공부하면서 가장 먼저 접하는 문제는 피보나치 수열 문제일 것이다. 피보나치 수열은 점화식으로 정의되며, 또한 그 정의가 재귀적이기에 쉽게 풀 수 있다.
// Fibonacci with DP.
int cache[MAX_NUM] = { 0 };
int fibonacci(int n)
{
if (n == 0)
return 0;
else if (n == 1 || n == 2) // 적절한 초기화로 생략가능
return 1;
else if (cache[n] != 0)
return cache[n];
else
return cache[n]
= fibonacci(n - 1) + fibonacci(n - 2);
}
C++
복사
피보나치 수열 문제는 DP의 도입에 대한 아주 적절한 예제다. 피보나치 수열을 정의하는 점화식에 n-1번째 항을 계산하기 위해서 사용한 n-2번째 항이 n번째 항을 구하는 데에 재활용 되는 점이 중복을 명시적으로 나타내기 때문이다.
그러나 이렇듯 명시적으로 중복 여부가 드러나는 경우는 거의 없다. 심지어 문제의 상황에 따라서는 DP를 사용해야 한다는 판단 자체가 서질 않는다. 이러한 연산의 중복을 파악하는 방법은 문제에 대한 심도깊은 분석 뿐이며, 이는 곧 소위 말하는 문제 해결력, 즉 프로그래머의 피지컬에 해당한다.
나는 아직까지 해당 실패 사유에 대한 명확한 해결법을 찾지 못했다. 좋은 방법이 있다면 댓글 부탁드립니다.
2) 자료 구조 설계 실패
이렇듯 힘겹게 DP의 도입을 확신하고, 제거해야 할 중복의 존재를 확인했다 해서 문제가 풀리는 것은 아니다. DP를 수행하기 위해서는 적절한 자료구조에 단계적인 계산 결과들을 기록해야 한다. 무엇보다 해당 자료구조는 재활용을 위한 빠른 접근을 보장해야 한다. 따라서 일반적으로는 N차원 배열을 활용해서 계산 결과를 기록하게 된다.
// 다항 방정식, F라는 시스템은 n개 축을 가진 상태공간에서 정의됨.
y = F(x1, x2, x3, ... xn)
// DP
int cache[x1][x2][x3]....[xn];
C++
복사
문제에서 수행되는 계산의 횟수에 맞게 배열을 정의했다면, 그 다음은 접근 방법을 고민해야 한다. 일반적인 배열을 사용하는 경우, 각 계산의 단계는 여러 값들을 통해서 정의된다. 마치 방정식의 해를 얻기 위해서는 각 변수들의 값이 결정되어야 하듯 말이다. 따라서, 각 계산 단계를 정의하는 값들을 하나의 독립변수로 생각하고, 상태공간을 정의하는 독립된 축으로 삼는다. 즉 상태를 정의하는 값이 3종이 있으면 3차원 배열을 사용하게 된다. 어떠한 값이 상태를 정의하는 독립변수이며, 이를 축으로 삼고 접근할 지는 프로그래머의 구현력, 컴퓨터사고력을 요구한다.
하지만, 일반적인 N차원 배열의 형태를 넘어서는 경우도 왕왕있으며, 이러한 경우에는 프로그래머의 구현력이 시험된다. 대표적으로는 나를 좌절시켰던 습격자 초라기 문제(백준 1006번)가 일반적인 N차원 배열의 DP에서 벗어나는 문제다.
해당 실패 사유에 대해서는 경험이 큰 도움이 되었다. 일반적인 N차원 DP문제의 경우에는 어느정도 형태가 정해져 있으며, 이는 경험적으로 알 수 있다. 하지만 N차원에서 넘어가는, 특이한 자료구조를 요구하는 경우에는 아직 명확한 접근 방식을 알아내지 못했다. 마찬가지로 좋은 방법이 있다면 댓글 부탁드립니다.
3. 결론
DP문제를 풀기 위해서는 다음의 두 덕목이 필요하다.
1.
문제를 분석하여 중복된 연산을 규명
→ 문제해결력
2.
적절한 자료구조를 설계하여 중복 내용을 빠르게 접근
→ 컴퓨터 사고력
DP는 프로그래머에게 핵심적인 두 가지 덕목인 문제 해결력과 컴퓨팅 사고력을 모두 요구하는 복합적인 문제이다. 이들 두 덕목을 모두 얻어야 상황에 맞는 DP를 적용할 수 있으며, 둘 중 어느 하나라도 부족하면 문제에 접근조차 하지 못하거나, 풀더라도 바로 제한 시간을 통해서 거를 수 있다. 이러한 탓에 코테나 대회에 자주 출제되는게 아닌가 생각된다.
지금까지 나의 여정에서 컴퓨터 사고력은 확실하게 발전했음이 느껴진다. 여러 알고리즘을 학습하고 문제를 풀면서 얻은 통찰은 적절한 자료구조의 선정에 큰 발전을 가져왔다. 하지만 문제해결력 부분에서는 발전이 느껴지지 않는다.
문제 해결력이란 이름을 붙이기는 했지만, 사실 이 덕목이 어떤 것인지 잘 모르겠다. 스스로를 돌아보면, 풀은 문제는 처음 문제를 보고 직관적으로 접근 방법이 떠오른 경우가 대부분이다. 고민을 해서 접근 방법을 떠올린 문제의 경우에는 일반적으로 수일이 넘는 시간이 걸렸다.
과연 생각하는 방식은 학습이 가능한가? 소위 문제풀이 고수들에게는 문제를 대하는 방식이 정립되어 있어, 의식적으로 뇌를 사용하는 방법이 있는듯 하다. 하지만 나로서는 이 부분이 이해가 되지 않는다. 누군가에겐 당연하게 느껴지는 접근 과정이, 그 당위성이 이해가 되지 않는다. 이러한 생각의 방식이 과연 학습이 가능한 부분인지 잘 모르겠다.
