Apes Together Strong.

https://leetcode.com/problems/coin-change/description Q. 수 만큼 value인 coins 배열과 amount가 주어질때, coins에서 amount를 맞추기 위한 최소한의 동전수를 찾아라. Solution DP 계열의 좋은 문제. 동전을 치우면서 amount가 되면 과정의 수를 구하고, 그 중 최소를 찾는다. 많이 보는 패턴이다. 로직대로 코드를 만든다. 더보기 int coin(vector& vCache, vector& coins, int amount) { if(amount == 0) return 0; if(vCache[amount-1] >= 0) return vCache[amount-1]; int minT = INT_MAX; for(int k = 0; k <..

https://leetcode.com/problems/longest-increasing-subsequence/description Q. 주어진 정수 배열 nums에서 증가하는 sub sequence의 가장 긴 길이를 찾아라. Solution 특정 조건을 만족하는 단계수를 찾아야 하므로, 전 값보다 지금이 크면 1 증가 시킨다. 배열 끝까지 가면 멈춘다. 현재 수가 조건을 만족해도, 다음 작은 수가 만족하고 또 더 작을 수 있으므로, 이후로 자체 loop를 다 돌아야 한다. 약간 backtrack 스럽기도 하다. 논리대로 코드를 만든다. 더보기 int length_help(vector& vCache, vector& nums, int idx, int last) { if(idx >= nums.size()) r..

https://leetcode.com/problems/perfect-squares/description Q. 정수 n 이 주어질 때, perfect square numbers의 합으로 이 정수를 만든다. 이때 최소의 이 perfect square numbers의 수를 구하라. Solution. 합이 n 이 되어야 하므로, 합이 n 보다 커지는 순간 진행을 멈춘다. 합이 n 이 되면 여지껏 더한 과정의 합계를 구하고, 그 과정의 합계 중, 가장 작은 값을 찾는다. 합은 1부터 n 사이의 값 중, 제곱수로만으로 구성하며, 최적화를 위해 n 보다 이 값이 커지는 순간 바로 loop를 탈출한다. 로직으로 코드를 작성해 본다. 더보기 int numSquaresdp(int n, vector& vCache) { if..

https://leetcode.com/problems/maximum-product-subarray/description Q. 정수배열 nums가 주어질 때, sub array 중 곱이 가장 큰 값을 찾아라. Solution. 우선 간단하게 2중 배열로 접근해 본다. 시작과 끝을 지정하고 과정 중 가장 큰 값만을 기억해서 반환한다. 더보기 int maxProduct(vector& nums) { int ret = INT_MIN; for(int left = 0; left < nums.size(); ++left) { int cur = nums[left]; ret = max(ret, cur); for(int right = left+1; right < nums.size(); ++right) { cur *= nums..

https://leetcode.com/problems/word-break/description Q. 주어진 string s를 wordDict 안의 단어로 자른다고 했을때, 정확하게 잘라지는지 여부를 반환하라. 이때, word Dict안의 단어는 과정에서 여러번 사용 될 수 있다. Solution. 특정 위치에서 캐릭터를 하나 비교하면서 이동한다. 이 과정에서, 현재 맞춰가는 word Dict의 단어가 없다면, 모든 word dict를 대상으로 그 첫 캐릭터가 있는지를 찾는다. 현재 맞춰가는 word dict의 단어가 있다면, 계속 진행하면서 캐릭터가 같거나 아니거나 두 가지만 존재한다. 로직과 캐시에 맞춰 코드를 써 본다. 더보기 bool wordBreak_dp(vector& wordDict, int i..

https://leetcode.com/problems/pascals-triangle/description Q. 아래와 같은 삼각형을 파스칼의 삼각형이라 정의한다. 높이가 주어질 때, 각 행의 값을 구하라. Solution. 이 문제는 직관대로 풀면 된다. 크게 문제될 점은 없어 보인다. 더보기 vector generate(int numRows) { vector vRet; vRet.push_back({ 1 }); for (int q = 1; q < numRows; ++q) { vector line; for (int x = 0; x < q + 1; ++x) { if (x == 0 || x == q) line.push_back(1); else line.push_back(vRet[q - 1][x - 1] + v..

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