Apes Together Strong.

Q. nums의 계단이 주어질 때, 현재 위치의 nums 값이 해당 위치에서 점프 할 수 있는 계단 수이다. 이때 마지막 계단에 도달 가능한지 여부를 반환하라. Solution. 일단 기본 로직 자체는 큰 복잡함이 없다. 특정 위치에서 가능한 모든 위치를 뛰어 본다. 그리고 끝에 도달하면 성공 실패 여부를 기록하고, 캐싱한다. 처음으로 되돌아와 계속 확인시 이 캐시를 확인한다. 기본적인 dp 문제다. 더보기 bool help(vector& vCache, vector& nums, int idx) { if(idx == nums.size()-1) return true; if(vCache[idx] >= 0) return vCache[idx]==1; for(int q = 1; q = nums.size()) bre..

https://leetcode.com/problems/jump-game-ii/description Q. nums의 계단이 주어진다. 이때 nums.size()-1 의 계단에 도달하려고 한다. 계단은 nums[i] 위치에서 0 ~ nums[i] 위치만큼 뛸 수 있다. 이때 도달가능한 최소 단계수를 구하라. Solution. DP 에서 많이 보이는 계단 jump 문제다. 수식을 잘 세우면 어려울 것이 없다. 특정 계단에 도달해서 0 ~ 현재 값 까지 점프 가능하다. 0 이면 점프하지 않으므로 1 부터점프하고, 도달하려는 다음 계단이 전체 nums 의 크기를 넘으면 하지 않는다. 이 단계수를 더하고 그 중 최대를 찾는다. 로직대로 코드를 만든다. 더보기 int helper(vector& vCache, vect..

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/construct-binary-tree-from-preorder-and-inorder-traversal/description Q. Preorder와 Inorder 순회 결과 배열로 tree를 구성하라.  Solution.  Tree 구성파트의 좋은 문제.  pre order는 self(mid), left, right 순서대로 traverse 하므로, tree를 해당 순서대로 visit 하는 그대로의 배열 결과가 된다.  따라서 depth first search 하면서 self, left, right를 배열 순서대로 값이 tree에 매칭하면 된다.   하지만 이것으로는 많은 다양한 트리가 만들어 질수 있으므로, 여기서 inorder traverse 정보..

https://leetcode.com/problems/rotting-oranges/description LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Q. 주어진 grid에서 각 숫자는 다음을 의미한다. 이때 모든 orange가 rotten 상태로 변화는 시간(단계 수)을 구하라. Solution. 위 문제인 지나갈 수 있는 길에서 모든 길에 도달하는 단계 ..

https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/description LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Q. n개의 도시수가 있고, 각 도시 노드의 연결 데이터가 주어진다. 이때 어떤 도시에서든, 0 도시에 도달 할 수 있도록, 변경해야 하는 ..

https://leetcode.com/problems/longest-common-subsequence/description LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Q. text1, text2가 주어질때, 두 text의 가장 긴 공통 subsequence string의 길이를 구하라. Solution. 우선 매우 좋은 문제다. 대놓고 이런 식으로 해결하..

https://leetcode.com/problems/path-sum-iii/description Path Sum III - LeetCode Can you solve this real interview question? Path Sum III - Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum. The path does not need to start or end at the roo leetcode.com Q. Tree 노드가 주어질때, 해당 노드의 leaf를 향하는 연속된 구간합이 targetS..

https://leetcode.com/problems/subarray-sum-equals-k/description/ Subarray Sum Equals K - LeetCode Can you solve this real interview question? Subarray Sum Equals K - Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k. A subarray is a contiguous non-empty sequence of elements within an array. leetcode.com Q. 주어진 배열 nums에서 연속된 subArray의 합이 ..

https://leetcode.com/problems/decode-string/description Decode String - LeetCode Can you solve this real interview question? Decode String - Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is g leetcode.com Q. k[string] 꼴의 입력이 들어올때, string을 k번 출력하게 디코딩 하..