Mini

https://leetcode.com/problems/pacific-atlantic-water-flow/ * 완탐모든좌표에대해 모든곳을 가보면서 갈수있는지 검사함O(N * M * N * M )int dy[]={1,0,-1,0};int dx[]={0,1,0,-1};vector> heights;vector> ret;int vis[204][204],dp[204][204]; //해당좌표에서 바다로 갈수있는지int n,m;int a,b;class Solution {public: //해당좌표가 pacific바다로 갈수있는지, 좌-우 탐색 void dfs(int y, int x){ // if(x =m || y>=n){ // can go atlantic // b=1; ..

* 완탐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) ..

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/* 내풀이size를 찾고prev값이 없길래 저장하고,제거대상인 노드인경우, prev->next = cur->next로 바꿔줬다.ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ결과 :맨앞의 노드를 제거하는경우 오답이났음.이경우는 head = head -> next를 리턴하면 됬다./** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next..

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

https://leetcode.com/problems/product-of-array-except-self/description/* 풀이1(케이스 분류)경우의수를 나누고구현i) 0의갯수가 0개인경우ii) 0의갯수가 1개인경우iii) 0의갯수가 2개이상인경우class Solution {public: vector productExceptSelf(vector& nums) { vector ret; int zero_count=0; int total_product=1; for(auto num : nums){ if(num==0) zero_count++; else total_product*=num; } ..

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

* 의사코드핵심은 rightNode에 직전우측노드를 캐시해놓고next를 캐시된 그걸로 대입해주는것이다.레벨별로 (rightNode의 초기값은 nullptr 이다.)  * 전체코드class Solution {public: Node* connect(Node* root) { if(!root) return nullptr; //null check 후에 root->next 등에 접근가능함 queue q; q.push(root); while(q.size()){ Node* rightNode = nullptr; for(int i=q.size();i;i--){ //레벨별 구분위한 반복문(1,2,4...) ..

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