https://www.acmicpc.net/problem/1498 1498번: 주기문 어떤 문자열 X를 n번 연달아 쓴 것을 (X)^n으로 나타내기로 하자. 예를 들어 (ab)^3는 ababab를 의미한다. 어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있다면, 그리고 n이 1이 아니라면 Y를 주기문 이라고 한다 www.acmicpc.net 실패함수의 응용의 응용 반복되는 가장 작은 문자열 == 문제에서 원하는 "주기문" 의 길이를 https://blog.koderpark.dev/263 백준 BOJ 1305 - 광고 @이화월백 이 골라준 태그 문제풀이 오늘의 태그는 KMP되시겠다 https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 ..

https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 등수의 차이가 $K$보다 작거나 같으면서 이름의 길이가 같은 친구들의 쌍 갯수를 세는 문제이다. 평범하게 생각하면 $O(N)$으로 훑어가면서 $O(2K)$에 등수의 차이가 작은 구간을 순회하게 되는데, 이 경우에는 $O(KN)$으로 TLE를 받아 제한시간 내에 문제를 해결할 수 없다. 투포인터를 활용한 스위핑으로 문제를 해결했다. 두개의 포인터 $l$ 과 $r$ 을 만드는데, ..

DP + BFS 문제. https://www.acmicpc.net/problem/16397 16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 www.acmicpc.net dp[k] 를 숫자 $K$를 만드는데 필요한 최소한의 버튼 누름 횟수 라고 하고, 숫자 $K$인 상태에서 두 버튼을 눌렀을때 변화하는 수를 각각 $A(K)$, $B(K)$ 이라고 하면 dp[A(K)] = dp[k] + 1 dp[B(K)] = dp[k] + 1 이 된다. 버튼 A, B를 누를 때 각각 숫자가 99,999..

https://www.acmicpc.net/problem/17212 17212번: 달나라 토끼를 위한 구매대금 지불 도우미 달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은 www.acmicpc.net DP 알고리즘 문제. dp[k]를 k원 계산을 할때 필요한 최소 동전의 개수로 정의하면 dp[k-a] 에서 a원어치 동전을 b개 지불하면 dp[k-a]+b = dp[k]가 되므로 dp[k] = min({dp[k-1], dp[k-2], dp[k-5], dp[k-7]})+1 이 된다. 해당 식을 그대로 적용해서 재귀문을 이용해 풀어도 되고 나는 바텀업 DP를 짰다. 입..

부분합 배열 만들어서 해결했다. 부분합 배열을 만들지 않는 O(T*N^3) 풀이로도 풀 수 있다고 한다. 내가 구현한 코드의 시간복잡도는 O(T*N^2) https://www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 부분합 배열을 미리 계산해놓고 답을 구하는데, 이때 sum[e] - sum[s] 를 통해 값을 구할 때 e와 s가 같아지는, 즉 아무것도 더하지 않아서 subarray의 길이가 0이 되는 경..

우선순위큐를 죽어라 바이럴하는 문제 우선순위 큐(특히 STL의 그것) 에 대해 알고있다면 쉽게 해결할 수 있는 문제였다. https://www.acmicpc.net/problem/14235 14235번: 크리스마스 선물 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 www.acmicpc.net 아이들이 요구할때마다 가장 가치가 큰 물건을 꺼내야 하기 때문에, 우선순위 큐를 통해서 우선순위(가치) 가 높은 숫자를 꺼내서 하나씩 출력해주면 된다. 굳이 우선순위 큐 아니더라도 중복 감안할수 있는 멀티셋 같은거 활용해도 되지 않나 싶기도 하고 아마 그냥 반복문으로도 해결을 할..