BFS

이번에는 코딩 테스트에서 꼭 알아야하는 유형 중 하나인 BFS(Breadth-First Search)에 대해 알아보겠습니다. BFS는 그래프 탐색 알고리즘 중 하나로, 너비 우선으로 탐색을 수행하는 방법입니다. 이전 그래프 이론 및 탐색 포스팅에서 간략하게 설명하였는데, 이번 글에서는 BFS의 개념과 코딩 테스트에서 BFS 문제를 접했을 때 어떻게 접근해야 하는지에 대해 자세하게 설명하도록 하겠습니다. BFS란? BFS는 그래프 탐색 방법 중 하나로, 시작 정점에서부터 인접한 정점들을 먼저 모두 방문한 후, 다음 단계의 인접 정점들을 차례대로 방문하는 방식입니다. 이러한 너비 우선 탐색은 큐(Queue) 자료구조를 활용하여 구현됩니다. BFS의 동작 원리는 다음과 같습니다. 시작 정점을 큐에 넣고 방문 ..

이번에는 코딩 테스트에서 중요한 유형인 'Graph Traversal(그래프 탐색)'에 대해 알아보겠습니다. 그래프 탐색은 그래프의 모든 노드를 방문하는 과정을 의미합니다. 그래프는 여러 개의 노드(Node)와 간선(Edge)으로 구성되어 있으며, 실제로 많은 문제들이 그래프 형태로 모델링됩니다. 그래프 탐색의 개념 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조로, 다양한 현실 세계의 문제를 모델링하기 위해 사용됩니다. 그래프 탐색은 주어진 그래프에서 모든 정점을 방문하거나 특정한 조건을 만족하는 정점을 찾기 위해 사용됩니다. 주요한 그래프 탐색 알고리즘과 관련된 개념들을 소개하겠습니다. 깊이 우선 탐색(Depth-First Search, DFS): 한 정점에서 시작하여 다음 분기..

오늘은 코딩 테스트에서 꼭 알아야 하는 유형 중 하나인 'Graphs'에 대해 이야기해보려 합니다. 그래프 이론은 수학적 구조를 모델링하고 분석하는 데 널리 사용되는 도구로, 그래프 자체는 객체들 간의 쌍을 연결하는 선으로 구성된 추상 네트워크를 나타냅니다. 그래프란? 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다. 간선은 두 정점을 연결하며, 방향이 있는 경우와 없는 경우가 있습니다. 방향이 있는 그래프를 '방향 그래프(Directed Graph)', 방향이 없는 그래프를 '무방향 그래프(Undirected Graph)'라고 합니다. 그 외에도 가중치가 있는 그래프(Weighted Graph), 순환하는 경로가 없는 트리(Tree), 모든 정점들이 서로 연결된 완전 그래프(C..