본문 바로가기

DP50

[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.
[Leetcode] 847. Shortest Path Visiting All Nodes 문제 : https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/ 우선 플로이드 워셜 알고리즘으로 모든 정점간 최단거리(dist)를 구한다. 구한 dist 배열로 플로이드 워셜 알고리즘이랑 비슷하게 정답을 구한다. 기본 알고리즘은 다음과 같다. 여기서 상태란 node들이 포함된 상태를 의미한다. (참고) 즉, 플로이드 워셜 알고리즘 처럼 3중 for문을 돌린다. 중간 지점을 중간에 거치는 상태로 두고 시작 노드에서 종료 노드로 갈 때 거치는 최소 간선의 수를 구한다. 조건문에 시작노드가 포함되고 종료노드는 포함되지 않은 상태가 중간상태가 되야 하는 이유는 중간상태에 시작노드가 있어야만 시작 상태가 될 수 있고, 중간상태에 종료.. 2022. 2. 26.
[leetcode] 1463. Cherry Pickup II 문제 : https://leetcode.com/problems/cherry-pickup-ii/ rows x cols 체리 필드(grid)가 주어지고 각 요소값은 체리 수를 의미한다. 로봇1은 왼쪽 상단 (0,0)에서 출발하고 로봇2는 오른쪽 상단 (0, cols-1)에서 출발한다. 셀 (i,j)에서 로봇은 (i+1, j-1), (i+1, j), (i+1, j+1) 3가지 중에 한 곳으로 이동할 수 있다. 두 로봇이 동일한 셀에 있을 때 한 로봇만 체리를 가져갈 수 있다. 로봇들이 이동할 때, 수집할 수 있는 체리의 최대 수를 구해라. DP로 풀 수 있다. dp[row][col1][col2] = 로봇1은 (row, col1), 로봇2는 (row, col1)에 있을 때 수집가능한 체리수의 최대값. dp[ro.. 2022. 1. 11.

티스토리툴바