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

 

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

 

[1번 문제] 없는 숫자 더하기

출제의도

• 배열, set 등을 활용할 수 있는지

해설

길이가 10인 배열 또는 set 같은 자료구조를 활용하여 $numbers$에 들어있지 않은 숫자를 모두 찾을 수 있습니다.

시간복잡도는 $O(n)$ 입니다. ($n$은 배열의 길이)

 

[2번 문제] 빛의 경로 사이클

출제의도

• 4방향 이동/회전 구현을 할 수 있는지

해설

3차원 배열 $visited$를 다음과 같이 정의합니다.

• $visited[r][c][d]$: $r$행 $c$열에서 $d$방향으로 나간 적이 있는지 기록

이제 임의의 $(r, c, d)$ 트리플에 대해서, $(r, c, d)$를 아직 방문하지 않았다면 해당 좌표의 해당 방향을 방문하고, 그 좌표로부터 사이클을 따라 다시 원래 좌표의 원래 방향을 방문할 때까지 이동을 반복합니다. 이를 수도코드로 표현하면 다음과 같습니다.

for r0 = 0, 1, ..., n-1:
    for c0 = 0, 1, ..., n-1:
        for d0 = LEFT, RIGHT, UP, DOWN:
            if not visited[r0][c0][d0]:
                r, c, d := r0, c0, d0
                while visited[r][c][d] is false:
                    visited[r][c][d] := true
                    r, c := MOVE(r, c, d)
                    d := ROTATE(r, c, d)

• MOVE 함수는 $r$행 $c$열에서 $d$방향으로 이동했을 때 도착하는 위치를 함수로 표현한 것입니다.
• ROTATE 함수는 $r$행 $c$열에서 $d$방향인 상태에서 회전을 했을 때 새롭게 설정된 방향을 함수로 표현한 것입니다.

이와 같은 알고리즘을 사용하면 모든 $(r, c, d)$ 트리플을 단 1번씩만 방문하므로, 시간복잡도는 $O(n^2)$입니다. ($n$은 배열의 한 변의 길이)

 

[3번 문제] 금과 은 운반하기

출제 의도

• 이분탐색을 적절히 활용할 수 있는지

해설

먼저 이 문제를 결정문제로 환원해봅시다. 시간 $T$가 주어졌을 때, $T$라는 시간 안에 트럭을 최대한 활용시켜 금과 은을 각각 $a$, $b$만큼 운반할 수 있는지 판별하는 문제로 바꿔봅시다. 그렇다면 해당 결정 문제는 다음과 같이 풀 수 있습니다.

1. 제한 시간 안에 금을 최우선적으로 운반했을 때 운반할 수 있는 금의 양과 은의 양을 각각 $G_{max}, S_{min}$ 이라고 정의합니다.
2. 제한 시간 안에 은을 최우선적으로 운반했을 때 운반할 수 있는 금의 양과 은의 양을 각각 $G_{min}, S_{max}$ 이라고 정의합니다.
3. 그렇다면 $G_{max} + S_{min} = G_{min} + S_{max}$ 입니다.
4. 만약 $a \leq G_{max}$, $b \leq S_{max}$, 그리고 $a+b \leq G_{max} + S_{min} = G_{min} + S_{max}$ 라면, 주어진 시간 $T$ 안에 $a$만큼의 금과 $b$만큼의 은을 운반할 수 있습니다.

이 결정 문제는 어떤 $t$값이 존재하여 $T < t$ 일 때는 전부 불가능, $t \leq T$ 일 때는 전부 가능하므로, 이분탐색을 활용하여 적정한 $t$를 찾을 수 있습니다. 결정 문제를 한번 푸는 데 $O(n)$ ($n$은 도시의 개수)이 소모되고, 결정 문제를 $O(\log T_{max})$ ($T_{max} \leq 10^{15}$) 번 푸므로, 시간복잡도는 $O(n \log T_{max})$ 입니다.

여기서 의문이 들 수 있습니다. 왜 결정문제를 푸는 과정에서 4번이 성립할까요? 이는 벡터를 활용하여 증명을 할 수 있습니다.

