[알고리즘] Dynamic Programming (DP)

알고리즘 문제를 풀 떄 항상 어려웠던 유형인 다이나믹 프로그래밍에 대해 깊이 다뤄보려고 한다.

개념

다이나믹 프로그래밍은 완전 탐색, DFS, BFS와 같이 수많은 경우의 수를 전부 따져봐야 하는데 그 경우의 수가 너무 많아서 속도가 느려지는 문제를 개선하고자 만들어진 알고리즘

특정 위치까지 올 수 있는 최적의 조합을 저장한다. 

각 위치까지 올 수 있는 최적의 값만 남겨 놓고 나머지 조합은 미리미리 버리기

기억하기 알고리즘. 기억하며 풀기.

장점

다음 단계를 계산할 때 최적이 아닌 다른 경우의 수는 고려하지 않기 때문에 연산 수가 줄어든다.

메모리를 사용해서 (=배열 혹은 자료구조 만듦)

중복 연산을 줄이고 (=연산한 결과를 배열에 담아서 같은 연산을 또 하지 않는다)

중복 연산을 줄여서 수행 속도를 개선한다.

판단 기준

다이나믹 프로그래밍은 특정 유형에만 국한되지 않고 다양한 유형의 문제를 최적화 할 때 고려될 수 있는 알고리즘이다.

1. DFS/BFS로 풀 수는 있지만 경우의 수가 너무 많은 문제 (DFS나 완전 탐색으로 풀 수 있는 마지노선은 대략 500만(5*10^6) 개의 경우의 수)
2. 경우의 수들에 중복적인 연산이 많은 문제

문제 해결 접근 방법

나만의 자료 구조를 하나 더 만들어서 어떻게 하면 이전 단계로 돌아가지 않을 수 있을까를 고민

현재 단계까지의 연산을 다시 반복하지 않으려면 어떤 정보를 남겨야 하지?

어떤 식으로 정보를 누적해야 하지?

여태까지의 최적의 답을 쌓아간다는 마음으로 프로그래밍을 한다. 

어떤 정보를 어떻게 쌓아야 연산 횟수를 가장 줄일 수 있을까를 고민하면서 DP식 사고방식을 습득하기

공부 방법

DP는 정해진 구조를 그대로 구현하는 하나의 자료구조가 아니라 수행 시간을 단축할 수 있는 기법이기 때문에 그 기법을 구현할 방법은 매우 많다. DP 유형만큼은 오래 붙잡고 있기 보다는 30분 정도 고민해보고 답이 안 나오면 풀이를 참고해서 구현만 해보는 방식을 추천한다.  

처음엔 brute-force하게 생각해본다. 일단 모든 경우를 다 테스트하는 코드를 짠 후에, 중복되는 함수 호출을 memoization을 통해 최적화해서 빨리 돌게 만들자. 라고만 생각하고 짜도 쉬운 문제들은 충분히 풀린다. 이런 단계를 통해 DP의 원리와 문제를 푸는 방법에 익숙해진 다음에 좀 더 어려운 기법들과 문제들을 차근차근 풀어나가면서 연습하는게 DP를 공부하기 좋은 방법인 것 같다.

• 백준 DP 문제집
  • https://www.acmicpc.net/workbook/view/157
  • https://www.acmicpc.net/step/16

References

• https://www.youtube.com/watch?v=0bqfTzpWySY
• https://www.acmicpc.net/board/view/22717