문제 출처 : https://www.acmicpc.net/problem/9248 9248번: Suffix ArraySuffix Array란, 문자열 S가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들어, 문자열 S=banana의 접미사는 아래와 같이 총 6개가 있다. Suffix i banana 1 anana 2 nana 3 ana 4 na 5 a 6 이를 Suffix 순으로 정www.acmicpc.net언어 : Kotlin 문제 설명 :Suffix Array란, 문자열 S가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들어, 문자열 S=banana의 접미사는 아래와 같이 총 6개가 있다.Suffix ibanana1anana2nana3ana4na5a6 이를 Suffix 순으로 정렬하면 아..
1. KMP(Knuth-Morris-Pratt Alogorithm) 알고리즘이란?흔히 발견자 Knuth, Morris, Pratt의 앞글자를 딴 KMP로 읽히는 이 알고리즘은 전체 문자열에서 특정 문자열을 찾는 방식으로 오토마타(Finite-state automaton based search) 알고리즘과 비슷한 형식을 가지나 메모리와 시간 양측에서 모두 이득을 볼 수 있어 문자열 검색 알고리즘에서 브루트포스 외에 흔히 사용되는 알고리즘이다. 시간복잡도는 O(N + M)이다. 2. 구현 방식예를 들어, "ABABABCD" 라는 문자열과 "ABABC"라는 패턴이 존재할 때 KMP 알고리즘으로 문자열을 검색하면 다음과 같은 방식으로 이루어진다. ABABABCDABABC ABABABCD AB..
정렬 알고리즘이란? 말그대로 정렬을 위한 것으로, 정렬은 일종의 조건에 맞게 요소들을 나열하는 것을 의미한다. 이 정렬 알고리즘은 종류가 다양한데 대표적인 것들을 하나씩 짧게 알아보도록 하자. 1. 선택 정렬(Selection Sort) 선택정렬 알고리즘은 앞 인덱스부터 시작하여 마지막 인덱스까지 값을 확인하며 최솟값을 비교하는 방식이다. 마지막에 도착했을때 최솟값을 앞 인덱스에 넣어 앞 쪽부터 정렬되도록 만든다. 시간복잡도는 O(n ^ 2)이다. var min_idx = 0 for (i in 0..arr.lastIndex-1) { min_idx = i for (j in i+1..arr.lastIndex) { if (arr[min_idx] > arr[j]) min_idx = j } val term = a..