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

그래프
다익스트라	그리디, DP로 분류되기도 함 단일 시작점 알고리즘 (최단거리) 양수 가중치 사이클 존재 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 결과가 유일하지 않음
MST(Minimum Spanning Tree)	그래프(사이클 존재)를 트리 만들기 (가장 적은 비용으로 모든 노드를 연결) 우선순위 큐 사용 크루스칼 or 프림 크루스칼(가중치 순으로 우선순위 큐사용하여 유니온 파인드(사이클을 만들지 않기 위해) 실행)
LCS(Longest Common Subsequence)	최장 공통 부분수열 "ABCDEF" "GBCDFE" => "BCDF" if A[i] == B[j]:     dp[i][j] = dp[i-1][j-1]+1 else:     dp[i][j] = max(dp[i][j-1], dp[i-1][j])
LIS(Longest Increasing Subsequence)	증가하는 가장 긴 부분 수열 dp로 모든 경우를 계산하는 경우 O(n**2) dp에 개수별 최솟값을 넣고 bisect로 갱신하는 경우(n log n) 1. [2,5,10] 1개의 최솟값은 2, 2개인경우 최솟값5, 3개인 경우 최솟값 10 2. 만약 11일 들어오는 경우 가장 마지막 10보다 크므로 [2,5,10,11] 로 갱신 3. 만약 4가 들어오는 경우 bisect로 5의 위치가 적합, 5보다 작으므로 [2,4,10,11] 로 갱신