ASP는 모든 정점이 출발점이 되어, 모든 정점에 대한 최단 거리를 구하는 것이다.
기존에 배운 두 가지 SSP (Dijkstra, Bellman-Ford) 를 정점의 개수만큼 진행하여도 답을 얻을 수 있지만, 굉장히 많은 연산이 소요된다.
따라서, ASP 문제를 해결하기 위해서는 새로운 알고리즘을 이용해야 한다.
이번에 알아볼 ASP (All Pairs Shortest Path) 는 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 이다.
두 번째 SSP (Single Source Shortest Path) 알고리즘은 벨만 포드 알고리즘 (Bellman-Ford Algorithm) 이다.
다익스트라 알고리즘과 비교했을 때 가장 큰 특징은, 음의 가중치를 가지는 간선이 있어도 사용할 수 있다는 점이다.
주의할 점은, 음의 가중치를 가지는 순환고리가 있다면 최단 거리가 존재하지 않는다는 것이다.
첫 번째로 다루어 볼 SSP( Single Source Shortest Path, 단일 출발지 최단 경로 ) 알고리즘은 다익스트라 알고리즘 ( Dijkstra Algorithm ) 이다.
다익스트라 알고리즘은,
음의 가중치가 없는 그래프 에서
한 노드에서 다른 모든 노드들까지의 최단 거리 를 구하는 알고리즘이다.
이분 탐색은 이름 그대로 탐색 알고리즘의 종류이다.
포인트는, “필요 없는 부분은 쳐다보지 않아” 시간을 줄인다.
주요 조건으로는, 정렬이 되어있어야 한다.
보통 정보들은 정렬이 되어 있지 않기 때문에, 입력을 받고 정렬을 해주어야 하는데, 이 경우 정렬 알고리즘으로 O(logN)이 소요된다.
분할정복에 대하여 공부하던 도중, 점화식 형태로 시간복잡도 식이 나타날 때
이 시간복잡도를 계산할 수 있는 공식을 알게 되었다.
구하고자 하는 경우의 시간복잡도 T(n)이 다음과 같이 표현된다고 하자.
SWAP을 자주 사용하는 경우에는, 아래와 같이 임의의 type에 대한 SWAP 함수를 매크로로 지정해 놓으면 편하다.
(특히, C 언어에서!)
Greedy Algorithm (그리디 알고리즘, 탐욕 알고리즘) 은 문제를 작은 문제들로 나눈 후, 각 순간순간의 문제마다 최적의 결정을 택하는 알고리즘이다. 작은 문제들로 나누어 풀기 때문에, 일종의 DP (동적계획법) 문제의 예라고 생각할 수 있다.
우선, Dynamic Programming에 대해 알아보자.
Dynamic Programming (동적계획법) 이란, 쉽게 말해 큰 문제를 작은 문제로 나누어 푸는 것을 말한다. 여기까지는 분할정복 (Divide and Conquer)와 개념이 일치한다. Dynamic Programming의 핵심 포인트는, 작은 문제들을 반복해서 풀지 않는다는 것이다. 이는 시간을 크게 절약할 수 있다.
두 번째로 소개할 Dynamic Programming 알고리즘은 배낭 문제(Knapsack problem) 이다.
Knapsack Problem(배낭문제)란, 주어진 가치와 무게를 가진 짐들을 배낭에 넣을 때, 주어진 무게의 최댓값을 넘지 않으면서 가치의 합이 최대가 되도록 짐을 넣는 방법을 찾는 문제이다.
백트래킹(Backtracking)은 문제에서 주어지는 한정된 조건을 만족하는 해를 구할 때 사용하는 알고리즘이다.
문제에서 가능한 모든 해 집합을 대입하면, 당연히 만족하는 해를 찾을 수 있다. 여기서, 백트래킹을 이용하면 시간을 크게 단축시킬 수 있다. 쉽게 말하자면 다음과 같다:
노드의 유망성을 확인한 후, 유망하지 않으면 그 노드의 부모 노드로 돌아간다. 즉, 유망하지 않은 노드는 배제한다.
