분류 전체보기49 벨만-포드 알고리즘: 음수 가중치와 사이클 완벽 해결법 우리는 앞서 다익스트라 알고리즘이 음수 가중치 앞에서 무력해지는 모습을 보았습니다. 하지만 현실의 세계에는 비용이 절감되거나 에너지가 충전되는 등 '음수 가중치'를 고려해야 하는 특수한 상황이 분명 존재합니다. 이러한 한계를 극복하고 그래프 내의 모든 최단 경로를 찾아내는 우직하고 강력한 해법이 바로 벨만-포드(Bellman-Ford) 알고리즘입니다. 본 포스팅에서는 벨만-포드가 어떻게 음수 가중치를 처리하며, 특히 무한 루프를 유발하는 '음수 사이클'을 어떻게 감지하는지 그 정교한 매커니즘을 파헤쳐 보겠습니다.1. 벨만-포드 알고리즘의 철학: 모든 간선의 전수 조사벨만-포드 알고리즘의 접근 방식은 다익스트라보다 훨씬 신중합니다. 다익스트라가 '가장 가까운 곳'을 믿고 나아가는 확신형이라면, 벨만-포드는.. 2026. 4. 7. 다익스트라 최단 경로 알고리즘: 우선순위 큐 구현 가이드 현대 사회에서 우리가 매일 사용하는 내비게이션 서비스나 배달 앱의 경로 최적화 배후에는 고도의 수학적 알고리즘이 숨어 있습니다. 그중에서도 다익스트라(Dijkstra) 알고리즘은 특정 지점에서 다른 모든 지점까지의 최단 거리를 구하는 가장 대표적이고 효율적인 기법으로 손꼽힙니다. 1956년 에츠허르 다익스트라에 의해 고안된 이 알고리즘은 반세기가 넘은 지금까지도 네트워크 라우팅 프로토콜(OSPF 등)의 핵심 로직으로 활용되고 있습니다. 본 포스팅에서는 다익스트라 알고리즘의 철학적 배경부터 우선순위 큐를 이용한 성능 최적화의 정수까지 심도 있게 분석해 보겠습니다.1. 다익스트라 알고리즘의 핵심 논리와 그리디 전략다익스트라 알고리즘의 근간은 그리디(Greedy) 알고리즘과 동적 계획법(Dynamic Prog.. 2026. 4. 7. DFS vs BFS 문제 상황별 알고리즘 선택 가이드 효율적인 프로그래밍은 단순히 정답을 맞히는 것을 넘어, 주어진 상황에 가장 적합한 도구를 선택하는 능력에서 시작됩니다. 그래프 탐색의 양대 산맥인 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 서로 상반된 전략을 가지고 있으며, 문제의 요구사항에 따라 그 성능 차이가 극명하게 갈립니다. 본 포스팅에서는 두 알고리즘의 장단점을 철저히 비교 분석하여, 실전 문제 해결을 위한 명확한 판단 기준을 정립해 드리겠습니다[cite: 5, 238].[Image comparing DFS and BFS traversal paths on a tree structure for clarity]1. DFS와 BFS의 메커니즘 비교와 특성두 알고리즘은 모든 노드를 방문한다는 목표는 같지만, 그 '과정'에서 큰 차이를 보입니.. 2026. 4. 6. 너비 우선 탐색 BFS 큐 활용 최단 거리 탐색 지형 정보가 담긴 지도에서 최단 경로를 찾거나, 소셜 네트워크 서비스에서 '아는 사람'의 단계를 계산할 때 필수적으로 요구되는 기술이 있습니다. 바로 너비 우선 탐색(Breadth-First Search, BFS)입니다. BFS는 시작 지점에서 가까운 곳부터 차례대로 탐색 범위를 넓혀가는 방식을 통해 데이터 간의 거리 관계를 명확히 규명합니다. 본 포스팅에서는 BFS의 수학적 정당성과 큐(Queue)를 활용한 구현 메커니즘을 상세히 다루어 보겠습니다[cite: 5, 238].1. 너비 우선 탐색(BFS)의 정의와 계층적 탐색 원리너비 우선 탐색은 시작 노드로부터 인접한 노드를 먼저 방문하고, 멀리 떨어져 있는 노드는 나중에 방문하는 방식입니다. 마치 호수에 돌을 던졌을 때 물결이 동심원을 그리며 퍼져나가.. 2026. 4. 6. 깊이 우선 탐색 DFS 재귀와 스택 원리 정리 컴퓨터 과학의 그래프 이론에서 탐색은 가장 기초적이면서도 강력한 문제 해결 도구입니다. 그중에서도 깊이 우선 탐색(Depth-First Search, DFS)은 미로를 찾듯 한 방향으로 끝까지 파고들어 탐색하는 기법으로, 알고리즘 설계의 정수로 불립니다. 본 포스팅에서는 DFS의 논리적 구조와 재귀 및 스택을 활용한 구현 방식, 그리고 실무적인 활용 방안을 상세히 기술하겠습니다[cite: 5, 238].1. 깊이 우선 탐색(DFS)의 정의와 논리적 메커니즘깊이 우선 탐색은 그래프나 트리 구조에서 시작 노드를 방문한 뒤, 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식입니다. 이는 '더 이상 갈 곳이 없을 때까지 깊게 내려가는' 전략을 취하며, 막다른 길에 도달했을 때만 가장 최근의 갈림길로.. 2026. 4. 6. 투 포인터(Two Pointers)와 슬라이딩 윈도우(Sliding Window) 차이점 코딩 테스트에서 배열이나 문자열을 다루는 문제를 풀 때, 이중 반복문(for문 2개)을 사용하여 전체 경우의 수를 샅샅이 뒤지는 O(N^2) 방식은 가장 직관적이지만 필연적으로 '시간 초과(Time Limit Exceeded)'의 늪에 빠지게 만듭니다. 데이터가 10만 개만 되어도 100억 번의 연산이 필요하기 때문입니다. 이때 O(N^2)의 끔찍한 시간 복잡도를 마법처럼 단 O(N)의 선형 시간으로 줄여주는 구세주 같은 두 가지 알고리즘 기법이 있습니다. 바로 '투 포인터(Two Pointers)'와 '슬라이딩 윈도우(Sliding Window)'입니다. 두 기법 모두 1차원 배열을 단 한 번만 스캔하여 정답을 도출한다는 공통점이 있지만, 포인터(화살표)가 움직이는 방식과 적용해야 하는 문제의 조건이 .. 2026. 2. 23. 이전 1 2 3 4 ··· 9 다음
