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

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

[1번 문제] 약수의 개수와 덧셈

출제 의도

• 약수의 개수를 구하는 방법을 구현할 수 있는지

해설

어떤 자연수 $x$에 대하여 $x$의 약수의 개수를 구하는 방법은 다음과 같습니다.

$i = 1, 2, \ldots x$에 대해서, $x$를 $i$로 나눈 나머지가 0인 $i$의 개수를 찾으면 됩니다.

이 행동을 $left, left+1, \ldots, right$에 대해 반복하면 됩니다. 시간 복잡도는 $O((right - left) \text{ } right)$입니다.

더 빠른 방법 해설

위에 서술된 완전탐색보다 더 빠르게 풀 수 있는 방법이 있습니다!

어떤 수의 약수의 개수가 홀수라는 것은, 해당 수가 어떤 수의 제곱수라는 것을 의미합니다.

따라서, $left$ 이상 $right$ 이하인 제곱수들을 찾으면 됩니다. 이것은 이진 탐색 또는 sqrt 함수로 빠르게 해결할 수 있습니다. 또한,

$$1 + 2 + \ldots + x = \frac{x(x+1)}{2}$$

$$1^2 + 2^2 + \ldots + x^2 = \frac{x(x+1)(2x+1)}{6}$$

을 이용하면 굳이 각 수들을 모두 더해주지 않아도 상수 시간 안에 합을 구하는 것이 가능합니다!

따라서, 시간 복잡도는 $O(1)$ 또는 $O(\log right)$입니다.

 

[2번 문제] 2개 이하로 다른 비트

출제 의도

• 비트 연산을 적절히 응용할 수 있는지

해설

$f(x)$는 다음과 같이 재해석될 수 있습니다.

$x$의 비트 형태	$f(x)$
......0	$x + 1 - 0$
.....01	$x + 2 - 1$
....011	$x + 4 - 2$
...0111	$x + 8 - 4$
..01111	$x + 16 - 8$
...	...

왜 이럴까요?

먼저, $x$에 어떤 수를 더하는 행위는, 다르게 해석하면 $x$의 특정 비트 몇 개를 골라 반전시키는 행위로 해석할 수 있습니다. 예를 들어, $10 + 3$은 $10$의 첫 3개의 비트를 반전시키는 것으로 해석할 수 있습니다.

여기서, 우리는 $x$의 비트를 딱 하나 또는 두 개만 바꾸어야 합니다. 그러면서 동시에 $x$의 값을 이전보다 더 크게 키워야 합니다. 여기서 얻을 수 있는 관찰은 다음과 같습니다.

• 만약 $x$의 비트를 하나만 바꿀 경우, $x$는 커져야 하기 때문에 $x$의 어떤 0을 1로 바꿔야 하는데, 그렇다면 $x$가 가진 0 중에서 가장 낮은 위치에 있는 0을 1로 바꾸는 것이 이상적입니다. $x$가 짝수인 경우가 바로 이 경우입니다.
• 만약 $x$의 비트를 2개 바꿀 경우, 일단 하나의 0은 1로 바꿔야 하는데, 다른 하나는 그보다 좀 더 낮으면서 제일 높은 자리의 1을 0으로 바꾸는 것이 더 이상적입니다. 왜냐하면, 비트는 윗자리로 갈수록 그 비트가 의미하는 값이 항상 커지기 때문입니다. $x$가 홀수인 경우가 바로 이 경우입니다.

$x$가 가진 제일 낮은 위치의 0을 구하는 데에는 $O(\log x)$이 소요되므로, 시간 복잡도는 $O(n \log (\max numbers))$입니다. ($n$은 numbers의 길이)

 

[3번 문제] 110 옮기기

출제의도

• 그리디(Greedy) 알고리즘을 설계할 수 있는지

해설

이 문제를 푸는 로직은 다음과 같습니다.

1. $s$에서 뽑을 수 있는 "110"을 그리디하게 뽑을 수 있을 때까지 계속 뽑아낸다. 이때, 스택을 사용하면 선형 시간 복잡도 내에 모든 "110"들을 뽑아낼 수 있습니다.
2. 추출한 "110"들을 1번 과정에 의해 변형된 $s$에서 나타나는 최초의 "111" 바로 앞에 삽입한다. ("111"이 $s$에서 나타나지 않으면 맨 뒤에 삽입)

