ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [월간 코드 챌린지 시즌3] 10월 문제 해설
    프로그래머스 이벤트 2021. 10. 18. 17:46

     

    코딩이 재미있는 사람들을 위한 챌린지! 프로그래머스에서 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번 문제] 공 이동 시뮬레이션

    출제 의도

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

    해설

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

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

    ex1

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

    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에서 다시 뵙겠습니다!

    댓글 1

    • grepp 2021.10.18 17:59 신고

      블로그 관리자입니다. :) 문제 풀이 과정에 대해 댓글에서 자유롭게 이야기를 나눌 수 있습니다. 다만, 추가적인 궁금증에 대해 프로그래머스에서 공식 답변을 드리지는 않습니다.

Programmers