최단 경로 알고리즘은 보통 한 정점에서 나머지 전부로 가는 거리를 푼다. 다익스트라와 벨만-포드 모두 시작점이 하나다. 모든 정점에서 모든 정점으로 가는 거리가 필요하면 다익스트라를 V번 돌릴 수도 있지만, 우선순위 큐와 인접 리스트를 매번 다시 세팅해야 하고 음수 가중치가 있으면 쓸 수 없다. 플로이드-워셜은 시작점을 고정하지 않는다. 거리 행렬 하나를 놓고 3중 루프를 한 번 돌면 모든 쌍의 최단 거리가 행렬에 채워진다. 코드는 12줄이고, 음수 간선을 처리하며, 음수 사이클의 존재 여부까지 알려준다. ...
백준 27440번 “1로 만들기 3"은 10^18 범위의 매우 큰 정수를 세 가지 연산(3으로 나누기, 2로 나누기, 1 빼기)으로 1로 만들 때 필요한 최소 연산 횟수를 구하는 문제다. 입력 범위가 10^18에 달하므로 일반적인 동적 프로그래밍 접근법(O(N) 시간, O(N) 공간)으로는 해결할 수 없다. 대신 재귀적 점화식과 맵 기반 메모이제이션을 활용해 O(log² n) 시간 복잡도로 해결해야 한다. 문제 설명 백준 27440번 - 1로 만들기 3 정수 N이 주어졌을 때, 세 가지 연산을 적절히 사용하여 1을 만드는 데 필요한 최소 연산 횟수를 구하는 문제다. ...