Dijkstra

그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘

• 두 도시 사이의 최단 경로 찾기
• 네트워크 라우팅 프로토콜에서 널리 이용
• 가중치가 있는 경우 가중치의 합이 최소가 되는 경로

시간 복잡도

우선순위 큐 사용

• O(|E|+|V|\log |V|) (|E|는 변의 개수)

미사용

• O(|V|^2) (|V|는 꼭짓점의 개수)

방법

우선순위 큐와 최단 거리를 저장할 배열

1. 노드의 개수만큼 배열을 생성
   • 본인 노드는 0, 나머지는 무한대로 초기화
2. 우선순위 큐 생성
   • 첫 노드를 0으로 생성
3. 우선순위 큐에서 값(가중치)을 꺼낸 후 거리 + 가중치를 구해 최단 거리 배열의 값과 비교
   • 작은 경우 배열을 업데이트하고 우선순위 큐에 넣기
4. 큐가 빌 때까지 3을 반복

동적계획법 (DP)

Dynamic Programming
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

• 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 빠르게 풀이
• 가능한 모든 방법을 고려해야 한다는 단점
  - 이 단점을 극복하기 위해 그리디 알고리즘이 등장

---

LIS

최장 증가 부분 수열 (Longest Increasing Subsequence)
수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제

• 동적 계획법으로 풀 수 있음

LCA

최소 공통 조상(Last Common Ancestor)
집단에 속하는 모든 개체의 공통 조상이 되는 최근의 개체

복잡도

• 크기가 N인 트리에서 O(logN)
• 최악의 경우 O(N) -> 한쪽으로 치우친 경우

방법

• 부모 리스트를 노트부터 비교해서 다른 부모를 만나면 직전 노드가 LCA

---

위키백과 - LIS
LIS
DP
Advanced Operators
2의 보수