본문 바로가기

다이나믹 프로그래밍

(2)
다이나믹 프로그래밍[Dynamic Programming] 문제풀이-2 (10문제) 11048 이동하기 https://www.acmicpc.net/problem/11048문제의 특징 1. 시작-> 도착 2. 이동방향3. 양의 정수 이동할수록 문제의 크기가 작아진다. 위나, 왼쪽으로 이동 못하므로 -> 항상 문제가 작아지므로 다이나믹 프로그래밍이라고 알 수 있다. 풀이 1O(NM) = NxMx1D[i][j] = (i, j)로 이동할 때 가져올 수 있는 최대 사탕 개수D[i][j] = Max(D[i-1][j-1], D[i][j-1], D[i-1][j]) + maps[i][j];for(int y=1; y풀이 2현재 d[i][j]까지 값을 채웠고 다음 3가지 방법을 채우는 방법 (1번과 순서가 다름)D[i][j+1] = D[i][j] + maps[i][j+1]; = max(D[i][j+1]);..
다이나믹 프로그래밍[Dynamic Programming] 1. 다이나믹 프로그래밍이란?2. 다이나믹 프로그래밍의 속성3. 다이나믹 문제 푸는 방법 4. 다이나믹 문제 풀이 전략 5. 다이나믹 프로그래밍 문제 1. 다이나믹 프로그래밍이란?다이나믹 프로그래밍 :Dynamic Programming 큰 문제를 작은 문제를 나눠서 푸는 알고리즘 1940년대 수학자인 Richard Bellman은 'Dynamic Programming'이란 용어를 사용했다.그는 프로세스가 다단계로 이루어져 있으며, 시가변적(time-varing)이며, '동적(Dynamic)'이다라는 개념(idea)이 전달되길 원했다.큰 문제 안에 작은 문제가 중첩되어있는 문제를 해결하는 데 사용하는 계획법(Programming)인것이다. 2. 다이나믹 프로그래밍의 속성알고리즘 측면에서 다이나믹 프로그래밍..