Algorithm/dp

리트코드 주식을사고파는가장좋은시기 c++ // 이분탐색(슬라이딩윈도)+그리디, dp

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/1. 이분탐색(슬라이딩윈도)+그리디nC2완탐은 불가능함.이분탐색? st=0, en=n-1? -> 자꾸 분기가 일어남 -> 슬라이딩 윈도우?1.1. buy(st)=0, sell(en)=1로 시작하고음수이면, 비싸게 사고, 싸게 판다는 뜻인데가격이 싼날에 사면 된다.양수면, 정답갱신후 추가 탐색한다.1.2. 부분최적해가 전체최적해가 된다.(그리디)class Solution {public: int maxProfit(vector& prices) { int ret=0; int sell=0,buy=0; int n=prices.size(); if(n==..

백준 1932 정수삼각형 c++ // 재귀dp, 1,2,3,4..n 개 입력받는법

https://www.acmicpc.net/problem/1932 1. 1,2,3,4..n 개 입력받는법int n; cin >> n; for (int i = 1; i > dp[i][j]; } }j 2. 의사코드1. 아래, 우아래 로 이동 하는 dfs2. 그때 상태를 dp에저장 : 그상태일때 최대값3. 기저사례1 : 정상적으로 n번째 노드에 노착기저사례2 : x가 아래 그림과같이 빨간x쳐진곳으로 간경우 -> 비정상 -> 매우작은값을리턴시켜 배제시킴.                     - 특징발견 : x>y인 경우가 그러함. 3. 전체코드#include using namespace std;int n,m,a[504][504];int dp[504][504];//상태 : 좌표 : 그때 합 최대값int dfs(..

프로그래머스 주사위고르기 c++ // 빡구현, 완탐, dp, 이분탐색, 발상 아이디어

https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 의사코드 고민완탐? : 10C5 * 6^5 * 10C5 * 6^5 -> 시간초과상태기반 dp? : (A가고른주사위 bit, B가고른주사위 bit) : 그떄 A의 승수 같은 상태가 중복되지 않는다... and 매 상태마다 6^5 * 6^5 -> 완탐이나 마찬가지임 * dp아이디어 : 메모리, 자료구조(배열)을 이용해 시간복잡도를 줄이자.각 경우마다 주사위의 합들을 arrA, arrB에  각각 따..

백준 4811 알약 c++ // 재귀dp, 경우의수는 +

https://www.acmicpc.net/problem/4811 1.의사코드1. 알약을 1개꺼낸 경우 vs 반개꺼낸경우 계속 2분탐색이다.2. 완탐? -> 2^30 -> 불가 -> dp?3. 상태 : 큰알약갯수, 작은알약갯수 : 그때의 경우의수4. 경우의수는 기저사례 -> return 1, 후 +하면 된다.아래 그림과 같이 1이 리턴되고 거꾸로 타고오면서 그런 경우의 수가 모두 더해진다. 2. 전체코드#include using namespace std;typedef long long ll;ll dp[34][34];//큰알약남은갯수, 반알약남은갯수 : 그상태일때, 경우의수ll dfs(int a, int b) { if (a==0 && b==0) return 1; if (dp[a][b] != -1..

백준 1103 게임 c++ // 경우의수 dp, 사이클검사방법

https://www.acmicpc.net/problem/1103 1. 사이클검사방법1. 방문한 좌표를 재방문했으면, 사이클이 있는것이다!! 2.중앙의 y,x에서 출발한경우, vis[y][x]=1 걸고들어간다탐색하면서 봤는데 vis[y][x]=1 이면, 빨간색경로로 갔다온것이다, 싸이클이 있는것임.이후, 원복을 해줘야함!원복안하는경우 : 우측의 2가 vis되있고, 다른경로(빨간경로)에서 2를 방문하면 사이클이 있는것으로 판단해버린다... 3. 의사코드if(visited) -1출력, 종료 visited = 1;상하좌우 탐색visited = 0;  2. 시행착오1. -1검사과정에서 상하좌우 같은수가 있으면 -1을 리턴하도록 했는데 이경우는1 11 1 에서는 먹히지만3 5 5 25 5 5 52 5 5 3 에서..

백준 17070 파이프옮기기 1,2 c++ // 재귀dp

https://www.acmicpc.net/problem/170691. 의사코드1. dfs("끝" 좌표, 상태 :가로 세로 대각) 의 상태 기록이 필요함2. 기저사례 : 범위밖, 벽이있음 -> 해당 경우의수는 "0" 개로 처리 -> 배제시키기3. 좌표가 n-1인경우 -> 정답 -> 1개의 정답으로 처리.4. 논리부분 : 케이스에 맞게 [초기화, 논리, 리턴] 해주면 끝. 2. 시행착오1. 상태가 대각(2)일때 y-1, x-1도 벽인지 체크해줘야함2. dfs 호출부에서 (0,0,0)이 아닌 (0,1,0) 으로 호출해야함 // 끝좌표가 (0, 1) 이므로. 3. 전체코드#include using namespace std;typedef long long ll;ll n, a[33][33], dp[33][33][..

백준 1149 RGB거리 c++ // 재귀dp, 추가정보 필요시 해결방법

https://www.acmicpc.net/problem/1149 1. 의사코드1. 완탐 -> 3C1 을 N번반복 -> 3^1000 -> 불가2. dp? 3. 상태 : [idx][색깔] 1000(n개)*3(빨,노,파)에 가능!3.5 값 : 그 상태일때, 비용의 최소값4. 완탐기반으로, 위에서 칠한색을 제외한 2개중 최소값을 dp에 저장함. 2. 추가정보 필요시 해결방법위에서 무슨색을 칠했는지 알아야하기때문에 , b[idx] 배열에 기록해둠. 3. 전체코드#include typedef long long ll;using namespace std;int n, k,dp[1004][3],a[1004][3];int b[1004]; //해당 idx에 어느색을 칠했는지int dfs(int idx, int color) ..

백준 12865 평범한베낭 c++ // 재귀dp, 불가능한경우를 먼저 ret하라

https://www.acmicpc.net/problem/12865 1. 불가능한경우를 먼저 ret하라int dfs(int idx, int weight) { //기저사례 //!조건불만족하면 리턴! 이 return이 먼저와야함!! -> 그래야 배제가능. // 안그러면, 조건불만족 인데 idx==n인 경우도 유효한 경우로 카운팅됨. if (weight > k) { return -987654321; } if (idx == n) { return 0; }idx==n return 0이 먼저오는 경우 : 조건불만족인데 n에 도달한경우도 유효한 경로로 카운팅이 되어버린다.. 2. 의사코드0 번베낭을 담는다, 안담는다1번 베낭을 담는다 안담는다 ... 로 완탐하고dp[idx][weight] 의 상태를 배열에 저장해..