2021-08-01 Problem Solving

한 동안 정신 없는 일정 때문에 알고리즘 문제 해결을 별로 하지 못했으나, 최근에 여유가 생겨 SCPC 대비도 해볼 겸 다시 잡기 시작했다. 이번에 해결한 문제들을 정리해본다. 어찌 뒤로 갈수록 풀이를 대충 적은 것 같다...

21586. Another Substring Query Problem

쿼리가 하나만 주어진다면 어떨까? 문자열 $S$에 특정한 패턴 $P$가 $k$ 번째로 등장하는 지점을 찾는 문제가 된다. 이는 라빈 핑거프린트를 이용하여 문자열을 해싱해놓은 후, $|P|$ 길이의 부분 문자열을 살펴보며 쉽게 해결할 수 있다. 이 경우, 전체 과정이 약 $O(|S| + |P|)$ 정도의 시간에 이루어진다.

그런데, 이 과정을 모든 쿼리에 대해 반복하게 된다면, $O(Q(|S| + |P|))$​ 정도의 시간이 걸려 시간 초과를 받게 된다. 고로, 개선이 필요하다. 어떤 계산이 중복되어 일어나는지 살펴보면, 쿼리로 들어온 두 개 이상의 패턴이 동일한 길이를 갖는 경우에도 길이 $|P|$의 부분문자열을 살펴보는 과정 이 중복되어 이루어진다.

따라서, 쿼리를 오프라인으로 처리하며, 길이가 같은 패턴끼리 묶어 처리해주게 되면, 보다 효율적으로 문제를 해결할 수 있다. 시간 복잡도는 약 $O(|S| + Q + \sum |P|)$ 정도일 것이다. 다만, 한 가지 유의해야 할 점은, 구현 시에 해시 충돌이 발생하지 않을 정도로 다양한 경우의 수를 커버하는지 확인해줘야 한다.

18448. Best Subsequence

자명한 관찰 몇 개가 곧 풀이가 되는 문제였다. 생각하는 것은 쉬웠는데, 코드 짜는 것은 다소 귀찮았다...고 생각했으나 막상 짜보니 짤 만 했다. 오랜만에 세그먼트 트리 짜니깐 꽤 힘들었다.

어쨌든, 다음과 같이 자명한 관찰을 할 수 있다.

1. 전체 배열에서 최솟값은 반드시 우리가 선택하는 부분 수열에 포함된다.
2. 최소 원소가 맨 앞으로 오도록 배열을 시프트(shiftpsh 아님ㅎ)해도 문제가 없다.

위 관찰을 배경으로 하여, 최소 원소가 맨 앞으로 오도록 배열을 잘 돌리자. 그 후, 이분 탐색을 적용하여 결정 문제를 해결하는 것을 시도해보자. 결정 문제는 DP로 해결하는데, LIS를 DP로 해결할 때와 비슷하게

• $X[i]$: DP값이 $i$인 원소들 가운데 최솟값

로 정의되는 배열을 관리해주면서, 문제를 해결할 수 있다. 다만, $X$​의 단조성이 보장되지 않아서 그냥 이분 탐색을 할 수는 없고, 세그먼트 트리 비스무리한 것을 잘 이용하면 된다.

16953. A→B

나는 이 문제를 두 종류의 간선이 있는 그래프로 보고 그래프 탐색을 통해 해결했으나, 더 쉬운 해결법이 있어 적어둔다. $B$를 $A$로 바꾸는 역연산을 한다고 생각하고, 2를 나누거나, 맨 오른쪽의 1을 떼는 것을 반복하면 된다. 하나의 연산이 가능한 경우에 다른 하나의 연산은 불가능하므로, 쉽게 구현할 수 있다.

1949. 우수 마을

간단한 트리 DP 연습문제다. 각 노드마다 해당 노드를 우수 마을로 선정하는 경우와 그렇지 않은 경우에 대해 주민 수의 총 합을 저장해두며 DFS를 수행하면 된다.

22359. 흔한 타일 색칠 문제

내가 선제에 관여한 대회인 UCPC 2021의 예선 문제다.

분할-정복 기법을 이용하여 L-트로미노로 한 칸 빠진 $2^k \times 2^k$ 체스 보드를 채우는 것은 널리 알려져 있다. (만약 모른다면, 수학적 귀납법으로 이 문제를 해결하는 것을 시도해보라. 꽤나 재미있다.)

분할-정복 기법을 이용하여 L-트로미노로 전체 체스 보드를 채우는 과정에서 가운데에 놓는 블록은 2번 색으로, 기저 사례에 해당하여 블록을 놓는 경우에는 사분면 번호에 따라 적당히 색상을 배정해주는 방식으로 구현하면 문제를 잘 해결해줄 수 있다.

22356. 종이, 펜, 삼각형

이 문제는,

1. degenerate된 삼각형을 포함하여 "큰 삼각형" 안에 포함되는 삼각형의 개수를 세어주고,
2. 그 중 degenerate 된 것의 개수를 빼주면

해결할 수 있다.

1번 과정의 경우, 직선들의 절편 값을 기준으로 prefix sum 등을 관리해주면 해결할 수 있다.

2번 과정의 경우, 세 다항식을 곱했을 때, 특정한 차수를 가지는 항의 계수를 구하는 문제로 reduce 가능하다. 그리고 이는 고속 푸리에 변환을 이용하면 쉽게 해결해줄 수 있다.

3408. Non-boring sequences

배열의 각 원소마다 같은 값을 가지는 직전 원소의 위치와 직후 원소의 위치를 저장해두자. 부분 배열 $A[l, r]$ 이 non-boring인지 판단한다고 해보자.

만약, $A[l, r]$에 단 한 번만 등장하는 수 $x$가 없다면, 이 수열은 non-boring이다.

이제, 그러한 수 $x$가 있다고 가정하자. 그러면, $x$의 위치 $i$를 기준으로, $A[l, i-1]$ 과 $A[i+1, r]$에 대해 재귀적으로 판단해주면 된다.

여기에서, $x$라는 수를 어떻게 잡아주느냐에 따라 재귀 호출의 깊이가 달라질 것이다. 이는 $x$를 찾을 때 단순히 왼쪽에서 오른쪽으로 배열을 훑는 것이 아니라, $x$로 선택되는 원소들이 한쪽에 치우치지 않게 적당히 다른 방법을 사용하면 된다.