Apes Together Strong.

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

https://leetcode.com/problems/kth-largest-element-in-an-array/description/ 주어진 정수 배열에서 k 번째로 큰 수를 찾아라. k번째로 큰 수는 minPriority Queue 에 배열을 넣고, 큐 사이즈가 k 가 될때까지 큐를 pop한다. 그리되면 사이즈 k 보다 작은 값들은 pop되고 k 개수 만큼 큰 값들만 남게 된다.  그 중 top이 k 번째로 큰 값이 된다.  코드 int findKthLargest(vector& nums, int k) { priority_queue, greater > minPQ; for (int q = 0; q k) minPQ.pop(); return minPQ.top();}   결과

https://leetcode.com/problems/k-closest-points-to-origin/description/ 2차원의 정점 정보가 주어질 때 원점에서 k 번째까지 가까운 점들을 찾아라.  priory queue를 구성할 줄 안다면 어렵지 않은 문제.  거리, index의 pair data로 queue를 구성해야 한다. 다만 여기서 거리는 크기의 비교로만 쓰이므로, root 연산은 해지 않아도 된다.(정확할 필요가 없다) 코드더보기vector> kClosest(vector>& points, int k) { priority_queue, vector>, greater>> pq; for (int q = 0; q > vRet; for (int q = k; q > 0; --q) ..

https://leetcode.com/problems/last-stone-weight/description/ 주어진 정수 배열은 돌의 무게을 의미한다. 가장 무거운 두개를 서로 부딪힌다. 무게가 같으면 사라진다. 다르면, 그 차가 남는다.  마지막 남은 돌의 무게를 구하라. 이거는 easy 난이도가 맞다. 직관대로 풀어 준다.  코드 더보기int lastStoneWeight(vector& stones) { priority_queue pqBuff; for (int q = 0; q = 2) { int first = pqBuff.top(); pqBuff.pop(); int second = pqBuff.top(); pqBuff.pop(); if (first ..

https://leetcode.com/problems/kth-largest-element-in-a-stream/description/정수형 입력 데이터가 주어질 때, k 번째로 큰 값을 반환하도록 하라. 조금 함정이 있는 문제다. 데이터가 얼마나 있는지, 다른 데이터는 무엇인지, 사실 문제는 관심없다. 오로지 반환으로 원하는 것은 k 번째 큰 값이다.  우선 map 등의 정렬된 hash등으로 값을 가질 수 있다.모든 값이 보존되며, add 시 정렬로 인해, O(logN) 시간이 소요 된다. 하지만 검색 시도 O(logN)이 소요된다. ( O(1) 을 원하면 hash_map 을 써야 하지만, 정렬이 지원되지 않는다. )이것으로도 충분히 문제는 풀릴 것이다.  다음으로 priority queue를 생각해 볼..

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/ Preorder와 Inorder traverse  정보가 주어질 때, 전체 tree를 구성하라. 우선 InOrder와 PreOrder에 대해 다시 정리할 필요가 있다.  DFS 그 순서 그대로 tree를 접근한다면, PreOrder 방식이라고 할 수 있다.어느 노드의 child를 어떤 식으로 attach하는지 정보를 얻기 위해 InOrder가 필요하다. inOrder는 이 값들을 tree의 밸런스 정보와 함께 가지고 있다. 즉, 특정 값이 inOrder에 존재 한다면, inOrder에서 해당 값보다 작은 index는 왼쪽 트리..

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/ 주어진 tree에서 k 번째로 작은 값을 찾아 반환하라.  2진트리에서 InOrder traverse가 기본적으로 정렬을 의미함을 이해 한다.  따라서 InOrder traverse했을 때, k 번째로 접근하는 node 값을 찾으면 된다.  코드 더보기bool kthSmallestInOrder(TreeNode* node, int& k, int& outValue){ if (node == nullptr) return false; if (kthSmallestInOrder(node->left, k, outValue)) return true; ..