이번에는 LCP 배열에 대해 알아보자! LCP 배열을 이해하기 위해서는 이전에 쓴 글인 접미사 배열을 우선적으로 이해해야한다. 2023.03.27 - [Algorithm] - [Algorithm] 맨버-마이어스 알고리즘(Suffix Array) [Algorithm] 맨버-마이어스 알고리즘(Suffix Array) 접미사 배열이란 특정 문자열에 대한 접미사들을 모두 나열한 뒤, 사전 순으로 정렬을 진행한 배열을 의미한다. 일반적으로 접미사 배열을 만드는 방법은 다음과 같다. 문자열에 대해 모든 접미 codable.tistory.com 위의 글에서 들었던 예시인 banana를 사용하자. LCP 배열을 만들기 위해서는 우선 해당 접미사가 정렬된 Suffix 배열에서 어느 위치에 있는지를 기록해야한다. 이를 위..
접미사 배열이란 특정 문자열에 대한 접미사들을 모두 나열한 뒤, 사전 순으로 정렬을 진행한 배열을 의미한다. 일반적으로 접미사 배열을 만드는 방법은 다음과 같다. 문자열에 대해 모든 접미사들을 만들어준다. 만들어진 접미사들을 맨 앞글자를 기준으로 정렬한다. 이후 정렬 기준을 앞에서 2번째 문자, 3번째 문자 ... 로 늘려가면서 최대 문자열의 길이인 n번째 문자까지 바꿔가며 정렬을 진행한다. 위의 과정을 따르면, 한번 정렬을 진행하는데 $O(n log n)$ 만큼의 시간이 걸리고, 정렬을 최대 문자열의 길이만큼 반복한다고 했으므로 총 시간복잡도는 $O(n^2 log n)$ 과 같이 나타날 것이다. 이를 맨버-마이어스 알고리즘을 통해 $O(n log^2 n)$의 시간복잡도로 단축시킬수 있다. 이제 정렬이 ..
이번에 풀 문제는 그래프 수정 문제이다. 위상 정렬을 활용하는 문제인데, 일단 문제를 보고 가자. - N개의 정점으로 구성된 그래프가 입력으로 주어진다. 이때 노드의 번호는 1보다 크거나 같고 N보다 작거나 같다. - 만약 노드 U에서 노드 V로 연결되는 간선이 존재한다면, 노드 V의 번호는 노드 U의 번호보다 커야 한다. - 위의 조건을 만족하도록 노드의 번호를 바꾸고, 원래의 1번 노드부터 N번 노드까지 각각 바뀐 노드의 번호를 출력해야 한다. 위의 말만 봐서는 문제에서 원하는 것이 무엇인지 정확히 감이 오지 않을 수 있다. 다음 입력값을 그림으로 나타내서 이해해 보자! n = 5 node1 : 00110 node2 : 00001 node3 : 00000 node4 : 01000 node5 : 000..
