전체 글
-
2024 SCPC 2차 예선 후기 및 풀이대회 2024. 7. 27. 22:05
기분 좋게 12시쯤 일어나서 디스코드를 보니 9시에 SCPC가 시작해 있었다.1. 연속 10과 1로 이루어진 문자열이 주어진다. $S$의 비용을 지불하고 0을 1로, $E$의 비용을 지불하고 1을 0으로 바꿀 수 있을 때, 연속된 1이 한 묶음 이내가 되게 하는 최소 비용을 구하는 문제이다. 각 인덱스에 대해, 이 인덱스 이전을 00...0011...11로 만들 수 있는 최소 비용과, 이 인덱스 뒤를 11...1100...11로 만들 수 있는 최소 비용을 DP로 구한 다음, 더해서 최솟값을 찾는다. 이후 전부를 0으로 만드는 비용과 비교하여 출력하면 된다. 더보기#include#includeusing namespace std;typedef long long ll;int t, n, s, e;int arr[..
-
백준 3408 - Non-boring sequences문제 2024. 7. 21. 03:25
https://www.acmicpc.net/problem/3408길이 $N(\leq 200000)$의 수열이 주어졌을 때, $N$의 모든 substring이 유일한 원소를 가지면 non-boring, 아니면 boring을 출력하는 문제다. 처음에 시도한 접근법은 아래와 같다.1. 수열 전체에 유일한 원소가 없다면 그 수열은 boring이다.2. 그렇지 않다면, 해당 원소를 포함한 모든 구간은 유일한 원소를 가진다.3. 따라서 해당 원소를 기준으로 수열이 두 부분으로 나뉘어지게 되고, 각각이 non-boring이면 전체 수열도 non-boring이다.4. 이를 재귀적으로 생각한다. 그러나 위 접근법을 이용한 풀이를 내려면 수열의 임의의 구간에서 유일한 원소가 존재하는지 판별해야 하는데, 이를 빠르게 할 수..
-
KMP 알고리즘자료 2024. 7. 15. 12:17
Q) 길이가 $N$ 이하인 두 문자열 $A$와 $B$가 있다. 이때 $A$가 $B$를 substring으로 가지는지 판별하여라.나이브를 생각해보자. $A$와 $B$의 길이를 각각 $a$, $b$라고 할 때 $A$의 모든 점에서 시작해 길이가 $b$인 substring을 뽑고, 그것이 $B$와 같은지 확인하면 되므로 나이브의 시간복잡도는 $O(N^{2})$이 된다. KMP 알고리즘은 이 문제를 선형에 푸는 데 사용된다. 직관적인 최적화를 생각해보자. 눈으로 두 문자열을 비교한다고 생각할 때, 우리는 위의 나이브 알고리즘처럼 하나하나 비교하지 않는다. 대충 표현하자면 좀 많이 겹치는 것 같은 부분을 집중해서 비교한다고도 할 수 있다. 이를 알고리즘적으로 서술하는 것이 가능할까?KMP 알고리즘의 작동 방식을 ..