Algorithm/dp
백준 2225 합분해 c++ // dp 규칙찾는 방법
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. dp 규칙찾는 방법 1.1 표를그린다 1.2 규칙을세우고(뒤에만 숫자추가하기) 경우의수를 센다. 1.3. 그 숫자가 어디서 왔는지 규칙을 찾고 화살표로 표시한다 1.4. 규칙을 찾았으면 dp 테이블로 옮기고 숫자의 이동을 표시한다. 1.5. 점화식을 세운다(dp[j]=dp[j]+dp[j-1]) 2. 전체코드 #include using namespace std; int n, k; int dp[204]; int divd = 1000000000; int main() { ios_base::sync_with_stdio(0); ..
백준 2294 동전2 c++ // dp 동전논리 정리, 규칙성발견 dp테이블 형식
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 0. 규칙성발견 dp 테이블 형식 dp : target 후보들.. ex) dp : 0 1 2 3 4 5 ... 15 (target) 1 5 7(동전들) dp[i][j] : i원 추가시 j원을 만드는 최소 동전갯수 i원들을 추가해나가면서 table을 완성시킨다 => 규칙성발견 1. 동전논리 정리 (j-coin)의 이유 5원일때) dp[12]=d[7]+1 dp[7]의 ..
백준 2293 동전1 c++ // dp, 경우의수는 덧셈이다!
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 의사코드 여기에서 2회차 dp[4]를 보면 1111 112 22 의 경우의 수가 있는데, 1111은 1회차의 dp[4]의 경우의수이고 (1) 11, 2 는 2회차 dp[2]의 경우의수이다. (2) 답은 1+2 = 3 따라서 dp[4]=dp[4](이전회차 경우의수) + dp[4-2(coin)] (현재회차까지 동전으 직전코인 경우의수) 이라는 식이 도출된다. 2. 경우의수는 덧셈이다. dp[4]를..
백준 9251 LCS c++ // DP 푸는방법 : 1. 부분해->전체해 2. DP테이블 그리기
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. DP 테이블 2. 전체코드 #include using namespace std; string s1, s2; int d[1004][1004]; //LCS(i,j) : x1,x2..xi / y1...yj 의 문자열에서 최대부분문자열의 길이 /* * 1. 부분문제로 만들기 * 2. 뒤부터 탐색 * 3. 맨뒤가 같은경우 : LCS(i,j)=LCS(i-1,..
백준 12865 평범한 배낭 c++ // dp는 경우의수로 해결
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. dp는 if(dp[i][j]=~~~) else dp[i][j]=~~~ 형태로 해결하라 2. 전체코드 #include using namespace std; int n, k,ret; int d[104][100000+4]; // i번째 물건까지 왔을때 최대가치, 제한무개 j int weight[100 + 4]; int value[1..
프로그래머스 코딩테스트공부 c++ // dp, 예외처리방법
코딩테스트 연습 - 코딩 테스트 공부 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 삽질과정 n이 150밖에안되서 빡구현인줄 알았는데, 알고보니 dp였다... 1.1 현재값 계산을 위해 이전값을 이용한다 -> dp를 떠올렸어야 했다. 2.주의사항 입력값이 최대값보다 큰경우, 다음계산할 값(코딩력,알고력)이 최대값을 넘을경우, 최대값으로 고정하는 로직이 필요하다. 2. 전체코드 #include using namespace std; int max_alp,max_cop; const int INF=9..
백준 1912 연속합 c++ [hard]// dp, 연속합중 최대값 구하는 방법
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1. 나의틀린풀이 나의틀린풀이 : d[i]=max(d[i-1], d[i-1]+a[2], a[2]_ d[i]=max(포함x, 포함o, 새로운값) 2. 정답코드 2시간고민해도 해결이안되어 정답코드를 보았다..... 일단 외우는게 좋을듯하다. #include using namespace std; long long d[100004], a[100004],n; //d[i]: i자리까지 연속합중 최대값 int main(..
백준 2193 이친수 c++ // dp, overflow 해결방법 long long
https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 1. 문풀과정 int -> overflow(-) long long으로 바꿧더니 통과되었다. 2. 전체코드 #include using namespace std; long long d[94][2], n; //d[i][j] : i자리 이친수의 갯수, j:맨뒤가 j인 이친수의 갯수 int main() { ios_base::sync_with_stdio(0); cin.tie(0); d[1][0] ..