플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
플로이드-워셜 알고리즘은 다익스트라 알고리즘과 비슷하게 최단경로(shortest-path)를 탐색하는 알고리즘이다.
Algorithm
최소 공통 조상 알고리즘 2 (Lowest Common Ancestor, LCA)
이전 글에서 설명했던 LCA 알고리즘의 방법 중 두번째 알고리즘을 설명하겠다. 첫번째 방법은 이해도 쉽고 구현도 간단하나 최종 O(NM)의 시간복잡도로 시간이 너무 오래 걸린다는 단점이 있다. 이를 최적화 하는 방법을 알아보자.
최소 공통 조상 알고리즘 (Lowest Common Ancestor, LCA)
LCA 알고리즘은 트리(Tree) 자료구조에서 두 노드의 가장 가까운 조상을 찾는 알고리즘이다.
최장 증가 부분 수열 - LIS(Longest Increasing Subsequences)
개요 주어진 수열에서 최장 증가 부분 수열(이하 LIS)를 구하는 방법을 알아보자. 어떠한 수열이 주어졌을 때, 일부를 뽑아 새로 만든 수열을 “부분 수열”이라고 한다. 이 수열이 오름차순을 유지하면 “증가 부분 수열”이다. 우리는 증가 부분 수열 중에서 가장 긴 증가 ...