본문 바로가기

백준

 (227)
백준 2016 국민대학교 교내 경시대회 풀이 https://www.acmicpc.net/category/detail/1541 2016 국민대학교 교내 경시대회 www.acmicpc.net 그렇다. 현재는 에디토리얼이 제공되고 있지 않으므로 후배로써 풀이를 복원하면 좋을 거 같아 글을 쓴다. PA 13410 거꾸로 구구단 시키는 대로 구구단을 수행하면서 뒤집은 수의 최댓값을 구하면 된다. CPP에서는 std::to_string으로 구구단 결과를 문자열로 바꾼 후 std::reverse로 뒤집고 다시 std::stoi로 전환하는 방법이 있다. 파이썬에서는 역시 str()로 문자열로 바꾼 후 슬라이싱 문법으로 뒤집은 다음 int()로 전환할 수 있다. std 함수의 경우 상수 시간이 크지만 문제에선 제한이 작으므로 문제없이 돌아간다. 전체 코드 - CP..
백준 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... 꼴로 만드는 연산 횟수" 그러면 각 상태에서 투 포인터로 스..

티스토리툴바