밤이 블로그

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..

BOJ#11053 가장 긴 증가하는 부분 수열(LIS) * 문제https://www.acmicpc.net/problem/11053 * 풀이 유명한 문제인 Longest Increasing Subsequence (LIS)입니다.O(N^2) 방법과 O(N logN) 방법으로 풀어보았습니다. 기존에 워낙 설명이 잘 되어있어서 따로 포스팅 하지는 않겠습니다만,제가 공부할 때 참고했던 사이트 남겨드립니다. 1. LIS 이해 및 O(N^2) 풀이https://www.youtube.com/watch?v=CE2b_-XfVDk 위 동영상을 보시고 아래 저의 코드를 보시면 되겠습니다. * 나의 코드 // O(N^2) for (int i = 1; i < N; i++) { for (int j = 0; j < i; j++) {..

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#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#11726 2xn 타일링 * 문제https://www.acmicpc.net/problem/11726 * 풀이동적계획법(Dynamic Programming)을 이용합니다. 2xN일 때, 아래와 같이 2개의 하위 문제로 나눌 수 있습니다. dp[N] = dp[N-1] + dp[N-2](dp[N] = 2xN 직사각형을 1x2, 2x1 타일로 채우는 방법의 수) static int go(int n) { if (n 0) { return dp[n]; } dp[n] = (go(n - 1) + go(n - 2)) % DIVISOR; return dp[n]; } * 나의 코드https://github.com/stack07142/BOJ/tree/master/B..

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