Apes Together Strong.

https://leetcode.com/problems/edit-distance/description Q. 주어진 word1과 word2에 대해서 아래와 같이 수정을 할 수 있다고 하면, word1을 word2로 바꾸는데 필요한 최소한의 연산수를 구하라. Insert 연산, Delete 연산, Replace 연산. Solution. 우선 풀이 전에, 이 문제는 충분히 좋은 문제다. 실생활에 많이 적용될 여지가 있다. 문제에서 필요한 것은 연산을 가한 횟수다. 따라서 string의 실제 변환에는 관심이 없다. 또한 코드 로직은 사람처럼 직관적일 수 없으므로, 하나 하나 다 해 보면서 결과를 확인해 봐야 한다, 우선, 특정 위치에서 어떤 것들이 가능한지 생각해 보자. 일단 특정 위치의 두 문장의 캐릭터가 같다..

https://leetcode.com/problems/climbing-stairs/description Q. 한번에 하나 혹은 두개의 계단을 올라갈 수 있을때, n 개의 계단을 모두 오르는 경우의 수를 계산하라. Solution. 완료 조건 경우의 수를 찾는 문제. DP의 일반적 문제 중의 하나다. 특정 위치에서 하나의 계단을 밟아 나가거나, 두개의 개단을 밟아 나가거나 두개의 선택만이 존재 한다. 종료 조건은? 다 올라가는 것이므로, 현재 계단이 n 보다 크거나 같으면 1회 달성 한 것이다. 로직대로 코드를 써 주고 벡터 캐시로 최적화를 한다. 더보기 int climbStairs_helper(int n, vector& vCache, int cur) { if(cur >= n) return 1; if(vC..

https://leetcode.com/problems/minimum-path-sum/description Q. m x n의 grid가 주어질 때, 우하단에 도달하는 경로 중 최소 값을 구하라. 이때 우측과 하단으로 한칸씩만 이동할 수 있다. Solution 문제에 의해 특정 위치에서 우하단으로 가는 경로는 우측 또는 하단으로 갈 수 있을 때, f(최소우측경로) + f(최소하단경로) 가 된다. 우하단에 도달하면 그 위치 값만 반환하면 된다. 로직으로 써 본다. 더보기 int minPS_dp(vector& grid, int x, int y, vector& vCache) { int h = grid.size(); int w = grid[0].size(); if(x == w-1 && y == h-1) return..

https://leetcode.com/problems/longest-valid-parentheses/description Q. 주어진 string s 에서 (와 )의 parentheses 쌍이 맞는 최대 길이를 찾아라. Solution. 직관적으로 우선 생각해 본다. 한 string에서 시작점을 기준으로 어디까지 parentheses정의를 만족하나 확인한다. 그리고 그 최대 길이를 udpate 한다. 도중에 만족하지 않으면, 그 다음 index의 시작점에서 다시 체크를 시작한다. 더보기 int longestValidParentheses(string s) { int maxLen = 0; int idxStart = -1; queue qBuff; for (int k = 0; k < s.size(); ++k) ..

https://leetcode.com/problems/longest-palindromic-substring/description Q. 주어진 string s의 가장 긴 palindrome이 되는 sub string 을 찾아라. Solution. 우선 직관적으로 생각해 보자. string에서 시작점과 끝점을 정하고 해당 sub string이 palindrom이 되는지 체크한다. 직관적이다. 코드로 옮겨 보자. 더보기 bool IsPalindrome(string& s) { for(int q = 0; q < s.size()/2; ++q) { if(s[q] != s[ s.size()-1-q ]) return false; } return true; } public: string longestPalindrome(s..

https://leetcode.com/problems/diameter-of-binary-tree/description Q. 주어진 Binary Tree의 최대 경로의 길이를 찾아라. 이 최대 경로는 root를 지나지 않을 수 있다. Solution. 우선 Binary Tree에서 최대 경로에 대한 정의를 찾아 본다. 특정 노드를 기준으로 left와 right를 연결한 길이가 최대가되면 그 경로를 최대 경로라 정의한다. 4 - 2 - 1 - 3 혹은 5 - 2 - 1- 3 이 최대 경로가 된다. 위 트리의 최대 경로는 보는 바와 같이 root를 지나지 않는다. -1 0 6 9 -9 -7 -6 9 -2 혹은 -4 6 6 9 -9 -7 -6 9 -2이 최대 경로가 된다. 그럼 이 경로를 어떻게 구할까. 특정 ..

https://leetcode.com/problems/path-sum-iii/description Q. 주어진 노드에서 경로합이 targetSum이 되는 모든 경로의 수를 구하라. 이때 경로는 특정 노드에서 아래 방향으로만 해당된다. Solution. 특정 노드 root를 기준으로 먼저 생각해 보자. root 에서 아래로 방문하는 노드의 값을 누적한 후, 그 값이 targetSum과 같으면 root에서 해당되는 경로가 있는 것이다. 이 연산을 모든 노드에 대해 수행한다. 더보기 void pathSum_dfs(TreeNode* node, int targetSum, long sum, int& pathCnt, unordered_set& setChecked) { if(node == NULL) return; su..

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description Q. 주어진 binary search tree에서 k 번째로 작은 원소를 찾아 반환하라. Solution k 가 tree의 원소 수 보다 작은 것이 문제에서 보장되므로, 예외처리는 필요 없다. 또한 inoder traverse의 결과가 오름차순 정렬이라는 것도 알고 있다. 따라서 inorder traverse하면서 k번째를 check 한다. 더보기 void inorder_BT(TreeNode* node, int k, int& idx, int& ret) { if(node == NULL) return; if(idx >= k) return; inorder_BT(node->left, ..

https://leetcode.com/problems/invert-binary-tree/description Q. 주어진 tree를 좌우전환 하여라. Solution. 단순히 node의 자식들을 반대로 연결한다. TreeNode* invertTreeBT(TreeNode* node) { if(node == NULL) return NULL; TreeNode* leftTemp = node->left; node->left = invertTreeBT(node->right); node->right = invertTreeBT(leftTemp); return node; } public: TreeNode* invertTree(TreeNode* root) { return invertTreeBT(root); } 결과.

Q. 주어진 binary tree를 linked list와 같은 flatten 하여라. 이때 tree를 pre-order 순회한 결과를 flatten 하여라. Solution Tree 에 대한 이해가 충분하면 역시 어렵지 않으리라 생각된다. 우선 tree를 pre order 순회하면서 그 결과를 특정 버퍼에 넣고, 버퍼를 순서대로 순회하면서 오른쪽 leaf 에만 child 를 attach 한다. 로직대로 코드를 만들어 본다. 더보기 // vector를 순회하며 우측에만 child를 attach 한다. TreeNode* build_flatten(vector& vNodes, int& idx) { if (idx >= vNodes.size()) return NULL; TreeNode* node = vNodes[..