algorithm
-
[Graph] 그래프의 탐색 - 너비 우선 탐색 (BFS, Breadth-First Search)알고리즘, 코딩테스트/알고리즘 개념 2023. 12. 18. 01:21
다양한 그래프 탐색 알고리즘이 있지만 가장 기본이 되면서 대표적인 알고리즘은 바로 DFS와 BFS다. 특히 DFS와 BFS는 탐색 방법이 상반되는 만큼 특징과 용도가 확실히 구분되는 편이기 때문에 두 탐색 방법 모두 확실히 이해하고 자유자재로 활용할 수 있어야 한다. 나아가 문제를 만났을 때 어떤 탐색 방식을 사용하는 것이 좋을지 결정할 수 있도록 그 특징을 이해하고 다양한 유형의 문제를 접해보는 것이 좋다. 너비 우선 탐색 (BFS, Breadth-First Search) DFS와 함께 대표적인 그래프 탐색 알고리즘 중 하나다. 깊이 우선 탐색인 DFS와 대조적인 탐색 방법으로 한가지 경로씩 끝까지 탐색하는 DFS와 달리 각 노드의 인접한 노드들부터 탐색해가는 특징을 가진다. 따라서 시작지점에 가까운 ..
-
[Graph] 그래프의 탐색 - 깊이 우선 탐색 (DFS, Depth-First Search)알고리즘, 코딩테스트/알고리즘 개념 2023. 12. 5. 02:12
알고리즘 문제에서 가장 큰 비중을 차지하는 유형 중 하나가 바로 그래프 탐색 문제다. 어떤 형태의 코딩 테스트, 알고리즘 시험에서든 가장 쉽게 만날 수 있는 문제 유형이기도 하고 여러 문제가 출제되는 형식이라면 반드시 한문제 이상 포함된다고 할 수 있을 정도다. 그래프 탐색 알고리즘은 필수 중 필수이기 때문에 반드시 익숙해져야 한다. 깊이 우선 탐색 (DFS, Depth-First Search) DFS는 대표적인 그래프 탐색 알고리즘 중 하나다. 직관적인 이름 그대로 깊이를 따라서 탐색해나가는 방법으로 너비 우선 탐색(BFS)과 대조되는 특징을 가진다. BFS의 경우 동시에 여러 갈래의 길을 뻗어나가듯 탐색한다면 DFS는 일반적으로 미로찾기를 해나갈 때와 같이 분기점에서 하나의 길을 선택하고 그 길을 따..
-
[Graph] 그래프의 표현 - 인접 행렬과 인접 리스트 (Adjacency Matrix, Adjacency List)알고리즘, 코딩테스트/알고리즘 개념 2023. 9. 12. 01:38
그래프(Graph) 탐색 문제를 풀기 위해서 가장 먼저 고려해야하는 것은 그 그래프를 어떻게 자료구조로 표현할지에 대한 것이다. DFS든 BFS든, 최단경로를 찾아내기 위한 다익스트라(Dijkstra)를 이용하든 일단 그래프를 프로그램으로 적절히 옮겨와야 무엇이든 해볼 수 있다. 정점 (Node 또는 Vertex) 과 간선 (Edge)으로 구성된 그래프를 자료구조로 표현하는 방법에는 인접행렬 (Adjacency Matrix)과 인접 리스트 (Adjacency List), 두가지가 있다. 각각 이름에서 알 수 있듯이 행렬(배열)을 이용해 표현하는 방법과 리스트를 이용하는 방법이다. 여기에서 말하는 '인접'은 두 노드 간 간선이 연결되어있음을 뜻한다. 그래프에서 두 노드가 간선으로 연결되어있다면 인접했다고 ..