플로이드-워셜(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을 만드는 데 필요한 최소 연산 횟수를 구하는 문제다. ...