본문 바로가기

dfs21

[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][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.
[leetcode][1345] Jump Game IV 문제 : leetcode.com/problems/jump-game-iv/ arr 배열이 주어진다. i 인덱스에서 한 칸 이동한다고 할 때, 총 3가지 위치로 이동할 수 있다. 배열의 범위 내에서 i-1(1), i+1(2)로 이동가능하다. 또한 현재 칸과 같은 값을 가지는 칸(3)으로 이동이 가능하다. 첫 번째 인덱스에서 마지막 인덱스로 이동하는 방법 중 최소의 이동횟수를 구하라. DFS로 풀었다. arr 배열을 탐색하면서 arr 요소값을 인덱스로 하고 인덱스 배열을 value로 만드는 map을 만든다. 인덱스와 탐색횟수를 저장하는 큐를 만들고 {0, 0}을 넣고 큐가 빌 때까지 반복한다. 탐색중인 인덱스가 i라고 할 때, i-1, i+1이 탐색한 적 없다면 큐에 넣는다. 또한 map에 arr[i]를 키 .. 2020. 12. 27.
[leetcode][309] Best Time to Buy and Sell Stock with Cooldown 문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 주식가격이 주어질 때 최대 이익을 구하라. 동시에 여러개의 교환은 진행될 수 없다. (즉, 주식을 샀으면 팔때까지 다른 주식을 사고팔수없다.) 주식을 팔았을 때 다음날엔 어떠한 거래도 할 수 없다. (쿨다운 1일) 오랜만에 dfs + dp(memoization). top-down 방식으로 풀었다. dfs(index)를 stock[index~]을 사고 팔 때 얻을 수 있는 최대이익을 가져오는 함수라하자. 이 값은 index에서 어떠한 거래도 하지 않았을 때(dfs(index+1))와 index를 샀을때로 나뉠 수 있다. index 번째 주식을 구입했으면 팔아야 .. 2020. 8. 1.
[leetcode][430] Flatten a Multilevel Doubly Linked List 문제 : https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/ doubly linked list 가 주어진다. 하나의 노드는 next, previous, child 포인터를 가지고 있다. 이를 prev, next만을 가진 linked list로 바꿔라. child와 next 포인터를 가지고 있다면 child 노드를 next 노드로 잇고 child 노드와 연결된 모든 노드들이 linked list로 만들어졌을 때 그 뒤에 next노드를 다시 이어나간다. dfs로 head 노드에서 child노드가 있다면 child 노드를 잇고 다음 next노드를 잇는 식으로 재귀함수를 만들어서 푼다. 이를 위해 최근 탐색했던 노드 포인터 before와.. 2020. 7. 10.
[leetcode][200] Number of Islands 문제 : https://leetcode.com/problems/number-of-islands/ 2차원 배열 grid가 있다. grid는 1(육지)이나 0(물)로 이루어져있다. 연결되어 있는 1들의 테두리가 모두 0들로 둘러쌓여 있다면 이를 하나의 육지로 본다. grid의 테두리도 0으로 감싸여있다고 한다. grid에 있는 육지의 수를 구해라. DFS, BFS 연습하기 좋은 문제다. 기본적인 구현으로도 풀 수 있다. grid를 전부 탐색하면서 육지를 발견하면 해당 위치를 기준으로 dfs나 bfs를 돌린다. 이 때, 육지를 발견했으므로 정답에 1을 더해준다. 돌리면서 4방면(상하좌우)의 grid 요소들을 탐색하며 이가 육지(1)인 경우 물이나 육지 이외의 사인으로 바꾸어 탐색한 위치라고 표시한다. (연결된.. 2020. 3. 30.

티스토리툴바