[월간 코드 챌린지 시즌2] 4월 문제 해설

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

 

[1번 문제] 음양 더하기

출제의도

• 주어진 문제를 푸는 로직을 구상하고 그 로직을 구현할 수 있는지

해설

먼저 정답을 0으로 설정한 후, absolutes 배열에 있는 모든 수들을 차례대로 보는데, 그 수에 해당하는 signs 값이 참이면 정답에 더하고, 거짓이면 정답에 빼면 됩니다.

$n$을 두 배열의 길이라고 할 때, 시간 복잡도는 $O(n)$ 입니다.

 

[2번 문제] 괄호 회전하기

출제의도

• 문자열과 스택을 적절하게 활용할 수 있는지

해설

먼저 문자열의 회전을 생각하지 않고 $s$가 올바른 괄호 문자열인지 아닌지를 판별하는 것부터 풀어봅시다. 이것은 스택으로 해결이 가능합니다.

문자열을 앞에서부터 훑어보면서 여는 괄호가 나오면 스택에 push 하고, 닫는 괄호가 나오면 스택의 top에 있는 원소가 닫는 괄호랑 같은 쌍인지 판별한 뒤 같은 쌍이면 스택을 pop 합니다. (같은 쌍이 아니라면 이 문자열은 올바르지 않은 문자열입니다.) 그렇게 문자열을 끝까지 훑어본 뒤 중간에 오류가 나지 않았고, 스택이 최종적으로 비어 있다면 비로소 이 문자열이 올바른 문자열이라는 것을 알 수 있습니다.

이제 문제를 다음과 같은 방식으로 풀 수 있습니다. (다른 로직으로도 이 문제를 풀 수 있습니다.)

1. 정답을 0으로 설정한다.
2. $s$가 올바른 문자열인지 판별하고, 만약 그렇다면 정답에 1을 더한다.
3. $s$를 1칸 회전한다.
4. $s$가 1바퀴 돌아올 때까지 2번, 3번 과정을 반복한다.
5. 정답을 return 한다.

$n$을 $s$의 길이라고 할 때, 한 번의 문자열 판별에 $O(n)$이 소모되고, 그런 판별을 $n$번 하므로, 시간 복잡도는 $O(n^2)$ 입니다.

 

[3번 문제] 모두 0으로 만들기

출제의도

• 트리를 루트부터가 아닌 리프 노드부터 거꾸로 탐색할 수 있는지
• 그리디(Greedy) 알고리즘을 설계할 수 있는지

해설

먼저, 주어진 트리의 모든 노드들의 가중치의 합이 0이 아니라면, 모든 점들의 가중치를 0으로 만드는 것은 불가능합니다. 왜냐하면 주어진 연산은 트리의 모든 노드들의 가중치의 합을 바꾸지 않기 때문입니다. (한쪽은 1 더하고, 한쪽은 1 빼므로 전체 가중치의 합은 동일합니다.)

그 외의 경우에는 항상 가능합니다. 그리디하게 리프 노드의 가중치를 0으로 만들어버리고 해당 리프노드를 트리에서 제거한 뒤, 노드가 하나밖에 남지 않을 때까지 계속해서 같은 과정을 반복하면 됩니다.

이 방법이 가능한 이유는 리프 노드는 어차피 언젠가는 해당 노드의 가중치만큼의 횟수의 연산을 적용시켜서 가중치를 0으로 만들어야 하고, 무엇보다 덧셈의 교환 법칙에 의해서 문제에 주어진 연산을 적용하는 순서가 별 의미가 없기 때문입니다. 따라서 리프 노드부터 해결해나가면 최소 연산 횟수를 확정적으로 찾을 수 있습니다.

$n$을 $a$의 길이라고 할 때, 시간 복잡도는 $O(n)$ 입니다.

 

[4번 문제] RPG와 쿼리

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

출제의도

• 주어진 문제를 여러 단계로 분할하여 풀이에 점진적으로 접근할 수 있는지
• 너비 우선 탐색(Breadth-First Search, 이하 BFS), 다이내믹 프로그래밍(Dynamic Programming, 이하 DP), Prefix Min을 적절하게 활용할 수 있는지

해설

먼저, $n z^2$ 개의 노드로 이루어진 그래프를 새로 만듭니다. 편의상 각 노드를 $(i, g)$라고 부르겠습니다. ($i$: 도시의 번호, $g$: 도시에 도착했을 당시 가진 돈 ($0 \le g \lt z^2$)) 왜 하필 $z^2$ 원까지 고려하는지는 나중에 설명드리겠습니다.

