코딩테스트 - 패스트캠퍼스 챌린지 18일차

수강한 강의
Chapter 20 그래프 고급 탐색 알고리즘
- 최단 경로 알고리즘 이해

학습 후기
최단 경로 알고리즘.. 강의를 다 듣고 학습후기를 쓰는데 오늘 강의는 진짜 어려운 것 같다. 하지만 알고리즘 테스트를 통과하기 위해서는 꼭 이해하고 구현할 수 있도록 해야 하기 때문에 강의 들을걸 잘 정리하고 넘어가자

최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제다. 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적이다.

최단 경로 문제 종류
1. 단일 출발 최단 경로 문제: 특정 노드 A에서 출발, 그래프 내 모든 다른 노드에 도착하는 가장 짧은 경로를 찾음.
2. 단일 도착 최단 경로 문제: 모든 노드에서 출발, 특정 노드 A로 도착하는 가장 짧은 경로를 찾는 문제.
3. 단일 쌍 최단 경로 문제: 노드 A에서 노드 B의 최단 경로를 찾는 문제
4. 전체 쌍 최단 경로 문제: 그래프 내의 모든 노드 쌍에 대한 최단 경로를 찾는 문제

최단 경로 알고리즘 - 다익스트라 알고리즘
최단 경로 문제 종류 중 1번에 해당, 하나의 노드에서 모든 노드에 도착하는 가장 짧은 거리를 구하는 문제

다익스트라 알고리즘 로직
시작 노드를 기준으로 연결되어 있는 정점들을 추가해 가며 최단 거리를 갱신한다. 다익스트라 알고리즘의 다양한 변형 로직이 있지만, 가장 개선된 우선순위 큐를 사용하여 다익스트라 알고리즘을 구현하는 방식을 설명한다.
우선순위 큐를 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 된다.
1. 첫 노드를 기준으로 배열을 선언하여 첫 노드에서 각 노드까지의 거리를 저장
- 초기 첫 노드의 거리는 0(자기 자신까지의 거리), 나머지는 Infinite(무한대)로 저장함
- 우선순위 큐에 초기 노드(첫 노드, 거리 0)만 넣는다.
2. 우선순위 큐에서 노드를 꺼낸다.
3. 2에서 꺼내진 노드의 인접 노드에 대해, 인접 노드로 가는 거리와 첫 노드에서 인접 노드까지 가는 최소 거리를 저장한 리스트의 거리를 비교하여 더 짧은 거리를 리스트에 저장한다.
4. 3에서 최소 거리가 업데이트될 경우 해당 노드를 우선순위 큐에 넣는다.
5. 리스트에 저장된 거리가 더 짧은 경우 해당 노드와 인접한 노드 간의 거리는 계산하지 않는다.
6. 2 ~ 5 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복한다.

우선순위 큐는 java.util.PriorityQueue 클래스를 사용하여 구현한다. PriorityQueue에서 내부적인 정렬 기능을 사용할 때는 해당 객체의 Comparable 인터페이스의 compareTo() 메서드를 호출하므로, 객체 간 정렬 기준을 정의하기 위해 Comparable 인터페이스의 compareTo() 메서드를 정의한다.

시간 복잡도
다익스트라 알고리즘의 시간 복잡도는 두 가지 과정에 영향을 받는다.
1. 각 노드마다 인접한 간선들을 모두 검사하는 과정
2. 우선순위 큐에 노드/거리 정보를 넣고 삭제하는 과정
총 시간 복잡도는 O(E) + O(E log E)로 O(E log E)가 된다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.