동적계획법

[백준 1937] 욕심쟁이 판다 C++

1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net DFS + DP dp[r][c]값 : 판다가 r, c에서 출발했을 때 최대로 살 수 있는 날을 저장 상하좌우로 움직이며 얻는 dp값들 중 최댓값을 현재 dp값으로 갱신한다 방문여부, 좌표별 최대 생존일의 메모이제이션을 통해 문제를 해결 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ..

[백준 11404] 플로이드 C++

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 최단경로 플로이드-와샬 알고리즘 11404문제 예제 입력의 그래프이다 숫자가 겹쳐보이는 이유는 1 4 1 , 1 4 2 처럼 1번에서 4번 노드로 가는 경우의 비용이 중복되어서 입력되기 때문이다 플로이드-와샬 알고리즘은 동적계획법을 활용한 알고리즘이다 그래서 임의의 vertax 에서 다른 vertax로 가는 모든 경우의 수를 조사해서 최소 비용을 구할 수 있다. 그리고 다익스트라 최단거리 알고리즘은 edge의 비용이 음수인 경우는 찾지 못하는 반면 플로이드-와샬 ..

[백준 9252] LCS2 C++

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의..