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/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 당연한 말이지만, 문제에 있는 코드로 풀면 시간초과로 틀린다. STL에 있는 sort를 활용하는데, 문제의 답은 어떻게 구하냐? pair를 이용하여 처음 입력받을 때, 숫자와 인덱스를 같이 저장해주면 된다! 버블 소트는 한번 정렬할 때 마다 제일 큰 수가 맨 뒤로 이동한다. 그렇게 되면 다른 수들은 자연스레 한칸 앞으로 움직이게 되고 버블 소트가 진행되고 난 후 배열의 인덱..
https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질 시리즈의 최종판이다. 이 문제는 다른 문제들과 달리, 동생의 위치에 포커싱을 맞춰야한다. (1초에는 1만큼 움직이고, 2초에는 2만큼 움직인다) (즉, 움직인 거리로 시간을 대체할 수 있다!) 만약 수빈이가 14초에 x라는 지점을 방문했다고 하자. 그런데 동생이 20초에 그 x지점을 방문했다. 그럼 수빈이와 동생은 20초만에 만날 수 있는 것이다. 라..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질1에 이은 문제이다. 숨바꼭질1은 최단경로를 찾아 루트부터 해당 노드까지의 거리(= 가장 빠른 시간)를 출력하고 바로 종료했다면, 이 문제는 큐가 빌 때 까지 모든 경우를 다 탐색해주면 된다. 물론, 가장 빠른 시간이 찾아지면 그보다 시간이 오래 걸리는 경로는 필요없으므로 트리가 한단계 더 깊어지면 멈춰준다. 이것은 약간의 트릭이다. 멈추지않고 찾아도 ..
