그래프이론

이번에는 코딩 테스트에서 종종 유용하게 사용되는 다익스트라(Dijkstra) 알고리즘에 대해 이야기하려고 합니다. 다익스트라 알고리즘은 최단 경로 문제를 해결하는 데 사용되며, 가중치가 있는 그래프에서 시작 정점으로부터 모든 정점까지의 최단 경로를 찾아줍니다. 다익스트라 알고리즘이란? 다익스트라 알고리즘은 하나의 시작 정점에서 모든 정점까지의 최단 거리를 구하는 그리디한 방법입니다. 이를 위해 우선순위 큐(힙)을 활용하여 현재까지의 최단 거리 정보를 업데이트합니다. 다익스트라 알고리즘의 접근 방법은 다음과 같습니다. 시작 정점을 선택하고 해당 정점까지의 거리를 0으로 초기화합니다. 나머지 정점들까지의 거리를 무한대로 초기화합니다. 현재 선택된 정점과 연결된 모든 인접한 정점들에 대해 최소 거리 갱신을 시..

이번에는 코딩 테스트에서 반드시 알아야 하는 주제 중 하나인 깊이 우선 탐색(DFS, Depth-First Search)에 대해 이야기하려고 합니다. DFS는 그래프 탐색 방법 중 하나로, 시작 노드에서부터 가능한 한 깊숙히 들어가며 그래프를 탐색하는 방식입니다. DFS(Depth-First Search)란? DFS는 그래프 탐색 알고리즘 중 하나로, 깊이를 우선으로 탐색하는 방식입니다. 시작 노드에서부터 한 경로를 따라 더 이상 갈 수 없을 때까지 탐색하고, 다시 돌아와서 다른 경로를 탐색합니다. 이 과정은 스택(Stack) 또는 재귀 함수를 통해 구현할 수 있습니다. DFS에서 사용되는 주요 개념은 다음과 같습니다. 스택(Stack): DFS는 스택 자료구조를 활용하여 현재 위치에서 갈 수 있는 경로..

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