Bansanka

https://leetcode.com/problems/longest-increasing-subsequence/ Longest Increasing Subsequence - LeetCode 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 /** * @param {number[]} nums * @return {number} */ var lengthOfLIS = function(nums) { const length = nums.length; const dp = Array.from({le..

DP를 이용하여 문제를 풀었다..! 우선 열의 개수는 무조건 4개이다. 시간은 충분할 것 같다..! 3중 for문을 이용하도록 하자. i = 1부터 시작하여, i - 1 행의 수를 모두 비교해야 한다. 단, j != k여야 같은 열 번호의 수를 선택하지 않는다. m은 현재 행의 위치에서 이전 행의 각 열을 더했을 때 가장 큰 값을 저장하는 변수이다. 그리고 이전의 최댓값이 누적이 되므로 마지막 행에서 최댓값만 찾으면 된다..! #include #include #include using namespace std; int solution(vector land) { int answer = 0, m = 0; for(int i = 1; i < land.size(); i++) { for(int j = 0; j < ..

피보나치 수열을 DP로 풀었다. 피보나치 수열에 관한 문제는 재귀, DP, 반복문을 사용하여 풀 수 있는데, 시간을 고려해야 하는 경우는 대부분 DP를 이용하면 풀 수 있다. 배열을 이용하여 F(n) = F(n - 1) + F(n - 2) 의 값을 저장한다. 반복문을 돌면서 계속해서 F(n - 1), F(n - 2)의 값을 가져오기 때문에 재귀보다 빠르게 풀 수 있다. #include #include using namespace std; int solution(int n) { int answer = 0; int num[100001] = {0, }; num[0] = 0; num[1] = 1; for(int i = 2; i