예를 들어, s = "10111111100" 이라면, 1번 과정에서 "110"을 2개 추출하게 되고, s = "10111" 이 됩니다. 그리고 3개의 "110"을 최초로 나타나는 "111" 앞에 삽입하여 s = "10110110111" 이 됩니다.

왜 이렇게 하는 것이 최선일까요?

1. "110"은 어떤 길이의 접두사(Prefix)와 접미사(Suffix)도 서로 겹치지 않습니다. 따라서, "110"을 그리디하게 추출하더라도 어떤 "110"이 다른 "110"과 영역을 공유하는 일이 없기 때문에 괜찮습니다.
2. 임의의 3글자짜리 문자열("000", "001", ..., "111") 중에서, "110"은 "111" 다음으로 사전 순으로 뒤에 가는 문자열입니다. 따라서, "110"을 최초의 "111" 바로 앞에 배치하지 않는다면, $s$를 사전 순으로 가장 앞에 가는 문자열로 만들 수 없을 것입니다.

$n$을 $s$의 모든 문자열의 길이의 합이라고 할 때, 시간 복잡도는 $O(n)$입니다.

 

[4번 문제] 중력 작용

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

출제의도

• HLD (Heavy Light Decomposition) 알고리즘을 활용할 수 있는지
• 세그먼트 트리 또는 Treap 자료구조를 활용할 수 있는지

해설

먼저, HLD를 이용하여 트리를 일련의 구간(Segments)들로 나눕니다. 그다음, 각 구간을 Implicit Treap (이하 Treap)을 통해 관리하면 다음의 모든 것들을 $O(\log N)$ 시간 안에 관리할 수 있습니다.

• 구간의 특정 지점에 새로운 노드를 삽입하기
• 특정 지점의 노드를 삭제하기
• 임의의 연속된 부분 구간(Arbitrary Interval in Segment)의 합, 최댓값, 최솟값 등등을 구하기
• 임의의 연속된 부분 구간의 모든 노드에 특정 숫자를 더하거나, 특정 값으로 마킹하기 등등
• 임의의 연속된 부분 구간을 앞뒤로 뒤집기

구간에서의 중력 작용은, 기본적으로 어떤 연속된 부분 구간을 정해서, 그 부분 구간의 끝에 노드 하나를 삭제하고 새로운 노드를 삽입하는 것과 같습니다.

따라서 각 구간마다 하나의 세그먼트 트리와 하나의 Treap (총 2개의 자료구조)을 관리하면 됩니다. 다음 그림은 어떤 트리의 heavy 구간을 세그먼트 트리와 Treap으로 관리하는 모습을 나타낸 것입니다.

세그먼트 트리: 해당 노드에 연결된 다른 light 구간들의 노드의 값의 합

• 어떤 노드로부터 시작되는 다른 구간이 존재한다면, 해당 구간의 최상위 노드를 루트 노드로 갖는 서브 트리(Subtree)의 모든 노드의 값의 합이 반영되는 트리 상의 위치는 항상 동일하므로, 이 값은 Treap 같은 어려운 자료구조를 사용해서 관리하지 않아도 됩니다.
• 어떤 특정 구간의 노드의 값의 합이 바뀌었다면, 해당 구간의 합을 업데이트하고, 이것을 다시 상위 구간으로 보내고, 같은 과정을 루트 노드가 속한 heavy 구간에 도달할 때까지 반복하면 됩니다.

Treap: 해당 구간에 있는 노드의 값

• Treap에서는 직접적으로 해당 구간의 노드들의 값을 모니터링합니다. 어떤 특정 구간의 노드에 중력 작용이 일어난다면, 해당 노드를 삭제하고, 구간의 한쪽 끝에 새로운 값을 가진 노드를 만들어 넣어주면 됩니다.

이제 특정 노드를 루트 노드로 하는 서브 트리의 값을 구하라는 쿼리가 날아오면, 해당 노드가 속한 구간의 세그먼트 트리를 통해 주변 light 구간들의 노드의 값의 합을 끌어모으고, 거기에 해당 Treap의 부분 구간의 노드의 값의 합을 더해주면 됩니다.

시간 복잡도는 $O((n+q) \log^2 n)$ 입니다.

 

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

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