본문 바로가기

전체 글

(277)
백준 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번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다...
매내처 알고리즘(Manacher's algorithm) 우린 다음과 같은 문제를 해결한다고 해보자. 어떤 문자열의 부분 문자열 중 팰린드롬인 것의 개수를 구하기. 흔히들 배우는 방법으로는 $O(N^{2})$에 해결할 수 있는 동적 계획법이 있다. 하지만 N이 10000을 넘어간다면 메모리와 시간에 상당한 제약을 받게 될 것이다. 매내처 알고리즘은 선형 시간 복잡도 $O(N)$에 풀 수 있는 해법을 제시한다. 중요 아이디어는 다음과 같다. 과정은 뒤로 미뤄두고 우리는 탐색하고 있는 인덱스 i의 이전에 존재하면서 마지막 인덱스 j가 j > i인 팰린드롬을 구했다고 하자. 그리고 이 팰린드롬이 커버하고 있는 범위는 현재 인덱스 i를 포함하여 더 넓게 차지하고 있는 상황이다. 그러면 그 팰린드롬의 중심을 기준으로 양 옆에는 서로 같은 자식 팰린드롬이 있을 수 있다...
백준 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 ..