이제 쿼리의 모든 수가 $z^2$보다 작고, 2번 행동(도시에 머무르면서 z원을 얻는 행동)을 하지 않는 경우에 한한 문제를 풀어봅시다. 그렇다면 문제는 다음과 같이 바뀌게 됩니다. queries 배열에 들어있는 각 숫자 $q$에 대해서, $(0, 0)$에 출발해서 아무 $(i, q)$에 도달하는 가장 빠른 시간을 구해야 합니다.

이 문제는 BFS를 통해서 해결할 수 있습니다. 물론 3번 행동(순간 이동)의 엣지를 그래프 상에 그대로 표현하면 시간 복잡도가 $O(n^2 z^2)$이 되어서 시간 초과가 나고, $F(i, g)$는 $(0, 0)$부터 $(i, g)$까지 가는 데 필요한 최단시간이라고 할 때, $G(g) = min_{i \in [0, n)}(F(i, g))$ 을 저장하는 배열을 하나 만들어서 보조적으로 활용해야 합니다.

앞서 첫 문단에서 말씀드렸지만, 이쯤에서 의문이 하나 생깁니다. 그래프를 만들 때 왜 하필 $z^2$ 원까지만 고려해도 되는 것일까요? 비둘기집의 원리를 이용하여 이 사실을 증명할 수 있습니다.

어떤 최적화된 경로 $c_0 \rightarrow c_1 \rightarrow c_2 \rightarrow \cdots \rightarrow c_k \rightarrow c \rightarrow c \rightarrow \cdots \rightarrow c$ 가 있다고 해봅시다. ($0 = c_0 \neq c_1 \neq c_2 \neq \cdots \neq c_k = c$) 2번 행동은 언제 하든 상관없으므로 경로 상에서 맨 뒤로 미루었습니다. 만약 $k$가 $z$ 이상이라면, 비둘기집의 원리에 의해 어떤 두 인덱스 $i$, $j$가 존재하여 $c_i$에 도착한 시점에 가진 돈 $g_i$와 $c_j$에 도착한 시점에 가진 돈 $g_j$를 $z$로 나눈 나머지가 같습니다. 이것은 $c_i$에서 $c_j$까지 이동하면서 $z$의 배수만큼의 돈을 벌었다는 뜻이 되며, 이렇게 이동할 바에는 차라리 도시에 가만히 있으면서 계속해서 $z$원씩 벌었다가, 나중에 순간 이동하는 편이 시간 절약을 더 할 수 있습니다. 모든 도로의 가중치값이 z보다 작기 때문입니다. 따라서 1번 행동은 아무리 많아봐야 z번까지만 하면 되며, 이는 $(i, g)$ 점으로 이루어진 그래프 상에서 $g < z^2$ 인 점들만 고려해도 무방하다는 점을 시사합니다.

이제 원래 문제를 풀어봅시다. 숫자 $q$가 들어왔을 때 $F, G$를 이용해서 어떻게 풀 수 있을까요? $q$원을 얻기 위해서는 어떤 $t$에 대해서 $(q\%z + tz)$원을 1번, 3번 행동을 통해 얻은 다음, 나머지를 2번 행동을 통해 얻어야 할 것입니다. 여기서 소모하는 시간은 $G(q\%z + tz) + \frac{(q - q\%z - tz)}{z} = G(q\%z + tz) + \lfloor \frac{q}{z} \rfloor - t$ 이 되겠죠. 따라서 feasible 한 $t$에 대하여 $G(q\%z + tz) - t$의 최솟값을 구할 수 있다면, 문제를 풀 수 있게 됩니다.

그러기 위해서는 다음과 같은 배열을 미리 만들어두면 됩니다: $H(q) = [\ G(q\%z), G(q\%z + z) - 1, G(q\%z + 2z) - 2, G(q\%z + 3z) - 3, \ldots \ ]$. 이 배열의 특정 prefix(G에 들어가는 값이 q보다 작은 인덱스까지)의 최솟값을 고른다면, 그 값을 통하여 정답을 도출해낼 수 있습니다! 그리고 이것은 Prefix Min으로 해결할 수 있습니다. 정확한 수식은 $\frac{q}{z} + \text{PrefixMin}(H(q))[min(z-1, \frac{q}{z})]$입니다.

$e$를 roads의 길이, $q$를 queries의 길이라고 할 때, 시간 복잡도는 $O((n + e) z^2 + q)$입니다.

 

 

월간 코드 챌린지 시즌2 4월 문제 다시 풀기

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