Algorithm/dp

[알고리즘] 416. Partition Equal Subset Sum c++ 리트코드 // 완탐, dp

https://leetcode.com/problems/partition-equal-subset-sum/solutions/1624939/cpython-5-simple-solutions-w-explanation-optimization-from-brute-force-to-dp-to-bitmask/* 완탐-내생각 : 200C1 + 200C2 + 200C3 + ,... + 200C 200 == 2^200 //빡세다..-답 : 이진트리로 쉽게생각하면됨 // num[idx]를 sum1에 넣기 or sum2에 넣기 == 2^200vector nums;class Solution {public: int go(int idx, int sum1, int sum2){ if(idx>=nums.size()){ ..

[알고리즘] leetcode 790. 도미노와 트로미노 타일링 c++ // dp

* 완탐1. 타일의 종류정리하기2. 상태정의 : 열번호, 이전이 완전한지 여부long mod = 1e9+7;int n;class Solution {public: long dfs(int i, int prevgab){ if(i==n && prevgab==0){ //success return 1; } if(i==n && prevgab == 1){ //fail return 0; } if(i>n){ //out of index return 0; } //이전열이 빈칸이있는경우, if(prevgab){ return dfs(i+1,0) ..

[알고리즘] 리트코드 1696. 점프 게임 VI c++ // set, deque dp

https://leetcode.com/problems/jump-game-vi/ * 그냥 dppos N에대해 k번반복문 == O(N * K) -> 100억 -> 터진다.   vector nums; int k;int dp[100000+4];class Solution {public: int dfs(int pos){ //pos에서 그때의 최대점수 if(pos==nums.size()-1){ return nums[pos]; } if(pos>=nums.size()){ //배제 return -987654321; } if(dp[pos]!=-1){ return dp[pos]; } ..

[알고리즘] 리트코드 45. 점프 게임 II c++ // dp, 그리디 bfs

* 나의문제점 : 너무 그리디로 접근하려고함그리디는 최후의 수단임.완탐-> 완탐dp -> pq,정렬 -> 이분탐색 ->  ... -> 그리디 순으로 접근하는게 맞음. * 완탐 * 완탐 + dpint dp[10000+4];vector nums;class Solution {public: int jump(vector& _nums) { memset(dp,-1,sizeof(dp)); nums=_nums; return dfs(0); } int dfs(int pos){ if(pos>=nums.size()-1){ return 0; } if(dp[pos]!=-1) return dp[pos]; dp[..

[알고리즘] 리트코드 최대하위배열 c++ // dp

* 의사코드- dp[i] : i번째까지 부분수열중 최대합2가지 경우의수가 있다.i) 이전값을 버리고, 새로시작하는경우ii) 이전값에서 나를 더하는경우둘중에서 큰값을 택하면된다.* 전체코드int dp[100000+4];class Solution {public: int maxSubArray(vector& nums) { dp[0]=nums[0]; for(int i=1;i * 번외 : 탑다운 dp- 완탐재귀class Solution {public: int maxSubArray(vector& nums) { return solve(nums, 0, false); } int solve(vector& A, int i, bool mustPick) { //..

[알고리즘] 리트코드 고유경로 c++ // dp 모든유형

https://leetcode.com/problems/unique-paths/description/* 완탐class Solution {public: int uniquePaths(int m, int n, int i = 0, int j = 0) { if(i >= m || j >= n) return 0; // reached out of bounds - invalid if(i == m-1 && j == n-1) return 1; // reached the destination - valid solution return uniquePaths(m, n, i..

리트코드 338. Counting Bits c++ // 1의갯수세기, dp, 비트

https://leetcode.com/problems/counting-bits/description/1. 비트 구현 풀이1. 각각 숫자에대해 2진수를 구하면서 1의 갯수를 계산한다.O(n lgn)class Solution {public: vector countBits(int n) { vector ret; for(int i=0;i 2. dp풀이*행동영역 : n이 홀짝일때를 나눠서 규칙을 발견해라!n==0인 기저사례 처리 주의.class Solution {public: vector countBits(int n) { vector dp(n+1,0); if(n==0) return dp; dp[0]=0; dp[1]=1; ..

리트코드 322 코인변경 c++ // 동전dp복습, 리트코드 초기화주의

https://leetcode.com/problems/coin-change/description/1. 리트코드 초기화주의리트코드는 아래 함수를 모든tc에 대해 재실행하는듯하다.따라서 이전 dp값을 그대로 사용해버린다.-> 함수내에서 초기화 해주면 된다.int dp[10000+4]; //dp [i][j] : i원을 달성하는 최소 동전갯수, j번째 동전추가시class Solution {public: int coinChange(vector& coins, int amount) { // memset(dp,0,sizeof(dp)); //리트코드는 전역변수 재사용하기땜에 초기화해줘야하는듯?!! 2. 동전dp복습1. 최솟값 구하기는 dp를 최대값으로 초기화해야 후에 min()함수를 쓰기 쉬워진다!!!..