밤이 블로그

BOJ#2293 동전1 * 문제https://www.acmicpc.net/problem/2293 * 풀이정말 이해하기 쉽지 않은 문제였습니다.조금 더 완벽하게 이해한 후에 저의 풀이를 포스팅하도록 하겠습니다. 참고한 풀이 : http://blog.naver.com/occidere/220784778900import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#2293 동전1 * https://www.acmicpc.net/problem/2293 */ public class Main { // dp[i] : n가지 종류의 동전..

BOJ#2011 암호코드 * 문제https://www.acmicpc.net/problem/2011 * 풀이동적계획법(Dynamic Programming)을 이용합니다. 숫자의 범위가 1~26이므로어떤 해석할 수 있는 암호가 주어졌을 때, 마지막 숫자는 아래와 같이 3가지 경우로 나눌 수 있습니다. 그리고 아예 해석할 수 없는 경우도 있습니다. (dp[i] : i번째 숫자까지 해석했을 때, 해석의 가짓수)1) 한 자리수로만 해석할 수 있는 경우예 : "251" → 마지막 숫자 "1"은 "1"로 해석 가능하나, "51"로는 해석할 수 없다. 즉, "25"에서 "1"을 추가한 경우 dp[i] = dp[i-1]; 2) 두 자리수로만 해석할 수 있는 경우 예 : "2510" → 마지막 숫자 "0"은 "10"로 해..

BOJ#2225 합분해 * 문제https://www.acmicpc.net/problem/2225 * 풀이dynamic Programming 문제입니다. 예를 들어 2 2가 입력된 경우 아래와 같이 3가지 경우가 있을 수 있습니다.0 + 21 + 12 + 0 3 2가 입력된 경우에는0 + 31 + 22 + 13 + 0 4 2가 입력된 경우에는0 + 41 + 32 + 23 + 14 + 0 감이 오시나요?어떻게 풀어야 할지 모를때는 예제의 숫자를 낮춰서 생각하면 좋습니다. " N K가 입력된 경우에서첫번째 숫자가 m으로 정해지면나머지는 N-m K-1의 경우가 됩니다. " dp를 아래와 같이 정의하고 위 내용을 구현하시면 되겠습니다. - dp[N][K] : 0~N까지의 정수 K개를 더해서 그 합이 N이 되는 경..

BOJ#1699 제곱수의 합 * 문제https://www.acmicpc.net/problem/1699 * 풀이Dynamic Programming 문제입니다. 주의할 점으로,Greedy 하게 풀면 안됩니다. 반례로 12의 경우를 생각해보시면 되겠습니다.ex) 12 = 3^2 + 1^2 + 1^2 + 1^2 (4) = 2^2 + 2^2 + 2^2 (3) 따라서 동적계획법을 이용하면서 완전 탐색을 해주시면 됩니다. - 비슷한 문제 https://www.acmicpc.net/problem/1463 * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%231699_SumOfSquares

BOJ#11055 가장 큰 증가 부분 수열 * 문제https://www.acmicpc.net/problem/11055 * 풀이 BOJ#11053 문제와는 조금 다른 문제입니다.11053 문제는 '증가하는 부분 수열' 중 가장 긴 수열의 길이를 구하는 것이었고,11055 문제는 '증가하는 부분 수열' 중 수열의 합이 가장 큰 것을 구하는 것입니다. 즉, 가장 긴 수열이 항상 가장 큰 합을 보장하지 않으므로dp를 11053 문제와는 다르게 설계하셔야 합니다. 11053의 dp[i]가 'A[i]를 포함하는 수열 중에, 길이가 가장 긴 수열의 길이' 였다면,11055의 dp[i]는 'A[i]를 포함하는 수열 중에, 수열의 합이 가장 큰 수열의 합' * 나의 코드https://github.com/stack0714..

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