DP 동적 계획법 개념

DP(Dynamic Programing)은 직역하면 동적인 프로그래밍이다.

여기서 프로그래밍은 코드를 작성하는 행위를 뜻하는 것이 아니라, 테이블을 이용한다는 뜻을 의미한다.

 

+ 테이블을 이용한다가 무슨 뜻일까?

DP에서는 이전의 값을 저장하여, 한번 구한 값은 다시 구하지 않는다. 이때의 저장하는 배열을 테이블이라고 하는 것 같다.

 

 

 

 

필요한 배경지식

DP는 왜 등장한 것일까?

DP는 이전에 구했던 값을 활용하여 효율성을 증가시키기 위해 만들어진 것이다. 이를 조금 다르게 생각해 보면, 이전에 구했던 값을 반복해 구하는 상황에서, 이러한 비효율적인 문제를 해결하기 위해 나온 것이라고 볼 수 있다.

 

 

흔히 DP는 트리를 그리는 것과 흡사하다고 한다.

왜 트리를 그리는 것과 흡사할까? 
이를 좀 더 쉽게 이해하기 위해 
아주 간단한 DP문제인 피보나치 수열 문제를 봐보자.

 

위 문제는 피보나치 수열을 구하는 문제를 트리로 표현한 것이다. 이렇게 트리 형태를 지니는 상황에서 문제를 좀 더 효율적으로 해결하기 위해, 우리는 테이블에 이전의 구한 값을 저장한 후 활용하여 풀게 된 것이다.

 

 

활용

이러한 배경지식을 가진 상태에서 문제를 보았을 때, 조금 다른 관점으로 접근할 수 있었다.
먼저 문제를 접할 때, 완전 탐색으로 접근한 후 이를 효율적으로 짜려는 생각을 거치면 자연스레 DP가 생각이 났다.