Mini

* 나의문제점 : 너무 그리디로 접근하려고함그리디는 최후의 수단임.완탐-> 완탐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[..

* 의사코드- 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) { //..

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

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

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()함수를 쓰기 쉬워진다!!!..

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

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

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에 각각 따..