밤이 블로그

http://stack07142.tistory.com/39 * 동적 계획법 (Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. : 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종 목표를 구한다. : 하위 문제들의 해결책을 저장하여 이후 같은 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. * 메모이제이션 (Memoization) : 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 반복 계산을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. : 동적 계획법의 핵심이 되는 기술이다. (예제) 피보나치 수열 보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다.function fib(n) i..

BOJ#2156 포도주 시식 * 문제https://www.acmicpc.net/problem/2156 * 풀이동적계획법(Dynamic Programming)을 이용해봅시다. 일단 아래와 같이 배열을 선언합니다.dp[n] : n잔 째 마셨을 때, 최대로 마실 수 있는 포도주의 양p[n] : 포도주 n번 째 잔에 들어있는 포도주의 양 포도주는 3번 연속해서 마실 수 없으므로,n번 째 (마지막) 포도주는 3가지 경우로 나눌 수 있습니다.마시지 않는 경우, 1잔 째 마신 경우, 2잔 째 마신 경우 우리가 구하려는 dp[n]을 구해봅시다.1) 마지막 n번 째 포도주 잔 - 마시지 않는 경우 : n-1번 째 잔은 다시 1, 2, 3번의 경우로 나누어 질 수 있습니다. : dp[n] = dp[n-1] 2) 마지막 n..

BOJ#9465 스티커 * 문제 https://www.acmicpc.net/problem/9465 * 풀이 동적계획법(Dynamic Programming) 문제입니다. 최종적으로 점화식을 구해야 문제를 풀 수 있습니다. 0) 자료구조- 각 스티커의 점수를 저장하는 2차원 int 배열 : cost - 0열에서 출발하여 해당 위치까지의 점수의 합을 저장하는 2차원 int 배열 : dp 1) 시작점 생각하기0열에서 시작한다고 생각해봅시다. 시작점은 (0, 0), (0, 1)으로 2개가 됩니다. 2) 다음 스티커 선택하기(0, 0)에서 시작할 경우 (1, 1), (1, 2) 스티커를 선택할 수 있습니다. 그리고 (1, 1)과 (1, 2) 중에서 큰 값을 선택하면 됩니다. 한편, (0, 0)에서 (0, 2), (..

BOJ#10844 쉬운 계단 수 * 문제https://www.acmicpc.net/problem/10844 * 풀이동적계획법(Dynamic Programming)을 이용합니다.일단 점화식을 만들어야 하는데.. 저에게는 꽤 어려운 문제였습니다. dp[N] : 길이가 N인 계단 수의 개수 → 인접한 자리수의 차이가 1이라는 조건을 이용할 수 없으므로 아래와 같이 점화식을 구성합니다. dp[N][L] : 길이가 N이면서 마지막 수가 L인 계단 수의 개수 → 마지막 수가 L이므로 앞자리 수는 L-1, L+1이 될 수 있다. → dp[N][L] = dp[N-1][L-1] + dp[N-1][L+1] public class Main { // dp[N][L] : 길이가 L이고 마지막 수가 L인 계단 수 // dp[N]..

BOJ#1463 1로 만들기 * 문제 https://www.acmicpc.net/problem/1463 * 풀이 동적 계획법 (Dynamic Programming) 기초 문제입니다. * 동적 계획법 (Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. : 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종 목표를 구한다. : 하위 문제들의 해결책을 저장하여 이후 같은 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. * 메모이제이션 (Memoization) : 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 반복 계산을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. : 동적 계획법의 핵심이 되는..