Mini

https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net #include using namespace std; long long dp[91], n; long long fibo(long long idx) { //기저사례 if (idx == 0 || idx == 1) return idx; //메모 long long& ret = dp[idx]; if (ret) return ret; //값이 있으면 바로리턴 //로직 retu..

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

https://www.acmicpc.net/problem/2294 2294번: 동전 2첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어www.acmicpc.net0. 규칙성발견 dp 테이블 형식dp : target후보들..ex) dp : 0 1 2 3 4 5 ... 15 (target)157(동전들)dp[i][j] : i원 추가시 j원을 만드는 최소 동전갯수i원들을 추가해나가면서 table을 완성시킨다 => 규칙성발견  1. 동전논리 정리 (j-coin)의 이유5원일때)dp[12]=d[7]+1dp[7]의 경우에서 뒤에 5원만(1..

https://www.acmicpc.net/problem/2293 2293번: 동전 1첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.www.acmicpc.net1. 의사코드여기에서 2회차 dp[4]를 보면111111222 의 경우의 수가 있는데,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]를 구하는 경우의수 : ..

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

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.net1. dp는 if(dp[i][j]=~~~)else dp[i][j]=~~~ 형태로 해결하라 2. 전체코드#include using namespace std;int n, k,ret;int d[104][100000+4]; // i번째 물건까지 왔을때 최대가치, 제한무개 jint weight[100 + 4];int value[100 + 4];i..

코딩테스트 연습 - 코딩 테스트 공부 | 프로그래머스 스쿨 (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..

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