코딩테스트 알고리즘별 전략 및 요약 (수정 중...)

코딩테스트 알고리즘별 전략 및 요약 (수정 중...)

그래프

다익스트라 최단경로 찾기

단일 시작점 알고리즘

양수 가중치

사이클 존재

INF 사용

BFS 처럼 큐를 통해 루프

우선순위 큐 사용(가중치,end노드)

일차원 dp 사용 O(|E||log|V|)

벨만-포드 최단경로 찾기

단일 시작점 알고리즘

음수 가중치

음수 사이클 판별

INF 사용

v, mid, end 순서로 루프

V-1 번의 완화 과정, 1번의 음수사이클 판별 과정 (완화가 실패할 때까지 완화함.)

일차원 dp 사용 O(VE)

플로이드 워셜 모든 쌍 최단 거리 알고리즘

음수 사이클 없으면 사용가능(음수 사이클 있으면 벨만 포드 N번하기)

메모리 초과 날 가능성 존재

INF 사용

k , i , j 순서로 루프

구현 간단 DP[i][j] = min(DP[i][k] + DP[k][j], DP[i][j])

이차원 dp 사용 O(V^3)

위상 정렬 DAG 만족해야함.(방향,비순환 그래프)

방향성을 거스르지 않고 정점 나열

indegree차수를 가지는 배열

indegree가 0인 값을 큐에 넣고 BFS

결과가 유일하지 않음

from http://guccin.tistory.com/115 by ccl(A) rewrite - 2021-08-20 17:26:18