Apes Together Strong.

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/course-schedule/description Q. 전체 코스의 수 numCourses와 해당 코스의 선학습 데이터 prerequisites 가 주어질 때, 전체 코스를 수강할 수 있는지 여부를 반환하라.  Solution.   코스 및 경로 데이터를 우선, 노드 기반으로 정리한다.   특정 코스를 듣기 시작해서 추가 경로가 없는 마지막 코스노드까지 중복해서 방문하는 노드가 있으면, 사이클이 있는 것이므로, 수강 불가능 한 것이다.   이 과정을 각 시작 코스별로 수행 해 주며, 불가능한 코스가 하나라도 생긴다면, 전체 수강 불가능하다고 하겠다.    그래프 방문 + back track(방문 check) 비슷하게 접근하면 될 것 같다.   이때, ..

https://leetcode.com/problems/number-of-islands/description Q. grid가 주어질 때, 섬으로 구분되어 질 수 있는 1 영역의 수를 구하라.   Solution.   그래프 관련 문제는 노드 방문을 어떤 방식으로 하고, 관련 처리를 어떻게 할지 등이 대부분이다.   이 문제에서는 모든 cell이 노드 진입로가 될 수 있다. 한번 진입하면 해당 진입 노드로 갈 수 있는 영역은 모두 방문처리 해 주고,  최종 몇 회 진입 할 수 있는지 찾는 문제다.   이 경우 방문은 DFS, BFS 모두 유효하다. 재 방문 하지 않도록 flag처리를 잘 하자. 더보기 void BFS(vector>& grid, int ix, int iy, vector& vVisit){ ..

https://leetcode.com/problems/partition-equal-subset-sum/description Q. 1부터 200까지의 수 배열 nums가 있을 때, 이 배열의 각기 합을 같게 만들어 2개로 분할하는 subset이 존재하는지 여부를 반환하라. Solution. 예제에서 보는 바와 같이, 연속되는지 여부에 관계없이 2개로 그 합이 같도록 분할되면 될 것이다. 우선 전체 합이 필요하다. 그 후 반으로 나눈 값을 배열을 순차적으로 지나며 그 값으로 빼거나, 말거나 계산 값을 끝까지 지속하며, 이 값이 0이 되면, 이미 반이 된 값이므로, 나눠진다는 것이고, 그렇지 않다면 나눠지지 않는다는 것이다. 이때, 양수입력만 있으므로, 도중에 - 값이 되면 바로 실패로 간주 할 수 있을 것이..

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