got beer?

✅ 벨먼-포드 알고리즘 (Bellman-Ford Algorithm) ❕ 기본 개념 - 그래프의 최단 경로 문제를 해결하기 위한 알고리즘 - 최단 경로 문제에서는 간선에 가중치가 부여된 가중 그래프가 주어지며, 시작점부터 종점까지의 경로 중 간선의 가중치 최소합을 구하면 됨 - 가중치가 음수라도 제대로 동작함 - 방향성/비방향성 그래프 모두 적용 가능 - 정점 수를 n, 간선 수를 m이라고 할 때, 가중치 변경 작업을 n회 순회하고, 각 변경 작업에서 각 간선을 1회씩 조사하므로 전체 계산 시간은 O(nm) ❕ 작동 방식 ✔ 구현 방법 (JS) function BellmanFord(graph, V, E, src) { // Initialize distance of all vertices as infinite..

✅ 너비 우선 탐색 (BFS, Breadth-First Search) ❕ 기본 개념 - 그래프의 시작점에서 간선(edge)을 따라가며 정점(node)을 탐색하고 지정한 목표 정점에 도달하는 것 - BFS는 그래프의 시작점부터 가까운 순으로 너비를 넓혀 가며 탐색하는 알고리즘 - 따라서 목표가 시작점에 가까이 있으면 탐색이 빨리 종료됨 - 후보 노드를 선입선출(FIFO) 구조로 관리하므로 queue 데이터 구조를 사용 - 따라서 queue와 while loop을 이용하여 BFS를 구현함 ❕ 작동 방식 ✔ 활용 예시 queue의 특징이 필요한 부분이나 너비를 우선으로 탐색하는 것이 효율적인 곳에 사용됨 ex. 최단거리를 구하는 문제 ☞ BFS로 가까운 노드부터 탐색하기 때문에, 가장 먼저 찾아지는 해답이 곧..