https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 이 문제를 보고, '반복 가능한 최소 길이의 부분 문자열' 을 찾으면 될 것 같았다. 없으면 1 출력해주고 어떻게 찾을까 고민하던 중, 실패함수의 마지막 값은 문자열 전체를 봤을 때의 최장 부분 문자열을 구한 것이므로 내가 찾고자 하는 '반복 가능한 최소 길이의 부분 문자열'의 길이는 전체 문자열 - 실패함수의 마지막 값을 통해 구할 수 있다! 그래서 전체 문자..
https://www.acmicpc.net/problem/16570 16570번: 앞뒤가 맞는 수열 수열 (a1, a2, ⋯, aN) 이 다음의 성질을 가지면 그 수열은 k-앞뒤수열 이라고 한다. (a1, a2, ⋯, ak) = (aN-k+1, aN-k+2, ⋯ , aN), 1 ≤ k < N 어떤 수열이 k-앞뒤수열일 때, k의 최댓값 k*를 그 수열의 앞뒤계 www.acmicpc.net 완탐하면 당연히 시간초과다. 그렇다면 어떻게 푸냐? 거꾸로 뒤집으면 된다. 수열을 거꾸로 입력받아서 그것에 대한 실패함수를 구하고, 최댓값과 최댓값이 나오는 횟수를 구해주면 된다. 근데 같은 방식인 것 같은데, 아래 코드와 정답 코드의 차이가 뭔 지 모르겠다. (더보기 클릭ㄱㄱ) 더보기 얘는 틀렸다고 한다.. why? ..
https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 이 문제는 실패함수만 구해주면 수월하게 풀리는 문제이다. bfs, dfs, 다익스트라를 공부할 때 코드의 틀을 외우듯이 실패함수도 외우고 계속 써먹다보면 언젠가 이해가 되리라 생각한다. 실패함수를 구한 뒤, 문제에서 주어진 광고판의 크기에서 실패함수를 빼주면 되는데, 광고판의 크기가 5라면 5번째 실패함수의 값을 빼주면 된다. (인덱스니까 -1해주기) 쉽게 말해서, 6칸짜리 광고판에 4글자 문구를 띄우면, 2칸이 ..
https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net kmp 알고리즘에 관한 문제이다. kmp 알고리즘이란, 문자열 패턴 매칭을 O(nm)이 아닌, O(n+m)에 해결할 수 있도록 해주는 문제이다. 이 알고리즘을 이해하기 위해서는, 접두사 접미사의 개념과 pi라고 칭한 이동경로 테이블을 왜 만드는지에 대한 이해가 필요하다. 이동경로 table은, 패턴의 부분 문자열(길이 1~원래 길이까지)마다 접두,접미사가 최대로 겹치는 길이를 저장해둔 tab..
