Mini

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. 의사코드 def dfs(n, sm): //dfs(인덱스, 현재돈) global ans # [1] 종료조건: 가능한 n을 종료에 관련된것으로 정의! if n>=N: ans = max(ans, sm) return # [2] 하부호출: 화살표 개수만큼 호출 if n+T[n] n) return; //마지막 수업을 들을수 없는경우(막날수업이 2일이상 소요되는경우) dfs(day+v1[day].first, money + v1[day].second); //해당강의선택 dfs(day+1, money); //미선택 } int main() { c..

https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 구간합 효율적으로 구하는법 1.1 1차원예시 [ 0 , 0 , 0 , 0 , 0] 에 0~3idx까지 a를 더하고싶다 1. [a, 0, 0, 0, -a] 배열 생성 2. ->쪽으로 누적합을구함 3. a배열과 원본배열을 더함. 끝. 1.2 2차원예시 네모친구간에 a를 더하고싶다. 1. 좌측위, 우측아래에 a를 더하고 / 우측위, 좌측아래에 -a를 더한다. 2. ->, 아래쪽으로 누적합을구함 3..

https://school.programmers.co.kr/learn/courses/30/lessons/1832 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1. 의사코드 (별:내위치)4가지 경우의 수가 나온다.이전 map의 상황에 따라 조건문을 분기한다 2. 전체코드#include using namespace std;int MOD = 20170805;int d[504][504][2]; //좌표, 0-> 1아래// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.int solution(int m, int n, vector> city_map)..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 1. LIS(최장부분증가수열) 풀이 ex) 수열 / dp값 /해당경우의수 3 / 1 / 3 5 / 2 / 3 5 1 / 1 /1 6 / 3 /3 5 6 4 / 2 /3 4 또는 1 4 일반화 : 앞에서 자기보다 작은게있다 -> 그 dp값 중 최대값 +1 행동영역 : dp문제를 LIS 문제로 해결할수 있을지 시험해보자 2. 의사코드 1. first에 대해 정렬후 2. second에 대해 최장부분증가수열 중..

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]를 구하는 경우의수 : ..