본문 바로가기
반응형

dfs18

[Programmers] 타겟 넘버 문제 : https://programmers.co.kr/learn/courses/30/lessons/43165 DFS 방식으로 탐색하면서 모든 인덱스의 숫자들을 더하거나 빼는 경우의 합을 구한다. 모든 numbers 를 탐색했을 때 합이 targetSum과 같다면 정답 +1을 해준다. 시간복잡도는 하나의 인덱스에 더하거나 빼는 경우, 두 번을 탐색하므로 O(2^N). N = |numbers| 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/%ED%83%80%EA%B2%9F%20%EB%84%98%EB%B2%84.cpp 2021. 8. 5.
[leetcode] 827. Making A Large Island 문제 : https://leetcode.com/problems/making-a-large-island/ n x n 크기의 0과 1로 이루어진 grid 배열이 입력으로 주어질 때, 1로 이루어진 섬의 최대 크기를 구하여라. 이 때, 최대 한 번 0을 1로 바꿀 수 있다. dfs를 한 번 돌리면서 연결된 1들을 하나의 섬으로 보고 섬의 번호와 해당 섬의 크기를 map에 저장한다. grid 배열을 한 번 더 탐색하면서 탐색하는 셸이 0인 경우 해당 셸의 상하좌우에 있는 섬의 번호들을 가져온다. 상하좌우에 있는 섬들의 합 + 1 (탐색중인 0 셸이 1로 바뀌면서 증가된 섬의크기)들이 하나의 0을 1로 바꿨을 때 구할 수 있는 섬의 크기이다. 구할 수 있는 섬들의 크기들 중 최대값이 정답이 된다. 시간/공간 복잡.. 2021. 8. 2.
[programmers][월간 코드 챌린지 시즌2] 모두 0으로 만들기 문제 : programmers.co.kr/learn/courses/30/lessons/76503# 연결된 두 점의 한 쪽은 +1, 다른 한 쪽은 -1을 하면 플마제로이기 때문에 결국 모든 노드의 가중치들의 합은 유지된다. 따라서 모든 노드들의 가중치 합이 0가 되지 않는다면 -1을 반환한다. 모든 노드들의 가중치 합이 0이 아니라면 가중치를 0으로 만드는 것은 가능하다. 임의의 노드를 루트노드라 가정하고 해당 노드로 다른 모든 노드들의 가중치를 루트노드로 이동시켜보자. [그림 1]은 가중치 0을 가진 노드를 루트노드라 가정하여 다른 노드들의 가중치를 순수하게 옮긴다고 가정했을 때의 이동횟수이다. 예를 들어 3 노드의 가중치를 0 노드로 옮길 때 -1 노드를 거치지만 단순히 거쳐가는 노드로만 사용된다. 총.. 2021. 4. 17.
[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.
반응형