Apes Together Strong.

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

https://leetcode.com/problems/permutations/description/ 정수 배열이 주어질 때, 가능한 모든 조합을 찾아라. 이 문제는 풀이 방법을 외우는 게 좋겠다.각 문제별로 효과적으로 푸는 체계에 대한 정리가 즉, 알고리즘 풀이법이다.  이 문제는 back tracking으로 접근해서 해결 할 수 있고, 직접 구성하기 보다는, 과정에서 오는 값으로 각 원소를 swap해 주면 원하는 결과를 얻을 수 있게 된다.  어떻게? backtrack 과정에서 현재 index와 이동하는 index를 교환한다.  코드 더보기void SwapPermute(vector& vNum, int idx1, int idx2){ if(idx1=vNum.size()) return; if(id..

https://leetcode.com/problems/combination-sum/description/ 정수 배열과 target 값이 주어 질 때, 정수 값의 합이 target이 되는 값들을 찾아라.  이전 문제보다는 종료 조건이 명확하므로, 조금 더 쉽다.  * 종료 조건 * loop의 재시작 index 지점* 다음 back track으로 넘기는 index 위 로직에 유의하면서 코드를 만든다.  코드더보기 void combiBT(int sum, vector>& vRet, vector& vCur, vector& candidates, int idx){ if(sum > combinationSum(vector& candidates, int target) { vector> vRet; vecto..

https://leetcode.com/problems/subsets/description/ 주어진 정수 배열의 모든 subset들을 출력하라. 할 때마다 감이 안잡히는 걸 보니 좋은 문제가 확실!  여러 방법이 있을 수 있겠으나, 일단 back tracking 형식으로 수를 모은다. back tracking의 주요 파라미터는 * 종료 조건 * loop의 재시작 index 지점* 다음 back track으로 넘기는 index 등이다. 따라서 위 세 값을 기본 backtrack 형식에 녹이고 잘 조절하면 답을 찾을 수 있다. 종료 조건 - 3개를 모으면 더 이상 하지 않는다.loop의 재 시작 index 지점 - 전달 받는 index 다음에서 시작한다.다음 backtrack으로 넘기는 index - 루프를 ..

https://leetcode.com/problems/task-scheduler/description/ char 열의 입력이 주어진다. 각 문자는 task를 의미하고, 각 task를 한 후 n 만큼 해당 task를 idle 하고 해야 한다.이때 모든 task를 처리하기 위한 cycle 수를 구하라.  실 사례에 알고리즘을 적용하기 좋은, 괜찮은 문제다.  우선 등장하는 task가 알파벳 대문자로 주어졌다. 같은 task대로 우선 빈도수로 정리를 해 본다. 빈도수와 task처리는 어떤 관계가 있을지 먼저 생각해 본다.idle 시간을 고려하여 많은 빈도수의 task를 먼저 처리해야 최종 cycle이 줄어 든다.  최종 그림은 아래와 같이 설계할 수 있게 된다.  "빈도수가 많은 할 수 있는 상태의 Task를..