Logo

Counting Bits

LeetCode의 338번째 문제인 Counting Bits를 함께 풀어보도록 하겠습니다.

문제

정수 n이 주어졌을 때, 길이가 n + 1인 배열 ans를 반환하시오. ans[i]i에 대한 이진수로 표현했을 때, 1의 개수를 담고 있어야 합니다.

예제

입력: n = 2
출력: [0,1,1]
입력: n = 5
출력: [0,1,1,2,1,2]

풀이 1

이 문제를 푸는 가장 단순한 방법은 0부터 n까지의 정수를 이진수로 바꾼 후에 그 안에 들어 있는 1의 개수를 세는 것입니다.

십진수를 이진수로 바꾸려면 0이 될 때까지 2로 계속해서 나눠봐야 하죠? 그리고 나머지가 1인 경우만 세면 될 것입니다.

그럼 이 알고리즘을 파이썬으로 구현해볼까요?

class Solution:
    def countBits(self, n: int) -> List[int]:
        def count(num):
            cnt = 0
            while num:
                cnt += num % 2
                num //= 2
            return cnt

        return [count(num) for num in range(n + 1)]

이 풀이의 시간 복잡도는 O(n * log n)이 되는데요. 1의 개수를 세어주는 내부 함수의 복잡도가 O(log n)인데, 이 작업을 n + 1번 수행해야하기 때문입니다.

공간 복잡도는 결과 배열을 제외하면 고정된 개수의 변수만 사용하므로 O(1)이 되겠습니다.

풀이 2

이전 풀이를 보면 2로 나누고 나머지를 구하는 작업을 0부터 n까지 모든 숫자를 상대로 하고 있기 때문에 상당히 비효율적입니다. 어떻게 하면 더 작은 숫자를 상대로 구한 이진수 내의 1의 개수를 더 큰 숫자를 상대로 구할 때 활용할 수 있을까요?

우리 한번 0부터 15까지의 이진수를 구해서 표로 나타내보겠습니다.

십진수이진수패턴
000000
100011
200101 + 0
300111 + 1
401001 + 00
501011 + 01
601101 + 10
701111 + 11
810001 + 000
910011 + 001
1010101 + 010
1110111 + 011
1211001 + 100
1311011 + 101
1411101 + 110
1511111 + 111

위 표를 자세히 살펴 보시면 다음과 같이 반복되는 패턴을 찾으실 수 있으실 거에요. 숫자가 2배가 될 때 마다 이진수로 나타내었을 때 맨 앞에 새로운 1이 붙게 되기 때문이죠.

  • 1의 이진수 내의 1의 개수 = 1 + 0의 이진수 내의 1의 개수
  • 2부터 3 사이의 이진수 내의 1의 개수 = 1 + 0부터 1 사이의 이진수 내의 1의 개수
  • 4부터 7 사이의 이진수 내의 1의 개수 = 1 + 0부터 3 사이의 이진수 내의 1의 개수
  • 8부터 15 사이의 이진수 내의 1의 개수 = 1 + 0부터 7 사이의 이진수 내의 1의 개수

이 패턴을 수식으로 나타내보면 dp[num] = 1 + arr[num - MSB]게 될텐데요. 여기서 MSB(Most Significant Bit), 즉 최상위 비트는 1, 2, 4, 8, 16, ... 식으로 2배씩 커지게 되는데, 숫자가 커질수록 MSB가 천천히 커지는 것을 볼 수 있습니다. 정확히 얘기하면 숫자가 기존 MSB의 정확히 2배가 될 때마다 MSB2 배로 늘어나게 됩니다.

이진수십진수최상위 비트1의 개수
000
1111 + dp[1 - 1] = 1
10221 + dp[2 - 2] = 1
11321 + dp[3 - 2] = 2
100441 + dp[4 - 4] = 1
101541 + dp[5 - 4] = 2
110641 + dp[6 - 4] = 2
111741 + dp[7 - 4] = 3
1000881 + dp[8 - 8] = 1
1001981 + dp[9 - 8] = 2
10101081 + dp[10 - 8] = 2
10111181 + dp[11 - 8] = 3
11001281 + dp[12 - 8] = 2
11011381 + dp[13 - 8] = 3
11101481 + dp[14 - 8] = 3
11111581 + dp[15 - 8] = 4

결국은 동적 계획법 (Dynamic Programming)으로 해결할 수 있다 문제라는 것을 알 수 있게 되었네요!

지금까지 설명드린 알고리즘을 파이썬으로 구현해보겠습니다.

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        msb = 1
        for num in range(1, n + 1):
            if msb << 1 == num:
                msb = num
            dp[num] = 1 + dp[num - msb]
        return dp

이 풀이는 단순히 O(1)의 시간이 걸리는 로직을 1부터 n까지 한 번 루프를 돌고 있기 때문에 시간 복잡도가 O(n)으로 향상이 됩니다.

풀이 3

이번에는 MSB(Most Significant Bit) 대신에 LSB(Most Significant Bit), 즉 최하위 비트를 활용해보면 어떨까요?

최하위 비트는 숫자를 2로 나눈 나머지나, 비트 연산 & 1을 해주면 구할 수 있는데요. 숫자가 1씩 커짐에 따라 01이 계속해서 반복될 것입니다.

그럼 우리는 최하위 비트를 제외한 이진수의 나머지 부분에서 1의 개수만 세면 될텐데요. 최하위 비트를 제외하려면 숫자를 2로 나눈 몫이나, 비트 연산 >> 1을 해주면 구할 수 있습니다. 그러면 현재 숫자보다 적은 숫자가 나오므로 동적 계획법을 사용할 수 있게 됩니다.

십진수이진수최하위 비트 제외최하위 비트1의 개수
0000
111dp[0] + 1 = 1
21010dp[1] + 0 = 1
31111dp[1] + 1 = 2
4100100dp[2] + 0 = 1
5101101dp[2] + 1 = 2
6110110dp[3] + 0 = 2
7111111dp[3] + 1 = 3
810001000dp[4] + 0 = 1
910011001dp[4] + 1 = 2
1010101010dp[5] + 0 = 2
1110111011dp[5] + 1 = 3
1211001100dp[6] + 0 = 2
1311011101dp[6] + 1 = 3
1411101110dp[7] + 0 = 3
1511111111dp[7] + 1 = 4

나누기를 사용해서 알고리즘을 구현해보겠습니다.

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        for num in range(1, n + 1):
            dp[num] = dp[num // 2] + (num % 2)
        return dp

비트 연산을 사용해서 구현할 수도 있습니다.

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        for num in range(1, n + 1):
            dp[num] = dp[num >> 1] + (num & 1)
        return dp

이전 풀이보다 코드가 살짝 더 간결해지기는 했지만, 시간 복잡도와 공간 복잡도는 모두 여전히 O(n)이므로 빅오 계산법 기준으로는 의미있는 차이가 없습니다.

마치면서

이 문제가 너무 어려우셨다면 비슷하지만 좀 더 쉬운 문제인 Number of 1 Bits도 풀어보시라고 추천드립니다.