나는 왜 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);
}