본문 바로가기

DP52

[leetcode][63] Unique Paths II 문제 : https://leetcode.com/problems/unique-paths-ii/description/ 로봇이 M x N 그리드의 왼쪽 위 코너에 있다. 로봇은 아래나 오른쪽으로만 움직일 수 있다. 그리드에는 장애물들이 있다. 장애물이 있는 경우 해당 칸으로는 갈 수 없다. 로봇이 그리드의 오른쪽 아래 코너로 가려고 할때 경우의 수는 총 몇 가지인가. 2차원 배열을 만든다. d[i][j] = (i, j)에서 도착점까지 갈 수 있는 경우의 수. 위 배열을 채우면 되는데, 로봇이 이동할 수 있는 방향은 아래, 오른쪽이고 장애물은 이동할 수 없다는 것으로 점화식을 세울 수 있다. d[i][j] = d[i+1][j] + d[i][j+1] ((i, j)가 장애물이 아닌 경우) d[i][j] = 0 ((.. 2020. 6. 30.
[leetcode][96] Unique Binary Search Trees 문제 : https://leetcode.com/problems/unique-binary-search-trees/1..n 의 수로 만들어질 수 있는 BST의 수를 구하라.예시에서 보여주고 있는 n = 3일 때의 만들 수 있는 BST들을 노드 입력 순으로 나열해보자. 1. 1 2 3 2. 1 3 2 3. 2 1 3 (2 3 1) 4. 3 2 1 5. 3 1 2 3번을 보면 [2, 1, 3] 과 [2, 3, 1]의 BST 결과가 같다는 것을 알 수 있다.BST는 루트노드보다 작은 노드들은 루트노드의 왼쪽 서브트리로 가고, 루트노드보다 큰 노드들은 루트노드의 오른쪽 서브트리로 간다.그러므로 2 다음에 1이나올지 3이 나올지는 중요하지 않다는 것이다. 1은 반드시 2의 왼쪽 서브트리로 갈 것이고, 3은 반드시 2.. 2020. 6. 24.
[leetcode][72] Edit Distance 문제 : https://leetcode.com/problems/edit-distance/ word1에서 word2를 만들고자 한다. 최소 편집횟수를 구하라. 편집 방법은 총 3가지가 있다. 1) 문자 추가. 2) 문자 삭제. 3) 문자 대체(변경) 대표적 DP 문제 중 하나. dp[i][j] = word1[0..i]를 word2[0..j]로 만들 때 최소 편집횟수. word1[i], word2[j]가 같다면 dp[i][j] = dp[i-1][j-1]. word1[i], word2[j]가 다른경우 i) 문자 추가 : dp[i][j-1] + 1 ii) 문자 삭제 : dp[i-1][j] + 1 iii) 문자 대체 : dp[i-1][j-1] + 1 위 3가지 방법 중 최소값이 dp[i][j]가 된다. 이를 열우.. 2020. 6. 2.
[leetcode][1277] Count Square Submatrices with All Ones 문제 : https://leetcode.com/problems/count-square-submatrices-with-all-ones/ 1과 0으로 이루어진 N x M 배열이 주어지면 1로 이루어진 정사각형의 개수를 구하라. 행, 열 subsum을 구한 뒤 이를 이용하여 구했다. 입력배열이 위와 같으면 행, 열 부분합 배열은 각각 위와같이 만들어진다. (2,1) 한 칸이 정사각형인지 판단하는 방법은 행 부분합에서 (2, 1) - (1,1) 값과 열 부분합에서 (2,1) - (2,0) 값이 둘 다 1이어야 한다. 즉, (2,1) 값이 1인지 확인하기만 하면 된다. 그 다음 (2,1)을 정사각형의 왼쪽 모서리로 두고 사이즈가 2인 정사각형이 가능한지 판단해보자. 이전 단계에서 (2, 1)은 모두 1인 것을 판.. 2020. 5. 23.
[leetcode][152] Maximum Product Subarray 문제 : https://leetcode.com/problems/maximum-product-subarray/ 정수형 배열 nums가 주어질때, subarray의 원소들의 곱 중 최대를 구해라. 곱한다고 했을 때, 최대값이 될 가능성이 있는 경우는 현재 탐색중인 원소가 양수인 경우 가장 큰 양수를 곱하는 경우이고. 탐색중인 원소가 음수인 경우 가장 작은 음수를 곱하는 경우이다. 즉, 배열을 탐색해나가면서 원소의 곱이 가장 큰 경우와 가장 작은 경우를 변수에 저장해둔다. // let, now = 탐색중인 원소 값 // let, maxProducts = 연속되는 원소들의 곱들 중 최대 // let, minProducts = 연속되는 원소들의 곱들 중 최소 maxProducts = max(now, maxProd.. 2020. 3. 24.
[Kickstart][2020][Round A] 2. Plates 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d40bb N개의 접시 스택이 주어지고, 각 접시들은 각 스택마다 K개의 접시들로 이루어진다. 각 접시들은 양의 정수를 가지고 있으며 접시들은 쌓여 있으므로 위에 있는 접시들부터 차례대로 가져올 수 있다. (중간에 있는 접시만 가져올수는 없다.) 최대 P개의 접시들로 저녁을 구성하려고 할 때, 해당 접시들의 양의 정수의 합이 최대가 되는 경우를 구하라. (최대 접시들의 고유 값의 합 리턴) 탐색은 dfs로 하고 메모이제이션을 위해 dp를 사용했다. n번째 접시 스택부터 N번빼 접시 스택까지 접시를 선택할 수 있다고 할 때, 총 P-p개의 접시로.. 2020. 3. 24.

티스토리툴바