[알고리즘] 동적계획법 DP(Dynamic Programming)

DP가 왜 필요?

DP의 장점?

DP 문제 어떻게 알아보고 접근할지

 

1. 다이나믹 프로그래밍의 목적

DP 는 완전 탐색, DFS, BFS 와 같이 수많은 경우의 수를 전부 따져봐야 하는데, 경우의 수가 너무 많아서 속도가 느려지는 문제를 개선하고 수행시간을 단축하고자 만들어진 알고리즘.

DP가 없던 시절에는 최단 경로를 찾거나, 최고 점수를 만들거나 하는 문제를 풀기 위해 모든 조합을 다 만들어 보는 수밖에 없었음.

DP 알고리즘이 만들어진 후에는 수행시간을 현저하게 줄일 수 있었다. 

예시) 프로그래머스 - 정수 삼각형 (Swift는 지원 안됌..ㅠ)

=> 메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여 수행 속도를 개선한다. 

메모리를 사용한다 : 배열 혹은 자료구조를 만든다.

중복 연산을 줄인다 : 연산한 결과를 배열에 담는다. (같은 연산을 다시 반복하지 않도록)

 

다이나믹 프로그래밍 = 기억하기 알고리즘

연산한 내용을 기억해 놓고, 다음에도 그 연산이 필요할 때 기억해놓은 값을 사용해서 문제를 푸는 것. 

 

2. 다이나믹 프로그래밍 문제 알아보고 구분하는 방법

다양한 유형의 문제를 최적화할 때 고려될 수 있는 알고리즘. 

1) DFS/BFS로 풀 수는 있지만, 경우의 수가 너무 많은 문제. 

보통 DFS/BFS 로 풀 수 있는 최대 경우의 수 : 500만 개(5*10^6)

그 이상일 경우, DP를 어떻게 구현할지 고민해봐야. 

2) 경우의 수들에 중복적인 연산이 많은 경우

 

3. 문제 해결 접근 방법

최대한 많은 문제들을 풀어보고 풀이들을 참고하면서 DP식 사고방식을 습들해야. 

어떻게 하면 뒤로 돌아가지 않을 수 있을까. 고민 

연산을 또 하지 않으려면 어떤 정보를 남겨야 할지. 어떤 식으로 정보를 누적해야 할지. 

-> DP 삼각형과 같이 나만의 자료구조를 하나 더 만들고, 어떤 정보를 담아야 이전 단계로 돌아가지 않을지 고민해보아야. 

어떤 정보를 어떻게 쌓아야 연산횟수를 가장 줄일 수 있을까를 고민하며 최적의 답을 쌓아가는 것!

 

DP는 정해진 구조를 그대로 구현하는 하나의 자료구조가 아니라, 수행 시간을 단축할 수 있는 기법이기 때문에 구현할 방법은 아주 많다.

따라서 다양한 풀이를 참고해보는게 많은 도움이 될 것. 

 

 

 

참고 : youtube - 개발자로 취직하기, 프로그래머스 - 동적계획법 문제들