Algorithm/dp

백준 1890 점프 c++ // dp, 배열순회dp, dp[next] += dp[cur]

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 1. 의사코드 1. dp도 배열한칸씩 탐색하는것이다. 2. pass 조건을 잘 생각하면 된다. 3. dp[i][j]= 어쩌구 가 아닌 // d[next] +=d[cur] 형태로도 짤수가 있다. 2.전체코드 #include using namespace std; typedef long long ll; ll dp[104][104],a[104][104]; //오큰수의 갯수 [길이][시작숫자] ..

백준 10844 쉬운계단수 c++ // dp

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 의사코드 1. 규칙발견 && 테이블정의 : dp [길이][끝나는숫자] 의 갯수 아래숫자 == 위행의 좌측 + 위행의 우측 이다. 2. 주의사항 %1억할때, (a%1억 + b%1억) %1억해야 올바른 값이 나온다.. 2. 전체코드 #include using namespace std; typedef long long ll; ll d[104][12]; //오큰수의 갯수 [길이][시작숫자] ll n; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for..

백준 11057 오르막수 c++ // dp

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 1. 의사코드 1. 아래칸 = 위칸의 총합인것을 발견할수 있다. 2. 전체코드 #include using namespace std; typedef long long ll; int d[1004][10]; //오큰수의 갯수 [길이][시작숫자] int n; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; fi..

백준 14501 퇴사 c++ // dfs, dp, 트리하부호출 되는경우만 dfs실행

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

프로그래머스 파괴되지않은건물 c++ // dp, 구간합 효율적으로 구하는법

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

프로그래머스 보행자천국 c++ // dp, 경우의수는 dp를 의심하라.

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

백준 2565 전깃줄 c++ // dp, LIS(최장부분증가수열) 풀이

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에 대해 최장부분증가수열 중..

백준 2748 피보나치수2 c++ // 탑다운 dp 형식

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