💻 Jihun's Ifuwanna IT :: Tech Blog 😃
BFS 검색 결과

해당 글 5건

[알고리즘] 깊이 우선 탐색(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] 101. Symmetric Tree - 문제풀이

Description 주어진 트리가 root를 중심으로 거울에 비춘 것 처럼 대칭을 이루는지 여부, 즉 대칭 트리 여부를 반환하는 문제입니다. Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). Example 1: Input: root = [1,2,2,3,4,4,3] Output: true Example 2: Input: root = [1,2,2,null,3,null,3] Output: false Constraints: The number of nodes in the tree is in the range [1, 1000]. -100
알고리즘/LeetCode 2022. 2. 14. 01:00

[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)이란?

너비 우선 탐색(BFS, Breadth-First Search) 트리나 그래프의 하나의 정점에서 시작해서 정점에 인접한 모든 노드를 먼저 탐색하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법으로 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다. BFS 탐색과정 루트에서 시작한다. 자식 노드들을 [1]에 저장한다. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다. 위의 과정을 반복한다. 모든 노드를 방문하면 탐색을 마친다. 왼쪽 그림과 같이 하나의 노드의 모든 루트를 깊게(deep) 탐색하고 다음 노드로 넘어가는 깊이우선탐색(DFS)과 오른쪽처럼 달리 동일한 깊..
알고리즘/이론 2022. 1. 12. 13:48