[월간 코드 챌린지 시즌3] 10월 문제 해설

 

코딩이 재미있는 사람들을 위한 챌린지! 프로그래머스에서 2021년 9월 9일, 10월 7일 두 번에 걸쳐 월간 코드 챌린지 시즌3가 진행되었습니다. 2021년 10월 7일 19시 30분부터 22시 30분까지 진행된 시즌3 10월 문제의 간단한 해설을 공개합니다.

 

[1번 문제] 나머지가 1이 되는 수 찾기

출제 의도

• 반복문을 활용할 수 있는지

해설

2부터 n-1까지의 모든 수에 대해 n을 해당 수로 나눈 나머지가 1이 되는 지 확인하면 됩니다.

시간복잡도는 $O(n)$ 입니다.

더 빠른 방법 해설

정답을 $p$라고 할 때, $n = pk + 1$ 이므로, $n-1 = pk$ 입니다. 즉, $n-1$의 가장 작은 약수(1 제외)를 찾으면 됩니다.

1. $\sqrt{n}$ 까지의 모든 수를 직접 나눠보는 방식(시간복잡도 $O(\sqrt n)$)
2. Pollard Rho 알고리즘을 적용하는 방식

등의 다양한 방법으로 문제를 풀이할 수 있습니다.

 

[2번 문제] $n^2$ 배열 자르기

출제 의도

• 수학적인 변환을 고안할 수 있는지

해설

다음은 $n \times n$ 행렬을 문제에서 주어진 방법대로 채운 결과를 나타낸 것입니다.

	1열	2열	3열	4열	...	n열
1행	1	2	3	4	...	n
2행	2	2	3	4	...	n
3행	3	3	3	4	...	n
4행	4	4	4	4	...	n
...	...	...	...	...	...	n
n행	n	n	n	n	n	n

규칙이 보이시나요? 1행 1열로부터 꺽쇠 모양의 웨이브가 펼쳐져 있는 것을 알 수 있습니다. 이걸 수학적으로 풀어서 쓰면, $i$행 $j$열에 있는 숫자는 $\max{(i, j)} + 1$ 입니다.

인덱스 $t$는 $\frac{t}{n}$행 $t \text{%} n$열을 가리키므로, 우리는 각 인덱스에 대해 해당 인덱스가 담고 있는 값을 바로 유도해낼 수 있습니다.

따라서, 시간복잡도는 $O(r - l)$입니다.

 

[3번 문제] 공 이동 시뮬레이션

출제 의도

• 문제에 주어진 시뮬레이션을 다른 형태로 변환하여 최적화할 수 있는지

해설

모든 격자 칸에 공을 하나씩 두고, 이 공들을 각 쿼리에 따라 "동시에" 움직인다고 상상해봅시다.

다음 애니메이션은 문제의 첫 번째 예시에서 모든 격자 칸의 공들을 동시에 시뮬레이션하는 모습을 나타낸 것입니다.

이 새로운 시뮬레이션의 특징은 다음과 같습니다.

1. 공들이 쿼리를 진행한 후에 모여 있을 수 있는 영역은 연속한 직사각형입니다.
2. 가로축과 세로축의 이동을 독립적으로 생각할 수 있습니다. 즉, $n$행 1열에서 행 방향 시뮬레이션만 따로 돌린 결과($x$행에 있는 공의 개수)랑, 1행 $m$열에서 열 방향 시뮬레이션만 따로 돌린 결과($y$열에 있는 공의 개수)를 구해서 두 결과를 곱한 것이 답이 됩니다.
3. 더 나아가서, 각 축의 방향을 따로 생각할 때, 격자의 영역은 3가지로 나눌 수 있습니다.
   1. 공이 없는 영역
   2. 공이 있는 영역의 두 끝부분
   3. 공이 있는 영역의 중앙 부분(없을 수도 있음)
   4. 이 3가지 영역 중에서 특히 2번째 영역에 있는 공의 개수를 관리하면서 시뮬레이션을 돌리면 해당 방향에 대한 시뮬레이션 결과를 $O(q)$ 안에 뽑아낼 수 있습니다. ($q$는 쿼리의 개수)

행 방향 시뮬레이션과 열 방향 시뮬레이션을 독립적으로 돌리면 되므로, 시간 복잡도는 $O(q)$입니다. ($q$는 쿼리의 개수)

 

[4번 문제] 쿼리의 모음의 개수

이 문제는 어려운 알고리즘 문제를 푸는 분들에게 한번 도전해 볼 만한 문제를 제공하고자 하는 의도로 출제했으며, 일반적인 채용 시험에서는 활용되지 않는 높은 난이도의 문제입니다.

출제 의도

• 복잡한 다이나믹 프로그래밍을 풀어낼 수 있는지

해설

해설에 나온 방법 말고도 다른 방법으로도 풀이가 가능하다는 점을 미리 말씀드립니다.

