PS하는 kdy

https://dojoi.xyz/ko 라는 사이트에서 KOI 2차 모의고사를 출제하였다고 하여 고등부를 참가해보게 되었다. 시험 시간은 4시간 반이고, 대략적으로 14:00 - 18:30 정도의 시간을 잡고 참가하였다. (해당 모의고사는 실제 KOI와는 전혀 무관합니다.) 고등부의 문제는 이렇게 4문제였다. [0:00 - 0:44] A. 히스토그램 (AC, 100)이번 출제자 중 한 명인 lunarlity가 저번에 만든 히스토그램 관련 PS 문제가 NM개라고 해서 문제를 보자마자 lunarlity가 냈겠다는 생각이 들었다. 일단 X번 이하 시행으로 가능한 경우를 탐색하는 것은 굉장히 어렵기 때문에 Parametric Search를 통해 문제를 풀어야겠다는 아이디어를 낼 수 있었다. 그러면 답이 p보..

올해도 작년처럼 서울대학교 컴퓨터 연구회 SCSC에서 주최하는 SCPC(SCSC Computer Programming Contest)가 열려 참가했습니다. 작년에는 별 생각 없이 지원해서 검수했던 대회였는데, 올해는 참가해야겠다는 생각이 들어서 신청했습니다. 닉네임을 뭘로 할지 조금 고민을 하면서 신청 폼을 작성할 당시 옆에 있던 친구한테 스코어보드 닉네임을 추천해 달라고 했는데, admin을 얘기하길래 바로 그대로 admin을 닉네임으로 해서 참가했습니다. 제가 참여한 디비전은 Division 1입니다. Codeforces 오렌지를 찍었기 때문인데, 제가 그렇다고 수많은 GM이나 IGM들과 경쟁했을 때 경쟁력이 있는 것도 아니라서 높은 상은 받기 어려울 것이라고 생각하고 대회에 임했습니다. (Divi..

지난 5월 3일 KAIST에서 진행된 2026 Kaist Run Spring Contest에 온사이트로 참가하였다. 백준이 없어져 기록을 남기기도 어려워졌기 때문에 이렇게라도 기록을 남긴다. 일단 서울에서 출발해야 했기 때문에, 오고가는 열차표를 예매했다. 서울역 -> 대전역 09:33 - 10:42 표와 서대전역 -> 용산역 20:39 - 21:54 표를 예매했다. 서울역에는 꽤 빨리 도착해서 시간이 좀 남았다. 그래서 맛있게 호두과자도 하나 사먹고 출발했다. 맛은 약간 안에 들어있는 팥이 고체보다 액체에 가깝다고나 할까..? 굉장히 물러서 평소에 먹던 것과 느낌이 조금 달랐는데 이것도 나름대로 맛있었다. 가는 길에는 얼마 전 재미있게 본 영화인 의 원작인 책을 조금 읽기도 하고, 리체스에서 래피드 경..

이 글은 독자가 trie 자료 구조에 대해 이미 알고 있다는 전제 하에서 시작한다. trie라는 자료 구조를 모른다면 이 글을 읽기 전에 다른 블로그를 읽고 https://www.acmicpc.net/problem/14725와 같은 문제를 해결해본 후 이 글을 읽는 것을 권장한다. Trie라는 자료 구조를 일반적으로 구현할 때에는 Node 클래스를 만들고 여기에 딕셔너리 혹은 리스트가 들어가서 여기에 다시 Node가 저장되는 형태로 구현한다. 하지만 이렇게 리스트나 딕셔너리를 많이 만들 경우 메모리 초과가 나기 십상이며, 접근 자체에도 긴 시간이 걸린다. 이를 개선하는 대표적인 방법으로, Trie 자료 구조를 1차원 배열을 이용해서 구현하는 방식이 있다. 우리가 일반적으로 알고 있는 트라이의 구조에 인..

이번에는 지난 글에서 구현하는 방법을 알아본 접미사 배열과 lcp 배열을 어떻게 활용하는지 알아볼 것이다.문제를 풀어보기 전에는 suffix array와 lcp array가 도대체 어떤 의미를 가지나.. 싶기도 한데, 우리는 보통 접두사, 접미사보다도 부분 문자열에 관련된 문제를 많이 해결하게 된다. 이때, 우리가 주목해서 기억해야 하는 것은 부분 문자열은 결국 접미사의 접두사라는 것이다. 그러면 suffix array를 구했고, suffix array에서 lcp를 구한 것은 공통된 접미사의 접두사, 즉 공통된 부분 문자열에 관한 정보를 얻었음을 의미한다. https://www.acmicpc.net/problem/1605이 문제는 지난번 라빈 카프를 설명했을 때에도 다루었던 문제로, 부분 문자열 내에서 ..

이번에는 접미사 배열과 lcp 배열에 대해 살펴보고자 한다. 바로 본론으로 들어가자. 먼저, 접미사 배열은 어떤 문자열 $S$가 주어졌을 떄, 이 문자열의 모든 접미사를 사전순으로 정렬할 때, 각 접미사가 시작한 인덱스를 저장한 배열이다. 예를 들어서 문자열 ABRACADABRA를 살펴보자. 이 문자열의 모든 접미사는 아래와 같다. ABRACADABRA 0 BRACADABRA 1 RACADABRA 2 ACADABRA 3 CADABRA 4 ADABRA 5 DABRA 6 ABRA 7 BRA 8 RA 9 A 10 이를 사전순으로 정렬하면 아래와 같은데, 이때 정렬된 상태에서 각 문자열이 원래 몇 번째 접미사였는지 각각 정수를 저장..

이번에 다뤄볼 알고리즘은 해싱, 그 중에서도 라빈 카프 방식에 대해 살펴볼 것이다. 서론은 짧게 하고 빠르게 본론으로 넘어가보자.해싱 (Hashing)해싱은 문자열을 해시 함수에 넣어서 특정한 값으로 추출하는 것을 의미한다. 이때 가장 중요한 것은 같은 문자열을 같은 해시 함수에 여러 번 넣어 추출한 결과는 일정해야 한다는 점이다. 해싱을 하면 어떤 부분이 좋을까? 바로 비교 시간복잡도를 줄일 수 있다. "abcba"라는 문자열과 "abcbd"라는 문자열이 서로 같은지 다른지 비교하려고 한다. 일반적으로는 문자열의 가장 앞부터 비교하면서 5번째 문자까지 비교했을 때 비로소 두 문자열이 다르다는 것을 판단할 수 있다. 하지만 해싱을 이용해서 미리 두 문자열에 대해 정수 형태로 값이 나오는 해시 함수 결괏값..

이번에 글을 적어볼 알고리즘은 매내처 알고리즘이다. 이 역시 바로 본론으로 들어가자면, 매내처 알고리즘은 어떤 문자열 $S$가 주어졌을 때, $S$의 부분 문자열 (앞뒤에서 0개 이상의 문자를 떼어내 만들 수 있는 문자열) 중 팰린드롬인 것을 빠르게 탐색하는 알고리즘이다. 그리고 실제 구현은 Z 알고리즘과 비슷하게 이루어진다. Manacher 알고리즘은 부분 문자열 중 팰린드롬을 팰린드롬의 중심을 기준으로 탐색한다. 예시를 들어서 설명하자면, 팰린드롬 abcba의 중심은 c이고, abcba가 팰린드롬임을 알면 중심을 기준으로 대칭인 c, bcb가 팰린드롬이라는 사실을 이용할 수 있는 것이다. 이때 위 팰린드롬의 반경은 $2$이다. 왜냐하면 c를 중심으로 오른쪽으로 두 칸, 왼쪽으로 두 칸이 서로 대칭이라..

지난번에 다루었던 KMP 알고리즘에 이어서, 이번에는 Z 알고리즘에 대해 다뤄보고자 한다. 바로 본론으로 들어가보자. Z 알고리즘은 문자열 $S$가 주어졌을 때, 문자열 $S$의 접미사와 문자열 $S$의 최대 공통 접두사의 길이를 빠르게 구하는 알고리즘이다. 예시를 들면 아래와 같다. 위 표와 같이 $Z[i]$에 $i$번째 문자로 시작하는 접미사와 원본 문자열의 공통 접두사의 최대 길이를 저장하는 알고리즘이 Z 알고리즘이고, Z 알고리즘으로 구한 이 array를 보통 Z array라고 부른다. 이 역시 Naive하게 구현하면 문자열의 길이가 $N$일 때 $O(N^2)$이 소요된다. Z 알고리즘은 이때 불필요한 탐색을 최적화하여 시간복잡도를 $O(N)$으로 줄인다. 그 원리는 아래와 같다. idx ..

지난 글에서 KMP 알고리즘의 원리와 시간복잡도를 알아보았고, 이를 바탕으로 문자열을 검색하는 기본 문제를 풀어보았다. 이번 글에서는 KMP 알고리즘을 활용하는 문제들을 몇 가지 살펴볼 것이다. https://www.acmicpc.net/problem/1305 문제는 단순하다. 광고 문구가 AABA이고 광고판이 9글자까지 표현 가능하다면 광고판에는 광고 문구를 반복해서 이어붙인 문자열이 보이고, 1칸씩 이동하는 형태이다. 즉, 아래와 같이 광고판에 문구가 뜨는 것이다.[A A B A][A A B A][A A B A][A A B A][A A B A][A A B A][A A B A][A A B A][A A B A] 광고판의 어느 순간의 모습이 주어지면 광고 문구로 ..