본문 바로가기

분류 전체보기

알고리즘/문자열 2021. 2. 17. Aho–Corasick 문자열 \(S\)에서 하나의 문자열을 검색하는 것은 간단합니다. 그런데 검색해야 할 문자열이 여러개라면 어떨까요? 일반적인 문자열 탐색 알고리즘으로는 이를 빠르게 처리할 수 없으므로, 다른 방법을 생각해 내야 합니다. 문자열 \(S\)가 있고, 크기가 \(n\)인 문자열의 집합 \(T\)가 있습니다. \(S\)에서 \(T\)에 속한 문자열 중 적어도 하나를 검색할 수 있는지 여부를 알고 싶습니다. \(T\)의 크기가 1이라면, 우리는 KMP알고리즘을 이용해 \(O(|S|+|T|)\)에 검색이 가능하다는 것을 알고 있습니다. anz1217.tistory.com/56 KMP 대부분의 문자열 알고리즘은 어떤 문자열이 주어졌을 때, 이 부분 문자열 중 조건에 만족하는 특정한 문자열을 찾는 알고리즘입니다. 가장 ..
알고리즘/문자열 2021. 2. 16. Suffix Array와 LCP배열 문자열 \(S\)가 주어졌을 때, 이 문자열의 모든 접미사(suffix)를 사전순으로 정렬해 봅시다. 가장 단순한 방법은 \(|S|\)개의 suffix를 만든다음, 직접 정렬하는 것입니다. 이 방법을 이용하면 \(O(n^2 \log n)\)의 시간복잡도로 Suffix Array를 만들 수 있습니다. (\(n = |S|\)) www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 물론 이는 문자열의 길이가 조금만 길어져도 쓸 수 없는 방법이므로, 다른 방법을 생각해 봅시다. 다음과 같은 문자열이 있습니다. (0-index) \(S = \) "ab..
작곡 2021. 2. 15. Sepia Frame 다른 장르를 쓰고 있었는데, 다 처음 해보는거라서 배워야하는 것도 많고 진행이 잘 안되는것 같았다. 아직은 때가 아닌것 같아 내 근본을 찾아나서기로 했다.
알고리즘/문자열 2021. 2. 5. Manacher 길이가 \(n\)인 문자열 \(S\)가 있습니다. 이 문자열의 부분 문자열 중 팰린드롬인 것을 모두 알고 싶다면, 어떻게 하면 될까요? 나이브하게 \(O(n^3)\) 또는 \(O(n^2)\)로도 해결할 수 있겠지만, 이를 \(O(n)\)에 해결할 수 있는 Manacher 알고리즘에 대해 알아봅시다. \(S\)의 각 \(i\)번째 문자를 중심으로 하는 팰린드롬의 최대 반지름을 \(A_i\)라고 정의합시다. 또, \(j m\) 현재 얻을 수 있..
문제 풀이/Codeforces 2021. 2. 2. Educational Codeforces Round 103 A - K-divisible Sum Problem - A - Codeforces codeforces.com 두 정수 \(n, k\)가 주어진다. \(n\)길이의 양의 정수 배열 \(a\)를 만드는데, \(a\)의 모든 원소의 합이 \(k\)로 나누어 떨어져야 하고 \(a\)의 원소중 최대값이 최소가 되어야 한다. 이 때 \(a\)의 원소의 최대값을 구해야 한다. 해설은 생략한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; ll gcd(ll a, ll b) { for (; b; a %= ..
문제 풀이/Codeforces 2021. 1. 31. Codeforces Round #698 (Div. 1, Div. 2) A - Nezzar and Colorful Balls Problem - A - Codeforces codeforces.com \(n\)개의 공이 있고, 각각의 공에 정수가 비내림차순으로 쓰여져있다. 이 공을 색칠하려고 하는데, 같은 색으로 색칠된 공은 오름차순을 유지해야 한다고 할때, 필요한 서로 다른 색의 최소 개수를 구해야 한다. 같은 수가 쓰여진 공이 다른색으로 칠해지면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; l..
문제 풀이/Codeforces 2021. 1. 21. Codeforces Round #696 (Div. 2) A - Puzzle From the Future Problem - A - Codeforces codeforces.com \(n\)길이의 이진 문자열 \(b\)가 주어진다. 여기에 새로운 \(n\)길이의 이진 문자열 \(a\)를 만들어서, 두 이진 문자열을 더하려고 한다. 두 이진 문자열은 자리올림 없이 더해진다. (결과에 2가 포함되어 있을 수 있다) 더해진 다음, 연속된 같은 숫자들은 1개로 압축된다. 두 이진 문자열을 더했을 때 합이 최대가 되는 \(a\)를 알아내야 한다. 자릿수가 클 수록 큰 수가 되므로, 더한 후에 연속된 같은 숫자들이 없는것이 무조건 이득이다. 이를 만족하도록 앞에서부터 더한 결과가 최대한 큰 수가 되도록 \(a\)를 만들어 주면 된다. 1 2 3 4 5 6 7 8 9 10 1..
잡담 2021. 1. 19. 2020 IUPC 후기 2020 인하대학교 프로그래밍 경진대회 (IUPC)에 참가해 1등을 했다. 팀원 ANZ1217, ik_e, Envil_Saintan 타임라인 대회가 완전한 온라인으로 진행된다는 말을 듣고 우리 팀은 모이지 않고 디스코드로 대화하면서 대회를 진행하기로 했다. 나는 A번부터 차례대로, 나머지 팀원들은 각각 중간부터, 뒷문제부터 풀며 일단 문제들을 훑기로 했다. 대회 시작 직후에 A, B번을 봤는데 쉬운 문제였고, 바로 제출했다. 0:01 A정답 0:03 B정답 다음으로 C번을 봤는데 LCS인것 같았다. 바로 풀려다가 문제가 너무 더러워서... 다른걸 먼저 보고 오기로 했다. 뒤를 보던 ik_e가 J번이 쉬워보인다고 했다. 실제로 쉬운 문제이긴 했는데, 문제 디스크립션에 문제가 있었다. 문제에 매운 맛의 "단..

티스토리툴바