본문 바로가기

HARD56

[leetcode] 639. Decode Ways II 문제 : https://leetcode.com/problems/decode-ways-ii/ A ~ Z 문자가 1 ~ 26 숫자로 인코딩된다.(01, 02 는 1, 2와 다르다.) 숫자와 * 문자로 이루어진 문자열이 주어진다. * 문자는 0을 제외한 1~9로 대체할 수 있다. 입력 문자열을 디코딩하였을 때 만들 수 있는 문자열들의 경우의 수를 구해라. 백트래킹과 DP(memoization)을 이용해서 풀었다. dp[ind] = 입력문자열[ind~]로 만들 수 있는 정답 경우의 수 ind 번째 문자를 탐색 중일 때, 해당 문자는 십의자리로 디코딩될수도 있고, 일의자리로 디코딩 될 수도 있다. 두 가지 경우의 수를 구한뒤 더해준다. 십의 자리로 디코딩될 수 있는 경우의 수를 먼저 알아보자. 만일 ind+1 번.. 2021. 7. 14.
[leetcode][778] Swim in Rising Water] 문제 : https://leetcode.com/problems/swim-in-rising-water/ N x N 배열 grid가 입력으로 주어진다. grid[i][j] = (i,j) 위치의 높이. 시간 t에서 모든 grid 위치의 수심은 t이고, 인접한 위치의 고도가 t 이하인 경우에만 이동가능하다. 이동하는데 드는 시간은 고려하지 않는다. grid의 (0,0)에서 (N-1, N-1)로 이동할 때 도달할 수 있는 최소시간은 얼마인가 이동하는데 드는 시간은 고려하지 않으므로 결국 (0, 0) -> (N-1, N-1)로 이동하는 경로의 고도값들의 최대값의 최소값을 구하는 문제이다. 다익스트라로 풀었다. 간선의 가중치는 u -> v로 이동한다고 했을 때, v 위치의 높이가 된다. 즉, 높이가 낮은 인접한 위치.. 2021. 6. 21.
[Leetcode][1074] Number of Submatrices That Sum to Target 문제 : leetcode.com/problems/number-of-submatrices-that-sum-to-target/ 2차원 배열 matrix와 target 정수가 주어진다. matrix[x][y] (x1 2021. 4. 18.
[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][1675] Minimize Deviation in Array 문제 : leetcode.com/problems/minimize-deviation-in-array/ n개의 양의 정수를 가지는 배열이 주어진다. 수가 짝수이면 2로 나눌 수 있고 홀수면 2를 곱할 수 있다. (복수번 적용 가능) 배열의 편차는 두가지 요소의 차이 중 최대 값이다. 구할 수 있는 배열의 편차 중 최소 값을 구하여라. 짝수면 감소. 홀수면 증가시킬 수 있다. 짝수를 2로 나누면 짝수 혹은 홀수가 나온다. 하지만 홀수를 2로 곱하면 반드시 짝수가 된다. 즉, 모든 요소들의 최대값들은 그 자신의 수(짝수인 경우)거나 x2한 수(홀수인 경우)이다. 따라서 모든 수들을 먼저 최대값으로 만든 뒤, 최대값을 감소시키면서 배열의 편차의 최소 값을 구한다. 구현은 set을 이용했고, 최대 최소는 set의 .. 2021. 1. 31.
[leetcode][987] Vertical Order Traversal of a Binary Tree 문제 : leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/ 이진 트리 노드의 루트 노드가 주어진다. 루트 노드는 (0, 0) (x,y) 위치를 가지고 왼쪽 자식 노드, 오른쪽 자식 노드로 갈수록 (x-1, y-1), (x+1, y-1) 위치 값을 가진다. 동일한 x 좌표 값을 가지는 노드들의 val 값의 배열을 x 좌표의 오름차순 정렬하여 구하라. 만일 동일한 x 좌표 값을 가진다면 y 좌표의 오름차순 정렬된 배열을 가진다. y좌표도 동일하다면 노드의 val 값을 오름차순 정렬한다. dfs로 풀 수 있다. 루트노드로부터 왼쪽, 오른쪽 자식으로 탐색하면서 (x-1, y-1), (x+1, y-1)로 좌표 값을 갱신시킨다. x 좌표를 키값, (.. 2021. 1. 30.

티스토리툴바