DFS4 DFS/BFS 개념 및 문제 접근 방법 0. 개요 - DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다. - DFS와 BFS가 어떻게 다른지, 언제 사용되는지 알아보자. 1. DFS(Depth First Search) a) DFS의 탐색 방법 - DFS는 다음과 같은 탐색 순서를 갖는다. - DFS는 하나의 방향을 결정하면 그 방향을 따라 끝까지 도달한다. ▶ 트리의 경우, 왼쪽에 위치한 노드를 우선적으로 탐색한다. ▶ 그래프의 경우, 가중치 또는 특정 기준을 따라 탐색 방향의 우선순위를 결정한다. - 위의 그림을 토대로 DFS는 다음과 같은 탐색 순서를 갖는다. ▶ 0번을 시작으로 왼쪽에 위치한 노드를 우선적으로 탐색한다. (0 ~ 3번 노드로 탐색) ▶ 3번 노드가 끝이므로 이전 단계로 돌아간다. (1번 노드로 돌아감) ▶ 1번 노드에서.. 2022. 7. 5. LeetCode 77(Combinations, java) 0. 문제 https://leetcode.com/problems/combinations/ Combinations - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 문제 설명 - 문제에서 정수 n과 k가 주어진다. - 1부터 n까지의 수를 이용하여 중복 없이 k개의 짝을 이루는 모든 조합을 구하는 것이 문제의 핵심이다. 2. 문제 해설 a) 첫 번째 접근 - 이 문제는 전형적인 back tracking 문제다. - back tracking은 정답에 부합하는 .. 2022. 5. 6. Advanced Algorithm - 깊이 우선 탐색(Depth First Search) 1. 깊이 우선 탐색(DFS)이란? - 방향과 상관없이 오른쪽 또는 왼쪽 노드를 기준으로, 한 노드의 자식노드를 타고 끝까지 순회한 후 다시 돌아와서 다른 형제들의 자식을 타고 내려가는 방식으로 순회하는 탐색 a) DFS 예시 DFS 동작방식: A - B - D - E - F - C - G - H - I - J 2. DFS 알고리즘 동작방식의 이해 - DFS 알고리즘은 Stack과 Queue를 이용하여 구현할 수 있다. - need_visit Stack과 visited Queue를 사용하여 구현한다. - stack의 특성(LIFO)으로 인해 BFS와는 다르게 need_visit Stack에서 꺼내오는 데이터는 가장 나중에 삽입된 데이터다. 3. DFS 알고리즘 코드구현 def dfs(graph, star.. 2020. 9. 25. Advanced Algorithm - 너비 우선 탐색(Breadth First Search) 1. 그래프 탐색 알고리즘이란? - 그래프를 기반으로 특정 노드를 찾아가기 위한 알고리즘 - 이 그래프 알고리즘에는 2가지 대표 알고리즘이 있다. 너비 우선 탐색(Breadth First Search) - 정점(노드)과 같은 레벨에 있는 노드(=형제 노드)를 먼저 탐색하는 방식 깊이 우선 탐색(Depth First Search) - 정점(노드)의 자식노드를 먼저 탐색하는 방식 a) 너비 우선 탐색(BFS)의 예 - 방향과 상관없이 왼쪽 또는 오른쪽 노드를 기준으로, 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드(형제 노드)를 먼저 순회하는 탐색 BFS 이동순서: A - B - C - D - G - H - I - E - F - J b) 깊이 우선 탐색(DFS)의 예 - 방향과 상관없이 왼쪽 또는.. 2020. 9. 24. 이전 1 다음