1. $i$번 도시로부터 $T$라는 시간 안에 가져갈 수 있는 광물의 양을 $W_{max}[i]$ 라고 정의할 때, 시간 안에 가져갈 수 있는 금의 양과 은의 양은 기울기가 -1인 선분을 이루고 있습니다. ($gold + silver = W_{max}[i]$)
2. 이때 이 기울기가 -1인 선분은 두 개의 벡터의 weighted sum으로 표현할 수 있습니다. ($\overrightarrow{W[i]} = p \overrightarrow{(G_{max}[i], S_{min}[i])} + (1-p) \overrightarrow{(G_{min}[i], S_{max}[i])}$, $0 \leq p \leq 1$)
3. $\sum_{i} \overrightarrow{W[i]}$ 가 나타내는 도형 또한 기울기가 -1인 선분입니다. 왜냐하면 더해진 모든 선분의 기울기가 -1으로 동일하기 때문입니다. 이 선분은 $p \overrightarrow{(G_{max}, S_{min})} + (1-p) \overrightarrow{(G_{min}, S_{max})}$로 표현될 수 있습니다. ($0 \leq p \leq 1$)
4. $\sum_{i} \overrightarrow{W[i]} - \overrightarrow{(a, b)}$ 가 나타내는 선분이 1사분면(축 경계 포함)을 지나면 금 $a$ kg과 은 $b$ kg을 운반할 수 있는데, 이는 $a \leq G_{max}$, $b \leq S_{max}$, $a+b \leq G_{max} + S_{min} = G_{min} + S_{max}$와 동일합니다.

 

[4번 문제] 안티세포

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

출제 의도

• 다이나믹 프로그래밍(이하 DP)과 Prefix Sum을 적절히 활용할 수 있는지

해설

먼저 가장 중요한 관찰이 하나 있습니다. $b$의 모든 원소가 양수이기 때문에, 임의의 $c$ 배열을 문제의 과정대로 만드는 방법은 유일하거나, 혹은 불가능하다는 것입니다. 이제 이 관찰을 기반으로 다음과 같은 DP를 정의해봅시다.

• $DP[i][e]$: $b[0], b[1], \ldots, b[i]$만 고려했을 때, $b[i]$가 속한 세포의 모든 수의 합을 $b[i] \cdot 2^{e}$로 만들 수 있는 경우의 수($0 \leq i < n$, $0 \leq e \leq \log_{2} \max(b)$)

먼저 기저 케이스의 경우 다음과 같이 풀 수 있습니다.

1. $i = 0$일 경우, $DP[i][0] = 1$, $DP[i][e (> 0)] = 0$ 입니다.
2. $i > 0, e = 0$일 경우, $DP[i][0] = \sum_{e} DP[i-1][e]$ 입니다.

이제 일반적인 케이스에 대해서 풀 방법을 알아봅시다. $PS[i] = \sum_{j=0}^{i} b[j]$, $PS[-1] = b[-1] = 0$ 라고 정의합니다. (Prefix Sum)

$DP[i][e] > 0$이기 위해서는 다음 3가지 상황이 선제적으로 필요합니다.

• $DP[i][e-1] > 0$
• $PS[i] - PS[j_{half}] = b[i] \cdot 2^{e-1} = b[j_{half}] \cdot 2^{e'}$, $0 \leq e'$를 만족하는 $j_{half}, e'$가 존재하여 $DP[j_{half}][e'] > 0$을 만족
• $PS[j_{full}] = PS[i] - b[i] \cdot 2^{e}$인 $j_{full}$이 존재

이 3가지 상황을 만족한다면, $DP[i][e] = \sum_{d} DP[j_{full}][d]$ 입니다. (그렇지 않다면, $DP[i][e] = 0$ 입니다.) $j_{full} + 1$부터 $j_{half}$까지의 인덱스의 숫자들을 하나의 안티세포로 합치고, $j_{half}+1$부터 $i$까지의 인덱스의 숫자들을 하나의 안티세포로 합친 뒤, 두 안티세포를 합치면 되기 때문입니다. 이 과정은 앞서 말씀드린 관찰 때문에 오직 1가지 경우만 가능하고, 그렇다면 $DP[i][e]$에 영향을 미치는 유의미한 factor는 $0$부터 $j_{full}$까지의 인덱스가 됩니다.

시간복잡도는 $O(n \log \max b)$ 입니다. ($n$은 $b$의 길이)

 

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

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