DP52 [Leetcode][923] 3Sum With Multiplicity 문제 : leetcode.com/problems/3sum-with-multiplicity/ 0이상 100이하의 정수를 가지는 배열 arr이 주어진다. 서로다른 원소 3개를 더한 값이 target이 되는 조합의 개수를 구하라. 배낭문제로 구할 수 있다. dp[target][cnt] = cnt 개의 원소들을 합해서 target 을 만들 수 있는 경우의 수. i 번째 원소(num)를 기준으로 dp 배열을 갱신해나간다. num + x = target 이라 가정하면 num에 x를 더하면 target을 만들 수 있으므로, x의 경우의 수로 target 인덱스를 갱신할 수 있다. 위의 식에서 num을 우항으로 옮기면 x = target - num이 되므로 dp[target][cnt+1] += dp[target-num.. 2021. 3. 23. [Leetcode][823] Binary Trees With Factors 문제 : leetcode.com/problems/binary-trees-with-factors/ 2이상의 정수 배열 arr이 주어진다. arr 배열의 수들을 노드로 가지는 이진트리를 만들고자 한다. 정수들은 중복으로 사용할 수 있고 각 노드들의 값은 자식노드들의 곱과 같다. 조건을 만족하며 만들 수 있는 이진트리의 개수를 구하라. num으로 만들수 있는 서브트리의 수를 메모이제이션으로 캐싱한다. dp[num] = num을 루트로 하는 이진트리의 갯수. dp[num] = dp[num1] x dp[num2] // num1 x num2 = num 점화식은 위와 같다. 따라서, 곱해서 num이 나오는 num1, num2의 세트 배열을 구해야 된다. 2중 for문을 돌려서 arr배열의 요소들을 곱해서 num이 나.. 2021. 3. 14. [leetcode][329] Longest Increasing Path in a Matrix 문제 : leetcode.com/problems/longest-increasing-path-in-a-matrix/ N*M 정수 배열이 주어질 때, 각 셸에서 상하좌우에 위치한 셸이며 현재 셸의 수보다 높은 수를 가지는 셸로 이동가능하다. 가장 긴 경로 길이를 구하라. DFS + DP 로 풀었다. i번째 셀에서 상하좌우로 이동가능한 곳으로 이동하면서 이동 가능한 경로의 최장 길이를 저장하는 배열(let, dp)을 만든다. dp[i] = min(dp[상하좌우 중 이동가능한 곳]) 위 점화식을 적용하며 dp배열을 dfs로 탐색하면서 세팅한다. dp 배열이 이미 갱신된적 있다면 새로 값을 구하지 않고 해당 값을 사용하여 시간을 줄일 수 있다. 시간복잡도, 공간복잡도 모두 O(NM). 소스코드 : github.c.. 2021. 3. 4. [leetcode][416] Partition Equal Subset Sum 문제 : leetcode.com/problems/partition-equal-subset-sum/ 양의 정수로 이루어진 nums 배열이 주어질 때, 동일한 배열 합을 가지는 두 개의 배열로 분리시킬 수 있는지 구하라. nums 배열의 합을 구한다. 동일한 배열 합을 가질 수 있다는 뜻은 배열 합이 짝수라는 뜻이다. 따라서 만약 홀수라면 false를 반환한다. 배열 합 / 2를 nums 배열을 탐색하면서 요소들의 합으로 만들 수 있는지 판단하고 만들 수 있으면 true, 아니면 false를 반환한다. nums 배열 요소들의 합으로 sum/2 를 구할 수 있는지는 배낭 문제로 풀 수 있다. dp[i][j] = nums[0~i]개의 요소들로 부분집합을 만들 때, 그 요소들의 합으로 j를 만들 수 있는지 여부... 2020. 11. 28. [programmers][찾아라 프로그래밍 마에스터] 사칙연산 문제 : programmers.co.kr/learn/courses/30/lessons/1843 숫자와 연산 기호(+, -)로 이루어진 수식이 주어질 때 괄호를 추가해 그 수식의 계산 결과는 여러가지가 나올 수 있다. 이 때 나올 수 있는 계산 결과 중 최대값을 구하여라. DP로 해결했다. 수식이 문자열 arr로 주어지고 부분문자열 arr[s~e]의 최대값, 최소값을 저장하는 배열을 만든다. 최대값 배열 dMax[s][e] = arr[s~e] 수식의 계산 결과 중 최대값. 최소값 배열 dMin[s][e] = arr[s~e] 수식의 계산 결과 중 최소값. 우리가 알고자 하는 값은 dMax[0][n-1] 인데 최대값을 구하기 위해서는 최소값도 알아야 하기 때문에 dMin 배열도 필요하다. 만약 i 인덱스가 연.. 2020. 9. 13. [leetcode][309] Best Time to Buy and Sell Stock with Cooldown 문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 주식가격이 주어질 때 최대 이익을 구하라. 동시에 여러개의 교환은 진행될 수 없다. (즉, 주식을 샀으면 팔때까지 다른 주식을 사고팔수없다.) 주식을 팔았을 때 다음날엔 어떠한 거래도 할 수 없다. (쿨다운 1일) 오랜만에 dfs + dp(memoization). top-down 방식으로 풀었다. dfs(index)를 stock[index~]을 사고 팔 때 얻을 수 있는 최대이익을 가져오는 함수라하자. 이 값은 index에서 어떠한 거래도 하지 않았을 때(dfs(index+1))와 index를 샀을때로 나뉠 수 있다. index 번째 주식을 구입했으면 팔아야 .. 2020. 8. 1. 이전 1 2 3 4 5 6 7 ··· 9 다음