개발노트 개발노트

1. 정의 : dp[n][m] : n행 m열 일때 합이 최대가 되는 경로의 합2. 점화식 : dp[n][m] = max(dp[n-1][m], dp[n-1][m-1])+value[n][m]3. 초기화 : dp[0][0] = value[0][0];4. 반례 : m=0 일때 주의 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include using namespace std; int main() { int count; cin >> count; int ** value = new int*[count]; // input int ** dp = new int*[count]; // memoization for (int i =..

이 문제 역시 끝을 기준으로 처리 해야된다. 그런데 같은 색을 연속으로 할 수 없는 조건 때문에 끝의 상태를 다르게 표현 해줘야된다. 따라서 이 문제는 2차원 배열을 이용한다. 1. 정의 : dp[n][3] : 3개의 색으로 n개의 집을 칠할때 비용의 최솟값, 끝이 n일때 0 or 1 or 2의 색을 나타낸다.2. 점화식 : dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + house[n][0] dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + house[n][1] dp[n][2] = min(dp[n-1][0], dp[n-1][1]) + house[n][2] 이후 min(dp[n][0], dp[n][1], dp[n][2])하여 최솟값을 출력한다.3. 초기화 ..

1. dp[n] : n을 1, 2, 3의 합으로 나타내는 방법의 수2. dp[n] = dp[n-1]+dp[n-2]+dp[n-3]3. 초기화 : dp[0]=1, dp[1]=1, dp[2]=2 핵심 : 마지막이 무엇인지 판단!이 전 문제까지(#1463, #11726, #11727)는 길이로 나타냈으나 여기서는 마지막에 오는 숫자가 무엇인지에 따라 판단했다. 123456789101112131415161718192021222324252627#include using namespace std; int d[12];int dp(int num) { if (d[num] > 0) { return d[num]; } else { d[num] = dp(num - 3) + dp(num - 2) + dp(num - 1); retu..

1. dp[n] : 2*n 직사각형을 채우는 방법의 수2. dp[n] = 2 * dp[n-2] + dp[n-1]3. 초기화 : dp[0] = 1, dp[1] =1 끝을 기준으로 어떻게 변화되는지 파악 12345678910111213141516171819#include using namespace std; int d[1004];int dp(int n) { if (d[n] > 0) { return d[n]; } d[n] = (dp(n - 1) + 2 * dp(n - 2)) % 10007; return d[n];} int main() { d[0] = 1; d[1] = 1; int n; cin >> n; cout

1. dp[n] : 2*n 크기의 직사각형을 채우는 방법의 수2. dp[n] = dp[n-1] + dp[n-2]3. 초기화 : dp[0] = 1, dp[1] =1; 핵심 : 끝을 기준 즉 N번째 타일이 들어올 때 어떻게 변하는지를 알아야 한다. 123456789101112131415161718192021#include using namespace std; int d[1005];int dp(int num) { if (d[num] > 0) { return d[num]; } d[num] = (dp(num - 1) + dp(num - 2)) % 10007; return d[num]; } int main() { d[0] = 1; d[1] = 1; int n; cin >> n; cout

1. dp[n] : 연산 3 개를 사용하여 n을 1을 만들때 연산 사용 횟수의 최솟값.2. 점화식 : dp[n] = min(dp[n/3], dp[n/2], dp[n-1]) +1 3. 초기화 : dp[0] = 0, dp[1] =0시간 복잡도 : O(N) N을 - - - 해서 변형을 해서 1로 만든다. 12345678910111213141516171819202122232425262728293031323334353637383940#include using namespace std; int d[1000001];int dp(int num) { int tmp; if (num 0) { return d[num]; } // Memoization d[num] = dp(num - 1) + 1; if (num % 2 == 0..

동적계획법(Dynamic Programming) 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 아래의 2가지 속성을 만족해야 DP로 문제를 풀 수 있다.1. Overlapping Subproblem- 예를 들어 피보나치 함수를 보자. f(6)을 구하기 위해서는 f(4), f(5)가 필요하고 f(5)의 값을 알기 위해서는 f(4), f(3)의 값이 필요하다. 즉 여기서 f(4)와 같이 부분문제들이 겹치고 n의 값에 상관 없이 작은 문제를 푸는 방법은 같다. 여기서 알 수 있는 것은 n의 값에따라 값이 일정하다는 것이다. 이로 인해 정답을 한 번 구했으면 정답을 어딘가에 메모 해놓자. 이 것을 Memoization(보통 배열)이라고 한다. 이로 인해 함수 호출 횟수를 줄일 수 있다.2. Oprimal S..

문자열을 다룰때는 아스키코드를 사용하는 경우가 많다. 외울 필요는 없고 상황에 따라 잘 활용해서 사용하면 된다. Example)https://www.acmicpc.net/problem/108081234567891011121314#include #include #include using namespace std;int main() { string s; cin >> s; for (int i='a'; i