본문 바로가기

DP52

[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.
[Codejam][2021][QR] 2. Moons and Umbrellas 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d1145 X = CJ 비용, Y = JC 비용. S = C, J, ? 로 이루어진 문자열 S 문자열의 ? 문자에 C 혹은 J를 대체한다고 할 때, 지불해야 하는 최소 비용을 구해라. DP로 풀 수 있다. dp[0][i] = S[i]가 'C' 일 때, S[~i] 까지 최소 지불금액 dp[1][i] = S[i]가 'J' 일 때, S[~i] 까지 최소 지불금액 dp 배열은 초기 값은 만들 수 없음을 의미하는 INF 값으로 세팅한다. 그리고 S[0]이 'C' 혹은 '?'인 경우 dp[0][0] 을 0으로 갱신한다. 또한 S[0]이 'J' 혹은 '?'인 .. 2022. 1. 8.
[leetcode] 131. Palindrome Partitioning 문제 : https://leetcode.com/problems/palindrome-partitioning/ 문자열 s가 입력으로 주어지면 파티션의 모든 하위 문자열이 palidrome 이 되도록 하는 모든 경우를 구하라. 문자열을 앞뒤로 읽었을 때 같은 문자열인 경우 palidrome이라 한다. DP + backtracking 팰린드롬인지 구하는 함수. DP // dp[s][e] = str[s ~ e]가 palidrome인지 fun isPalidrome(str, s, e) { if(dp[s][e]가 없으면) dp[s][e] = str[s]와 str[e]가 같은 문자이며 isPalidrome(str, s+1, s-1) 인 경우 return dp[s][e]; } 팰린드롬 하위 문자열들을 만들어서 partit.. 2022. 1. 6.
[Leetcode] 337. House Robber III 문제 : https://leetcode.com/problems/house-robber-iii/ 이진 트리로 구성된 집들의 구조가 있다. 도둑은 집들에 침입해 도둑질을 하려고 하는데 연결된 집을 동시에 털면 경찰에 연락이 간다. 경찰에 연락이 가지 않게 집들을 도둑질하려고 할 때, 훔칠수 있는 최대 금액을 구해라. memoization을 위해 TreeNode*을 키 값으로 하고 해당 노드를 헤드노드로 한 서브트리에서 조건을 만족하며 훔칠 수 있는 최대 금액을 저장한다. 탐색 중인 노드를 훔쳤다면 왼쪽, 오른쪽 자식 노드들은 훔치면 안되므로 왼쪽 자식 노드의 자식 노드들, 오른쪽 자식 노드의 자식 노드들을 다시 헤드 트리로 하여 훔칠 수 있는 최대 금액들의 합이 정답이 될 수 있다. 또한 탐색 중인 노드를 .. 2021. 12. 5.
[leetcode] 115. Distinct Subsequences 문제 : https://leetcode.com/problems/distinct-subsequences/ 문자열 s, t가 주어지면 t와 동일한 s의 고유한 하위 시퀀스 수를 반환하라. 답은 32비트 부호있는 정수임을 보장한다. DP로 풀었다. dp[i][j] = t[0~j]와 동일한 s[0~i]의 고유한 하위 시퀀스 수. dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (s[i]가 t[j]인 경우) dp[i][j] (s[i] 가 t[j]가 아닌 경우) 점화식은 위와 같다. s[i] == t[j]인 경우 s[0~i-1] 문자열의 고유 하위 시퀀스들 문자 뒤에 s[i]를 붙이면 t[0~j]가 되므로 dp[i-1][j]에 dp[i-1][j-1]을 더해준다. ex) s = "rabbbit", .. 2021. 9. 19.

티스토리툴바