IfUwanna IT

💻 Jihun's Ifuwanna IT :: Tech Blog 😃

깊이우선탐색 검색 결과

해당 글 4건

[알고리즘] 깊이 우선 탐색(DFS, Depth First Search)이란?

깊이 우선 탐색(DFS, Depth-First Search) 트리나 그래프의 하나의 정점의 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 깊게 전부 먼저 탐색해 나가는 방법입니다. 마치 미로에서 갈수있는 끝까지 갔다가 가장 가까운 갈림길에서 다시 탐색을 시작하는 방법과 유사합니다. 왼쪽 그림과 같이 하나의 노드의 모든 루트를 깊게(deep) 탐색하고 다음 노드로 넘어가는 깊이우선탐색(DFS)과 오른쪽처럼 달리 동일한 깊이를 먼저 넓게(wide) 탐색하는 것을 볼 수 있습니다. 깊이 우선 탐색(DFS)의 특징 DFS는 일반적으로 스택이나 재귀호출을 통해 구현합니다. (재귀호출을 통한 메서드 스택) 리프노드를 한 번에 잘라내기 용이하여 백트래킹 알고리즘에 자주 사용됩니다. 어떤 노드를 방문했..

알고리즘/이론 2022. 3. 7. 06:21

[LeetCode ] 112. Path Sum - 문제풀이

Description 주어진 이진트리를 root부터 leaf 노드까지 탐색하여 targetSum과 일치하는 값이 있는지 찾아가는 문제입니다. Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: T..

알고리즘/LeetCode 2022. 2. 14. 02:02

[LeetCode] 226. Invert Binary Tree - 문제풀이

Description 주어진 이진 트리를같은 뎁스의 값들을 뒤집어(invert) 반환하는 문제입니다. Given the root of a binary tree, invert the tree, and return its root. Example 1: Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1] Example 2: Input: root = [2,1,3] Output: [2,3,1] Example 3: Input: root = [] Output: [] Constraints: The number of nodes in the tree is in the range [0, 100]. -100

알고리즘/LeetCode 2022. 2. 14. 01:23

[LeetCode] 77. Combinations - 문제풀이

Description 1부터 n까지의 정수중에서 k개의 조합의 경우의 수를 모두 반환하는 문제입니다. Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]. You may return the answer in any order. Example 1: Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] Example 2: Input: n = 1, k = 1 Output: [[1]] Constraints: 1

알고리즘/LeetCode 2022. 2. 2. 15:21