동적 계획법

다이나믹 프로그래밍(동적 계획법)

다이나믹 프로그래밍이란 동적 계획법이라고 한다. 간단히 설명하자면 어떠한 문제를 한번에 해결하기 어렵기 때문에 작은 문제로 쪼개어 작은것 부터 하나씩 해결하여, 마지막에 문제를 해결하는 것이다. 솔직히 무슨 말인지 바로 와닿지 않는다. 그러나 원래 모를때는 일단 들으면서 알때까지 자료를 찾아보면 얼추 이해가 되기 마련이다. 다이나믹 프로그래밍에는 2가지가 존재한다. 1. Bottom-up : 작은 문제를 처음부터 풀어가는 방식이다. 주로 점화식을 세우고 for 구문으로 빠르게 해결해준다.(리스트나 배열에 직관적으로 구할 수 있는 값들이 넣어넣고 for 구문을 시작한다.) 2. Top-down : 재귀함수로 주로 구현하기 때문에 큰 문제를 풀기위해 작은 문제로 파고들어가서 작은 문제를 해결하면서 큰문제를 ..