강한 연결 요소 (SCC, Strongly Connected Component) 란, 유향 그래프에서 정점의 부분집합이 부분집합 내의 다른 모든 정점에 대해 방문 가능한 경우를 말한다. 쉽게 말해 사이클이 생기는 그룹을 엮으면 강한 연결 요소가 된다. 다음 그래프에서 사이클이 생기는 그룹을 엮어보자. 이 사이클이 생기는 그룹을 하나의 정점으로 보고 문제를 해결해야 하는 경우가 생길 수 있다. 따라서 이렇게 엮은 그룹들을 정점으로 치환하면 다음과 같은 그래프로 볼 수 있다. 정점 안에서 엮여진 하위 정점들은 그 정점 안이라면 언제든 방문 가능하다. 이렇게 강한 연결 요소로 묶으면 사이클이 없는 유향 그래프로 바라볼 수 있다는 특징이 있다. 이제 SCC 를 두 가지 방법으로 구현해보자. 타잔 알고리즘SCC ..

최소 공통 조상 (LCA, Lowest Common Ancestor) 알고리즘은 트리 구조 안에서 특정 정점 두 개의 공통 조상 정점 중 가장 가까운 공통 조상 정점을 찾는 알고리즘이다. 단순히 두 정점의 깊이를 맞춘 뒤 한 칸씩 동시에 올라가다가 마주치는 공통 조상이 최소 공통 조상인지라 쉽게 구할 수 있지만, 이동해야 할 정점이 많은 경우 희소 배열을 이용해 빠르게 최소 공통 조상을 구할 수 있다. LCA먼저, 7번 정점과 11번 정점의 공통 조상을 찾아보자.  7번 정점과 11번 정점이 공통으로 가지는 조상 정점은 1번 정점, 2번 정점, 4번 정점이 있다. 이 정점들은 모두 7번 정점과 11번 정점에서 시작해서 루트를 향해 올라가다가 마주칠 수 있는 공통되는 정점이다. 그 중에서도 시작 지점과 가..

희소 배열 (Sparse Table) 은 그래프 상에서 N번째 앞에 있는 정점을 빠르게 찾을 수 있는 자료 구조 기법이다. 다음과 같은 유향 그래프가 있다고 가정해보자. 모든 정점은 나가는 방향의 화살표를 1개 가지고 있다. 이 모든 정점에서 1번 이동했을 때의 정점은 각각 어디일까? 0번 이동12345671번 이동2365246 이와 같은 결과를 얻을 수 있다. 화살표를 따라가다 보면 2번 이동했을 때, 3번 이동했을 때... 도 얻어낼 수 있다.0번 이동12345671번 이동23652462번 이동36423543번 이동6453625  이를 코드로 표현하면 다음과 같다.n = 7 # 정점 개수m = 3 # 3번 이동했을 때table = [[0 for _ in range(n+1)] for _ in range..

커누스-모리스-프랫 알고리즘 (Knuth–Morris–Pratt algorithm, KMP) 은 문자열 S 에서 문자열 A 를 찾고자 할 때 단순히 모든 경우를 다 비교해보면서 찾는 방식 보다는 접두사와 접미사를 이용해 불필요한 문자열 탐색 횟수를 줄여 문자열을 효율적으로 찾아낼 수 있는 문자열 매칭 알고리즘이다. 하나씩 비교하는 문자열 매칭문자열 S의 길이를 N, 문자열 A의 길이를 M이라 할 때, 문자열 S 에서 문자열 A를 찾을 때의 시간 복잡도는 O(NM) 이다.S = input()A = input()for i in range(len(S)): for j in range(len(A)): if S[i+j] != A[j]: break if j == len(A) - 1: print(i)# I..