동적계획법

[알고리즘]다이나믹 프로그래밍(DP, 동적계획법)

다이나믹 프로그래밍이란? 다이나믹 프로그래밍(Dynamic Programming)은 다른말로 동적계획법 이라고 합니다. 저도 처음에는 동적계획법을 듣고 왜 동적계획법일까? 했는데 이름 지으신분이 그냥 이 이름이 멋있어서 이렇게 지었다고 하네요... DP(다이나믹 프로그래밍)알고리즘은 백준 사이트 알고리즘별로 문제풀기에서 가장많은 문제수를 가지고 있어요! 그만큼 종류도 다양하고, 출제빈도도 높습니다. ​ DP는 작은문제를 풀어서 큰문제를 해결하는 알고리즘입니다. 여기서 주의할점은 작은문제들을 여러번에 걸쳐서 다시 푸는일이 없도록 어딘가에 값을 저장해두고, 필요할 때 그 값만 가져와서 사용한다는 점입니다. ​ 즉, 문제를 여러번 풀지않고 단 한번만 계산을 할 수 있는 거죠. ​ ​ 예) 피보나치 수열 위는 ..