Algorithm

위상 정렬은 방향성 비순환 그래프(DAG)에서 노드의 순서를 정하는 알고리즘이다. 순서를 지켜야하는 작업을 차례로 수행해야할 때, 작업의 순서를 결정해주는 알고리즘이다. 답이 여러개 존재할 수 있음에 유의해야한다.

 c++ set 라이브러리에 정의되어 있는 자료구조인 set, multiset에 대해서 정리해보자. 먼저 set은 노드기반 이진 탐색 트리 구조로 삽입, 삭제, 탐색 모두 O(logN)의 복잡도를 가진다. set은 요소가 고유하고 자동으로 정렬되어야 할 때 유용하게 사

 유니온-파인드(Union-Find) 알고리즘은 서로소 집합(Disjoint Set)을 관리하기 위한 데이터 구조로, 여러 개의 원소가 각각 독립적인 집합에 속해 있을 때, 두 원소가 동일한 집합에 속하는지 판별하거나 두 집합을 합치는 연산을 수행할 수 있는 기법이다.

 에라토스테네스의 체(Sieve of Eratosthenes)는 소수를 찾는 알고리즘으로, 주어진 범위 내의 모든 소수를 효율적으로 찾는 방법이다.

 카데인 알고리즘(Kadane's Algorithm)은 연속된 부분 배열에서 최대 합을 찾는 효율적인 방법이다. 즉, "최대 연속 부분 배열(Maximum Subarray) 문제"를 해결하는 데 사용된다. 

 LCS 알고리즘은 두 문자열에서 공통된 부분 수열 중 가장 긴 부분 수열을 찾는 문제이다. 문자열 비교 문제에서 기본적으로 사용되는 알고리즘 중 하나로, 여러 응용 문제에서도 중요한 역할을 한다.