Apes Together Strong.

https://leetcode.com/problems/house-robber-ii/description/ 주어진 정수 배열을 각 집과 그 집에서 rob 할수 있는 value라고 한다. 이때 도둑은 인접해 있는 집은 털수가 없다. 또한 집들이 원형으로 연결되어 있다고 가정한다.따라서 마지막 집과 첫 집은 연결되어 있다.  도둑이 훔칠 수 있는 최대값을 찾아라. House Robber I 문제의 변형이다.  특정 위치에서 idx+2 혹은 idx+3에 접근 할 수 있다. 다만, 0에서 시작했으면 size()-1 까지만 접근 가능하다. 따라서 캐시 버퍼를 만들때 이 경우를 고려한다. 따라서 size() x 2의 캐시 사이즈가 필요하다. 또한 시작 시, 첫 집에서 시작 할 수 있고, 이때는 마지막 집은 접근 할 ..

https://leetcode.com/problems/house-robber/description/ 정수 배열이 주어지고 이것은 각 집과 훔칠 수 있는 돈을 의미한다.도둑은 인접한 집은 방문할 수 없다. 모든 집을 털었을 때, 기대할 수 있는 최대 값을 찾아라. 아래 문제에 비유적 설명을 덧댄 문제.https://leetcode.com/problems/min-cost-climbing-stairs/description/ 인접해서 방문 할 수 없으므로, 특정 위치에서 기대 할수 있는 최대 값은nums[idx] + max(idx+1 이동, idx+2 이동)일 것이다.  코드 더보기 int minCostDP(vector& vCache, int idx, vector& cost){ if(idx >= cost...

https://leetcode.com/problems/min-cost-climbing-stairs/description/ 정수배열 cost는 각 계단을 밟는 비용을 의미한다. 한번에 계단은 하나 혹은 두개씩 밟을 수 있다.시작은 0이나 1 위치에서 시작 할 수 있다.이때, 최고 높은 계단에 도달하기 위한 최소 비용을 구하라.   특정 위치에서 비용은 cost[idx] + min(1단계, 2단계) 일 것이다.  위를 기준으로 코드를 만든다. 코드 더보기int minCostDP(vector& vCache, int idx, vector& cost){ if(idx >= cost.size()) return 0; if(vCache[idx] >= 0) return vCache[id..

https://leetcode.com/problems/climbing-stairs/description/ 한번에 1개 혹은 2개의 계단을 밟을 수 있다고 할 때, 계단을 다 오를 모든 경우의 수를 찾아라. 리마인드 하듯이 문제를 풀어 본다.  DP 문제는 복합적인 듯한 문제를 단일 단계로 해석하는 것이 중요하다.  한 단계에서 1개 혹은 2개만 올라 갈 수 있다. 또한 끝까지 오르면 그만 둔다. 따라서 특정 단계에서 오른 횟수를 구한다면, 그 값을 재활용 할 수 있다.(마지막 계단 바로 앞에서는 1회 두 번, 2회 한번의 두 가지 경우가 존재하고, 이것은 이 전에 무엇을 했던 동일하다.) 코드 더보기int climb(vector& vCache, int idx, int n){ if(idx >= n) ..

https://leetcode.com/problems/n-queens/description/ 아래와 같은 N-Queens 를 만든다고 할때, n 이 주어지면 이에 가능한 N-Queens를 모두 찾아라. 문제 자체는 쉽다.  매 칸당 Queen을 놓을 수 있다면, 놓거나 아니면 놓지 않는다.  코드 더보기bool CanPlace(int idx, const vector& vCur, int n){ int y = idx / n; int x = idx % n; // check H for(int h = 0; h =0) { if(vCur[yy--][xx++] == 'Q') return false; } // check to LB xx = x-1..

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/ 2-9 까지의 다이얼을 누른다고 할 때, 매칭 가든한 모든 문자열을 찾아라. BackTracking의 고전과도 같은 문제. depth가 더해 지면서 진행 하는 index 는 찾고자 하는 input digit이다. 이 데이터를 가지고 가질 수 있는 문자를 문자열의 길이가 digits만큼 되면 반환 buff에 넣는다.  코드 더보기void letterCombinationsBT(const string& digits, map>& buff, vector& vOut, string& cur){ if (cur.size() >= digits.size()) { ..

https://leetcode.com/problems/palindrome-partitioning/description/ 문자열이 주어질 때, palindrome한 sub string의 모음을 찾아라.  BackTrack의 원리 자체는 같지만, 구성과 진행 조건이 조금 다르다.  실제로 string을 cut 해 보며 이것이 palindrome인지 확인하고, 그럴 때만 진행해 나간다. 나머지 조건은 대동소이 하다. 코드더보기 bool IsPalindrome(const string& s){ if (s.size() >& vRet, vector& vCur, const string& s, int idx){ if (idx >= s.size()) { vRet.push_back(vCur); ..

https://leetcode.com/problems/word-search/description/ m x n grid의 문자열이 주어진다. 이 안에서 특정 word가 존재하는지 여부를 확인하라.  맞는 단어를 하나 하나 확인해 가며 진행한다. 다만 시작 지점이 모든 영역이다. 로직 자체는 간단하다. 코드 더보기bool existBT(int idx, vector& vVisit, vector>& board, string word, int idxW){ int H = board.size(); int W = board[0].size(); char target = word[idxW]; int iy = idx / W; int ix = idx % W; char cur = board[iy..

https://leetcode.com/problems/combination-sum-ii/description/ 주어진 정수 배열의 합이 target이 되는 조합을 찾아라. 이때 정수에는 중복값이 있을 수 있다. 결과에서 중복 결과를 제거하라.  Subset II와 거의 같은 풀이의 문제. 같은 로직으로 중복을 제거 할 수 있다.  코드 더보기void combinationSum2BT(int idx, vector>& vRet, vector& vCur, vector& candidates, int target){ if(target idx && candidates[q-1]==candidates[q]) continue; vCur.push_back(candidates[q]); ..

https://leetcode.com/problems/subsets-ii/description/ 정수 배열이 주어 질 때, 가능한 한 모든 sub set을 찾아라. 이때 중복이 없도록 하라. subset 1과 기본적으로 동일하지만, input에 중복값이 주어진다. 따라서 결과에서는 주어진 input을 제외하고 다른 중복이 있으면 안된다. 1, 22, 1 등은 허용하지 않는다.  1과 기본적으로 같은 흐름으로 하되, 결과에 중복만 set으로 filter 해 보았다.  코드더보기void subsetsWithDupBT(int idx, vector>& vRet, vector& vCur, vector& nums, unordered_set& sBuff){ string temp; for(int q = 0;..