건빵의 블로그

재밌는것 같은데 너무 어려운 다이나믹 프로그래밍.ㅡㅜ Dynamic Programming(동적 프로그래밍)은 문제를 작은 인스턴스들로 나누고 Bottom-up order로 풀어나가면서 문제의 값을 저장해놓고 필요할때 가져와 쓰는 방식으로 문제를 해결하는 방식을 의미한다. Divide and conquer와의 공통점은 문제를 작은 단위로 나누어 해결한다는 것이고 차이점은 Divide and conquer는 Top-down 방식으로 위에서부터 진행하는 방식인데 Dynamic Programming은 Bottom-up 방식으로 작은 인스턴스부터 풀어나가면서 그 값을 더 큰 인스턴스를 풀 때 이용한다. 기존에 진행된 smaller instance의 값들은 주로 이차원 array에 저장되며 영향을 받는 변수의 수에..