💡 최단 경로 코딩테스트
가장 짧은 경로를 찾는 알고리즘
우선,
-
한 지점에서 특정 지점으로 까지의 최단 경로를 구해야하는 경우
-
모든 지점에서 모든 지점까지의 최단 경로를 구해야하는 경우
인지 생각해본다.
또,
- 최단 경로의 합을 구하는 경우
- 최단 경로에서 거쳐온 노드들을 구하는 경우
를 캐치한다.
> > 앞서 공부한 그리디, 다이나믹은 최단경로 알고리즘에서 그래도 적용 된다.
💡 다익스트라 알고리즘
기준 노드에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하여 갱신한다는 특징이 있다.
방법 1. 구현하기 쉽지만 느리게 동작하는 다익스트라 O(n^2)
방법 2. 구현하기 조금 어렵지만, 빠르게 동작하는 다익스트라 (우선순위 힙 이용) O(elogv)
우선순위 힙을 이용하면 방문 여부의 노드를 만들 필요가 없고, 이미 정렬되어있기 때문에 '방문하지 않은것들중 가장 작은 노드'를 찾을 필요도 없다.
>> 다익스트라는 방법1, 방법2를 자다가 말하면 나올 정도로 외워나야 한다.
💡 플로이드 알고리즘
2차원 리스트를 이용하여 모든 지점에서 다른 모든 지점까지의 최단 거리를 구할 때 사용하는 알고리즘. O(n^3)
- 핵심 점화식
$$ Graph [a][b] = min(Graph [a][b], Graph [a][k] + Graph [k][b]) $$
거리 문제에서 시간복잡도가 O(n^3)인 만큼 주어진 최대 데이터가 굉장히 작다면 플로이드를 이용하는 것을 생각해보아야 한다.
💡 시간제한 참고
파이썬 => 1초 20000000번 연산
데이터 20,000,000 => O(N)
데이터 1,000,000 => O(NlogN)
데이터 4~5,000 => O(N^2)
데이터 100~200 => O(N^3)