먼저 쿼리를 다음과 같이 2가지로 분류합니다.

• 쓸모있는 쿼리: 최소 1개 이상의 인덱스를 desired value로 만들어주는 쿼리
• 쓸모없는 쿼리: 그 어떤 인덱스도 desired value로 만들 수 없는 쿼리

예를 들어, $a = [1, 4, 5]$라면, $query(0, 2, 1)$은 $a[0]$을 1로 만들어주기 때문에 쓸모있는 쿼리이고, 반면 $query(1, 2, 3)$은 그 어떤 인덱스의 값도 충족시켜주지 못하므로 쓸모없는 쿼리입니다.

이제부터 쓸모있는 쿼리 $q_0$개와 쓸모없는 쿼리 $q_1$개를 섞어서 경우의 수를 계산해낼 것입니다. ($q_0 + q_1 = q$)

먼저 쓸모없는 쿼리를 사용하는 경우의 수를 계산하는 과정은 다음과 같습니다.

• $aux[k][q]$는 $q$개의 쿼리를 사용해서 $k$개의 서로 다른 넘버링을 만들어내는 경우의 수를 의미합니다.
• INVERSE_MOD(x)는 modulo 998,244,353 상의 곱셈에 대한 $x$의 역원을 의미합니다.

aux = [[0, ...], ...]
aux[0][0] := 1
for k = 0, 1, ..., q-1:
    for i = k, k+1, ..., q-1:
        for j = 1, 2, ..., q-i:
            aux[k+1][i+j] += aux[k][i] / INVERSE_MOD(j!)

이제 쓸모있는 쿼리를 사용하는 경우의 수를 계산하는 과정은 다음과 같습니다.

기본적으로, $a$의 모든 distinct한 값 $x$에 대해서 $x$ 이상의 모든 값을 포함하는 모든 subarray를 정의하여 해당 subarray에 대한 temporary DP를 만들고, 이를 $dp$에 적용시키는 것을 목표로 합니다.

• $temp_dp[q][c]$는 $q$개의 쿼리를 사용해서 해당 interval의 첫 $c$개의 $x$들을 커버하는 경우의 수를 의미합니다.
• SORTED_DISTINCT_NUMBERS(a)는 $a$에 들어있는 모든 수들을 정렬한 배열을 나타낸 것입니다.
• UPPER_INTERVALS(a, x)는 $a$의 모든 subarray 중 $x$를 최소 하나 이상 포함하면서 해당 subarray의 모든 원소가 $x$ 이상인 모든 subarray들을 의미합니다.
• COUNT(v, x)는 $v$ 안에 들어있는 수 중 $x$의 개수를 의미합니다.

dp = [0, ...]
for x in SORTED_DISTINCT_NUMBERS(a):
    for interval in UPPER_INTERVALS(a, x):

        temp_dp = [[0, ...], ...]
        temp_dp[0][0] := 1
        prev = 0
        c = COUNT(interval, x)

        while interval.left <= interval.right:
            current := prev
            for k = interval.left, ..., interval.right:
                current += 1 if a[k] == x
                if current > prev:
                    for t = q-1, q-2, ..., 0:
                        for p = prev, prev+1, ..., c
                            for y = 1, 2, ..., q-t
                                temp_dp[t+y][max(p, current)] += temp_dp[t][p] * INVERSE_MOD(y!)
            prev += 1 if a[i] == x
            interval.left += 1

        new_dp = [[0, ...], ...]
        for i = q-1, ..., 0:
            for k = 1, ..., q-i:
                new_dp[i+k] += dp[i] * temp_dp[k][c]
        dp := new_dp

이제 쓸모없는 쿼리와 쓸모있는 쿼리를 합치는 일만 남았습니다. 다음과 같습니다.

• INFINITY는 $a$의 어떤 값보다도 더 큰 충분히 큰 값을 말합니다.
• COMBINATION(x, y)는 $\binom{x}{y}$을 의미합니다. (이항계수)

for i = 0, ..., n-1:
    m = INFINITY
    for j = i, i+1, ..., n-1:
        m := min(m, a[j])
        for p = q-1, ..., 0:
            for k = 1, 2, ..., q-p:
                for l = 1, 2, ..., min(k, m-1):
                    dp[p+k] += dp[p] * aux[l][k] * COMBINATION(m-1, l)

답은 dp[q] * q!이 됩니다. 시간복잡도는 $O(n^4 q^2 + n^2 q^2 \min(M, q) + M q)$ 입니다. ($n$은 $a$의 길이, $M$은 $a$의 원소의 최대값)

 

 

 

월간 코드 챌린지 시즌3 10월 문제 다시 풀기

월간 코드 챌린지 시즌3의 문제는 프로그래머스에서 다시 풀 수 있습니다. 여기를 클릭 후 '문제 모음 선택' 필터 조건에 월간 코드 챌린지 시즌3을 선택하세요. 그럼 시즌4에서 다시 뵙겠습니다!