0. 최단 경로최단 경로간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로하나의 시작 정점에서 끝 정점까지의 최단 경로다익스트라(Dijkstra) 알고리즘음의 가중치를 허용하지 않음벨만-포드(Bellman-Ford) 알고리즘음의 가중치 허용모든 정점들에 대한 최단 경로플로이드-워셜(Floyd-Warshall) 알고리즘이번에는 이 중에서 플로이드-워셜(Floyd-Warshall) 알고리즘을 알아본다.1. 플로이드-워셜(Floyd-Warshall) 알고리즘모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.시작 정점에서 목표 정점의 최단 경로를 계산할 때, 다른 정점을 경유했을 때 비용을 비교하면서 구하는 방식이다.DP 기법을 사용한 알고리즘으로 인..

0. 최장 증가 부분 수열 LIS최장 증가 부분 수열 LIS어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있을 때, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열을 추출하는 문제를 의미한다.ex) 3, 2, 6, 4, 5, 1의 배열의 LIS 해 중 하나는 2, 4, 5이다.이 문제를 부분집합으로 접근하면 시간 복잡도가 O(2^n)이므로, DP나 이진 검색을 활용하여 접근하는 것이 효율적이다.1. DP를 활용한 접근각 원소까지의 LIS 길이를 저장하는 배열인 LIS라고 할 때, LIS(i)를 이전 단계들과의 관계로 표현해보자.Case 1: LIS(i)가 a_i를 부분 수열의 마지막으로 포함하지 않는다면 → LIS(i) = LIS(i - 1)Case 2: LIS(i)가 a_i를 부분 수..

0. 트라이(Trie)트라이(Trie)는 문자열을 저장하고 호율적으로 탐색하기 위한 트리 형태의 자료구조이다. 트라이는 Retrieval Tree에서 나온 단어로 검색할 때 사용되는 자동완성 기능, 사전 검색 등 문자열 탐색에 특화되어 있다.단, 각 노드에서 자식들에 대한 배열을 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다.(메모리 복잡도에서 비효율적임)0-1. 트라이 자료구조의 노드 구조트라이의 노드는 4개의 정보를 담고 있다.key: 현재 노드의 알파벳data: 현재 노드까지의 결과 -> 완성된 문자열endOfWord: 현재 노드로 이루어진 단어가 있는지 판단하는 변수children: 자식 알파벳 노드들1. 트라이(Trie) 연산1-1. 삽입첫번째 문자가 trie head의 자식 노드에 있는..

0. 0/1 Knapsack배낭에 물건을 쪼개지 않고 담는 문제를 0/1 Knapsack이라고 한다.이 문제를 부분집합으로 풀게 되면 시간 복잡도가 O(2^n)이므로, DP로 접근하는 것이 효율적인 문제가 된다.1. 0/1 Knapsack 정의W = 배낭의 용량(v_i, w_i) = (물건의 가치, 물건의 무게)K[i, w] = 물건 i까지 고려했을 때, 배낭의 용량이 w일 때의 최대 가치 1-1. K[i, w] 수식 정의1-2. i번째 물건을 고려할 때1-3. 의사 코드배낭의 용량 Wn개의 물건과 각 물건 i의 무게 w_i와 가치 v_i, (단, i = 1, 2, ..., n)K[n, W]For i in 0 -> n : K[i, 0] W : K[0, w] n For w in 1 -> W If..