DP

최단 경로 알고리즘 최단 경로 알고리즘은 다음과 같이 경우를 나눠서 사용하는 알고리즘이 다르다. 1. 단일 출발점에서 다른 모든 정점까지의 최단 경로를 구하는 경우 a. Dijkstra's Algorithm (다익스트라 알고리즘): 간선의 양의 가중치만 허용 b. Bellman-Ford Algorithm (벨만-포드 알고리즘): 간선의 양, 음의 가중치 모두 허용 c. BFS : 간선의 가중치가 없는 경우 2. 그래프 내의 모든 정점 쌍 간의 최단 경로를 구하는 경우 a. Floyd-Warshall (플로이드-워셜 알고리즘): 간선의 양, 음의 가중치 모두 허용 b. Johnson's Algorithm (존슨 알고리즘): 간선의 양, 음의 가중치 모두 허용 이 중 이번에는 플로이드-워셜 알고리즘에 대해 ..

최장 증가 부분 수열이란? 어떤 수열이 나열되어 있을 때, 그 배열 순서를 유지하면서 점점 커지는 부분 수열의 가장 길이가 긴 수열을 구하는 문제. ex) 3, 1, 5, 2, 4, 6 이라는 수열이 있을 때, 3, 1, 5, 2, 4, 6 --> [1, 2, 4, 6] 이라는 해를 구할 수 있고, 길이는 4이다. 접근법 + Java 코드 1. 완전 탐색 수열의 모든 부분집합을 구한 후, 길이가 긴 수열부터 그 부분집합이 증가하는 수열인지 확인한다. 이 방법은 부분집합을 전부 구하는 Brute-force 방법이기 때문에, 시간복잡도는 O(2^n)이라고 할 수 있다. ex) [3, 1, 2, 4, 5, 6] -> [3, 1, 2, 4, 5] , [3, 1, 2, 4, 6] , [3, 1, 2, 5, 6] ..

0/1 Knapsack Problem이란? 용량이 W인 배낭, N개의 물건(각 물건은 무게(w)와 가치(v)가 주어짐) 1. 배낭에 담을 물건의 무게의 합이 W를 초과하지 않으면서 2. 담을 수 있는 최대 가치를 찾는다. 물건을 쪼갤 수 있다면 > Fraction Knapsack Problem 물건을 쪼갤 수 없다면 > 0/1 Knapsack Problem 접근법 DP 중에서도 작은 문제의 해로 큰 문제의 해를 찾는 상향식 접근법을 사용한다. 그렇다면 점화식을 구해야 한다. 부분 문제를 정의해 보면, 물건을 담을 수 있는 경우와 담을 수 없는 경우로 나눌 수 있고 담을 수 있는 경우에는 물건을 넣기로 결정하거나 물건을 안 넣기로 결정하는 경우로 또 나눌 수 있다. 정리하면, 1. 물..