플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프의 모든 정점 쌍(All-Pairs) 사이의 최단 경로를 찾는 동적 프로그래밍 기반 알고리즘이다. 다익스트라나 벨만-포드 알고리즘과 달리 한 번의 실행으로 모든 쌍의 최단 경로를 동시에 계산할 수 있으며, 1962년 Robert Floyd와 Stephen Warshall이 각각 독립적으로 발표했다. 시간 복잡도는 O(V³)이며, 음수 가중치 간선을 처리할 수 있고 음수 사이클의 존재 여부도 탐지할 수 있어 네트워크 지름 계산, 추이적 폐쇄 연산, 데이터베이스 쿼리 최적화 등 다양한 분야에서 활용된다. 플로이드-워셜 알고리즘의 역사 플로이드-워셜 알고리즘이란? ...
벨만-포드(Bellman-Ford) 알고리즘은 가중치가 있는 그래프에서 단일 시작점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 1950년대에 Richard Bellman과 Lester Ford Jr.가 독립적으로 발견했으며, 다익스트라 알고리즘과 달리 음수 가중치를 가진 간선을 처리할 수 있다. 또한 그래프 내에 음수 사이클이 존재하는지 탐지할 수 있다는 점이 큰 특징이다. 이 알고리즘은 동적 프로그래밍(Dynamic Programming) 접근법을 바탕으로 O(VE)의 시간 복잡도로 동작하며, 네트워크 라우팅 프로토콜, 금융 시장의 차익 거래 탐지, 최소 비용 흐름 문제 등 다양한 실제 응용 분야에서 활용되고 있다. ...
다익스트라(Dijkstra) 알고리즘은 가중치가 있는 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 대표적인 알고리즘으로, 1956년 네덜란드의 컴퓨터 과학자 Edsger Wybe Dijkstra가 발명하여 현재까지 네트워크 라우팅, GPS 내비게이션, 게임 AI 등 수많은 분야에서 핵심적으로 활용되고 있다. 탐욕 알고리즘(Greedy Algorithm) 접근 방식을 사용하여 매 단계에서 최적의 선택을 하며, 우선순위 큐를 활용한 구현으로 O(E log V)의 효율적인 시간 복잡도를 달성하여 대규모 그래프에서도 실용적으로 사용할 수 있다. 다익스트라 알고리즘의 역사 다익스트라 알고리즘이란? 가중치가 있는 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘으로, 모든 간선의 가중치가 0 이상이어야 한다는 제약 조건을 가진다. ...
백준 27440번 “1로 만들기 3"은 10^18 범위의 매우 큰 정수를 세 가지 연산(3으로 나누기, 2로 나누기, 1 빼기)으로 1로 만들 때 필요한 최소 연산 횟수를 구하는 문제다. 입력 범위가 10^18에 달하므로 일반적인 동적 프로그래밍 접근법(O(N) 시간, O(N) 공간)으로는 해결할 수 없다. 대신 재귀적 점화식과 맵 기반 메모이제이션을 활용해 O(log² n) 시간 복잡도로 해결해야 한다. 문제 설명 백준 27440번 - 1로 만들기 3 정수 N이 주어졌을 때, 세 가지 연산을 적절히 사용하여 1을 만드는 데 필요한 최소 연산 횟수를 구하는 문제다. ...