본문 바로가기

백준/문자열

 (4)
백준 1498 - 주기문 https://www.acmicpc.net/problem/4354 사전 지식 이 문제를 KMP로 풀고 와야 한다. https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 풀이 문자열 제곱을 제대로 이해하고 왔다면 KMP 실패 함수에 다음 성질이 있음을 알 것이다. 길이 x의 문자열이 주기성을 만족하려면 n - x개의 접미사와 n - x개의 접두사가 같아야 한다. 또한 x|n을 만족해야 한다.(|은 정수론에서 배수관계..
[ICPC] 백준 14959 - Slot Machines https://www.acmicpc.net/problem/14959 사전 지식 이 문제를 제대로 푸려면 다음 두 문제를 먼저 풀고 올 필요가 있다. 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 https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다...
[ICPC] 백준 10266 - 시계 사진들 https://www.acmicpc.net/problem/10266 스텝 1 - 수열 정렬 시계 바늘은 모두 똑같이 생겼다. 따라서 주어진 각들을 오름차순으로 정렬해도 시계의 위상은 유지된다. 그러니까 일단 정렬하자. 스텝 2 - 각도값 보정 두 수열에 대해 맨 처음의 값이 0이 되도록 모든 원소에 적절한 값을 빼준다. 그래도 위상은 유지된다. 스텝 3 - 둘 중 하나를 두 배 하고 스트링 매칭 예제 입력 2를 보면 정렬을 함에도 절대적인 각도가 차이가 있는데 이를 해소하기 위해 수열을 복제하는 테크닉을 쓰면 정상적인 스트링 매칭이 가능하다. 이제 스트링 매치를 해서 매칭이 되면 possible, 그렇지 않으면 impossible을 출력하면 된다. 전체 코드 - kmp로 매칭했다. 더보기 1 2 3 4 ..
[ICPC] 백준 9081 - 단어 맞추기 https://www.acmicpc.net/problem/9081 주의! 이 문제에는 낚시가 있다! 출력란에 써진 글을 보자. 각 테스트 케이스에 대해서 주어진 단어 바로 다음에 나타나는 단어를 한 줄에 하나씩 출력하시오. 만일 주어진 단어가 마지막 단어이라면 그냥 주어진 단어를 출력한다. 여기서 말하는 마지막 단어는 입력의 마지막이 아니라 사전순으로 마지막인 단어를 의미한다! C++의 경우 next_permutation()을 할 때 현재 순열이 사전순으로 마지막이라면 false를 반환한다. next_permutation의 결과가 false이면 prev_permutation으로 다시 되돌린 후 출력하면 된다. 전체 코드 더보기 #pragma GCC target("avx,avx2,fma") #pragma ..

티스토리툴바