본문 바로가기

DP52

[Leetcode] 2218. Maximum Value of K Coins From Piles 문제 : https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/description/ 테이블 위에 n개의 동전 더미가 있습니다. 각 더미는 여러 가지 단위의 양의 동전으로 이루어져 있습니다. 한 번의 이동으로 단일 더미에서 맨 위의 동전을 선택하여 제거하고 지갑에 추가할 수 있습니다. piles는 각 더미를 나타내는 리스트이고, piles[i]는 i번째 더미의 위에서부터 아래쪽으로 순서대로 표시된 정수의 리스트입니다. k개의 동전을 정확히 선택하여 최적으로 지갑에 보관할 경우, 지갑에 가질 수 있는 동전의 최대 총 가치를 반환하세요. DP로 풀 수 있습니다. 먼저 dp에서 사용할 인덱스를 골라봅시다. 문제를 보았을 때 가장 먼저 골라볼 수 .. 2023. 4. 15.
[Leetcode] 516. Longest Palindromic Subsequence 문제 : https://leetcode.com/problems/longest-palindromic-subsequence/description/ 주어진 문자열 s에서 가장 긴 회문 부분 수열의 길이를 찾으세요. 부분 수열이란 다른 수열에서 일부 또는 전혀 없애지 않고 남은 원소들의 순서를 변경하지 않고 유도할 수 있는 수열입니다. DP로 풀 수 있습니다. dp[i][j] = s[i~j] 의 부분 수열의 가장 긴 펠린드롬 길이. dp[i][j] = dp[i+1][j-1] + 2 (s[i] == s[j]) = max(dp[i+1][j], dp[i][j-1]) (s[i] != s[j]) 점화식은 위와 같습니다. 만약, 문자열의 가장 앞과 뒤의 문자가 같다면 문자열의 가장 앞, 뒤 문자를 부분 수열에 포함하여 길.. 2023. 4. 14.
[Leetcode] 629. K Inverse Pairs Array 문제 : https://leetcode.com/problems/k-inverse-pairs-array/ inverse pairs : 0 nums[j] 조건을 만족하는 [i, j]. DP[n][k] = n 크기의 nums 배열이 있을 때 k 개의 inverse pairs 를 가지는 경우의 수. n-1 크기의 nums에서 어떻게 n 크기의 nums를 만들 수 있는지 먼저 살펴보자. [그림 1] 에서 n=4, k=1인 경우는 왼쪽 아래와 같이 총 3가지 방법이 있다. 3가지 리스트들에서 4인 원소들을 제거하면 오른쪽과 같은 리스트들이 나온다. 여기에서 추론 가능한건 n-1 크기의 배열에서 추가되는 4의 위치에 따라 k(inverse pairs)의 크기가 달라진다는 것이다. 예를 들어보자. [그림 2] 에서 [.. 2022. 7. 17.
[leetcode] 354. Russian Doll Envelopes 문제 : https://leetcode.com/problems/russian-doll-envelopes/ 배열을 width 오름차순으로 정렬한다. 조건에서 width 는 고려하지 않게 하기 위함이다. 정렬 후 앞에 있는 요소의 width는 뒤에 있는 요소의 width 보다 항상 작거나 같으므로 height 만 고려하면 된다. 결국 정렬된 후 height의 LIS(최장 증가 수열)의 길이를 구하면 이게 정답이 된다. 위와 같은 알고리즘을 사용한다고 할 때, 고려할 점이 하나 있다. [[4,5],[4,6],[6,7],[2,3],[1,1]] 입력 배열이 위와 같을 때, [4,5] [4,6] 중 하나만 선택되게 해야 한다. height의 LIS로 정답을 구할 때 width가 동일한 요소들은 하나만 선택하게 하려.. 2022. 5. 26.
[Leetcode] 32. Longest Valid Parentheses 문제 : https://leetcode.com/problems/longest-valid-parentheses/ '(', ')' 문자만 포함한 문자열이 주어질 때, 가장 긴 유효한 괄호 부분 문자열의 길이를 구하여라. DP + Stack dp[i] = s[~i] 문자열에서 s[i]를 포함한 부분 문자열의 가장 긴 유효한 괄호 부분 문자열 길이. stack 열린 괄호 문자 인덱스 문자열 s를 앞에서부터 탐색하면서 열린 괄호 문자면 스택에 저장하고 닫힌 괄호 문자이면서 스택에 값이 있으면 top 값을 가져온다. top은 현재 탐색 중인 닫힌 괄호 문자와 매칭 되는 열린 괄호 문자의 인덱스(let, index)이며 dp[i] = (i - index + 1) + dp[index-1] dp의 점화식은 위와 같다. .. 2022. 5. 24.
[Leetcode] 799. Champagne Tower 문제 : https://leetcode.com/problems/champagne-tower/ DP로 풀었다. dp[row][glass] = row 행의 glass 번째 그릇의 남는 샴페인 양. = (dp[row-1][glass] + dp[row-1][glass+1]) % 1 dp[0][0] = poured로 갱신 후 아래 수도코드를 진행한다. for(int row=0; row 2022. 3. 5.

티스토리툴바