[Algorithm] 동적 계획법(Dynamic Programming)

작성 이유

[Programmers] 완전범죄 - Java

이 문제를 풀면서, 다이나믹 프로그래밍에 대한 이해가 부족해서 풀이를 설명하기 매우 어려운 것을 느꼈기 때문에 이 글을 작성한다.

그리고 사실, 다이나믹 프로그래밍은 코딩테스트에서 가장 큰 벽이라고 생각해서 이 참에 이 벽을 넘어보려고 한다..

 

동적 계획법(Dynamic Programming)

작은 문제의 결과가 큰 문제가 되는 경우에 사용할 수 있는 알고리즘

N-x번째의 결과도 정답이 되고, N번째 답도 정답이 된다. 즉, 중간 과정에 구해진 값도 모두 정답이 된다.

완전 탐색쪽으로 생각을 하는 연습이 필요하다. 또한 완전 탐색을 해야하는 경우, N의 값이 100,000이라는 큰 숫자라면 의심을 해보는 것이 좋다.

ex) 물건을 훔치는경우/훔치지 않는 경우 => 시간복잡도: O(2^100000) => 절대 안된다... 

정답을 저장하는 배열이 있으며 주로 for문이나 재귀함수로 구현이된다.

 

메모이제이션(Memoization)

한번 구한 값을 배열에 저장해두고, 다음에 같은 값이 필요하면, 저장해둔 배열 값을 다시 사용하는 것으로, 시간복잡도를 줄일 수 있다.(캐시와 같은 역할)

 

문제 풀이 방식

1. 문제를 읽어보면서 어렵게 만드는 변수들을 파악한다.

가령 Knapsack 알고리즘이라고 한다면, 가방의 부피, 물건의 가치와 같은 것들을 의미한다.

 

2. 테이블을 일단 정의해본다.(감으로 가정)

테이블 정의가 틀려도 좋다. 자꾸 가정해보면서, 풀이 방법을 찾는 것이다.

 

3. 정의한 테이블로 문제에서 원하는 답이 도출이 될 수 있는지 파악해본다.

문제 요구가 무엇이고 충족이 되는지 확인

임의의 k에서 정의한 테이블이 어떤 의미를 가지는지 설명할 수 있어야 한다.

 

4. 정의한 테이블로 어떻게 초기화를 하면 될지 구상해본다.

다이나믹 프로그래밍에서는 초기화를 하고 들어가는 경향이 있기 때문이다.

 

5. 점화식을 도출해본다.

큰 문제가 있다면, 작은 문제로 쪼개서 도출해본다.

여기서 작은 문제를 결정하는 요소는 문제에서 변화하는 요소이다.(물건을 훔치는 것/훔치지 않는 것, 물건을 가져가는 것, 가져가지 않는 것)

 

1~5번을 반복하면서 DP 문제를 해결한다.