본문 바로가기

백준

(206)
백준 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을 만족해야 한다.(|은 정수론에서 배수관계..
백준 14517 - 팰린드롬 개수 구하기 (Large) https://www.acmicpc.net/problem/14517 풀이 다음 테이블을 세운다. dp(i, j) := i번째 문자부터 j번째 문자까지 해서 부분 수열을 구성했을 때 나올 수 있는 팰린드롬의 갯수 그러면 dp(i, i) = 1, dp(i, i + 1) = 2로 초기화를 할 수 있다. 이 때 입력으로 주어진 문자열 s에 대해 s[i] = s[i + 1]이면 대칭인 팰린드롬이 존재하는 것이므로 dp(i, i + 1) = 3이 된다. 그리고 부분 수열이 가질 수 있는 범위 gap마다 반복문을 돌면서 다음을 더하거나 빼면 된다. 시작점이 i이고 끝점이 j일 때... dp(i + 1, j)에서 그대로 가져오는 경우 -> dp(i, j)에서 단순히 확장한 것으로 간주할 수 있다. dp(i, j - 1..
[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번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다...
백준 1522 - 문자열 교환 https://www.acmicpc.net/problem/1522 힌트 더보기 특정한 상태를 만들어 보는 방법을 생각해보자. 그리고 원형의 상태가 문제 풀이에 어떤 영향을 미치는지도 생각해보자. 풀이 더보기 우리는 aaaabbbb 꼴과 같은 상태를 만들어 볼 것이다. 그러면 왼편의 b는 오른편의 a와 바꿔야 할 것이다. 물론 원형이라는 조건 하에 abbbbaaa 같은 문자열도 성립됨을 상기하자. 다만 abbbbaaa를 만드는 것과 aaaabbbb는 구현상 모순이다. 우리는 이 모순을 극복하기 위해 원형이라는 점을 이용해 문자열을 쉬프트 할 것이다. 그러면 문제는 다음과 같이 바뀐다. "원본 문자열을 x번 쉬프트 한 상태에서 aaaabbbb... 꼴로 만드는 연산 횟수" 그러면 각 상태에서 투 포인터로 스..
[ICPC] 백준 10266 - 시계 사진들 https://www.acmicpc.net/problem/10266 스텝 1 - 수열 정렬 시계 바늘은 모두 똑같이 생겼다. 따라서 주어진 각들을 오름차순으로 정렬해도 시계의 위상은 유지된다. 그러니까 일단 정렬하자. 스텝 2 - 각도값 보정 두 수열에 대해 맨 처음의 값이 0이 되도록 모든 원소에 적절한 값을 빼준다. 그래도 위상은 유지된다. 스텝 3 - 둘 중 하나를 두 배 하고 스트링 매칭 예제 입력 2를 보면 정렬을 함에도 절대적인 각도가 차이가 있는데 이를 해소하기 위해 수열을 복제하는 테크닉을 쓰면 정상적인 스트링 매칭이 가능하다. 이제 스트링 매치를 해서 매칭이 되면 possible, 그렇지 않으면 impossible을 출력하면 된다. 전체 코드 - kmp로 매칭했다. 더보기 1 2 3 4 ..