Python으로 0부터 n까지 모든 숫자의 세트 비트(Set Bit) 총합 구하기

문제 소개

숫자 num이 주어졌을 때, 0부터 num까지의 모든 정수 i에 대해 해당 숫자를 이진수로 나타냈을 때 포함되는 1의 개수(세트 비트 수)를 계산하고, 그 값들을 모두 더한 합계를 반환하는 프로그램을 Python으로 작성해 보겠습니다.

예를 들어 num이 5라면 대상 숫자는 [0, 1, 2, 3, 4, 5]입니다. 각 숫자의 이진수 표현과 세트 비트 수는 다음과 같습니다.

따라서 각 숫자별 1의 개수는 [0, 1, 1, 2, 1, 2]이며, 최종 결과는 이들의 합인 7이 됩니다.

해결 알고리즘

이 문제는 동적 계획법(DP)을 활용하면 각 숫자의 이진수를 일일이 변환하지 않고도 선형 시간 O(n)에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• i가 2의 거듭제곱(1, 2, 4, 8, ...)이라면 이진수 표현이 1, 10, 100처럼 1이 하나뿐이므로 세트 비트 수는 항상 1입니다.
• i가 2의 거듭제곱이 아니라면, 직전 2의 거듭제곱 지점에서 떨어진 거리(offset)에 해당하는 숫자의 세트 비트 수에 1을 더한 값과 같습니다.

구체적인 풀이 단계는 다음과 같습니다.

1. (num + 1)개의 0으로 초기화된 배열 res를 생성합니다.
2. offset을 0으로 초기화합니다.
3. i를 1부터 num까지 반복하며 다음을 수행합니다.
   • i & (i - 1)의 결과가 0이면(i가 2의 거듭제곱), res[i]를 1로 설정하고 offset을 0으로 초기화합니다.
   • 그렇지 않으면 offset을 1 증가시킨 후, res[i]를 1 + res[offset]으로 설정합니다.
4. 배열 res의 모든 요소의 합을 반환합니다.

참고로 i & (i - 1)은 비트 AND 연산으로, i가 2의 거듭제곱일 때만 0이 됩니다. 예를 들어 4(100)와 3(011)을 AND하면 000이 되므로, 이 조건 하나로 2의 거듭제곱 여부를 손쉽게 판별할 수 있습니다.

Python 구현 예제

class Solution:
    def countBits(self, num):
        result = [0] * (num+1)
        offset = 0
        for i in range(1, num+1):
            if i & i-1 == 0:
                result[i] = 1
                offset = 0
            else:
                offset += 1
                result[i] = 1 + result[offset]
        return sum(result)

ob1 = Solution()
print(ob1.countBits(5))

입력

5

출력

7

복잡도 분석

시간 복잡도는 O(n)으로, 0부터 n까지 각 숫자를 한 번씩만 처리하면 됩니다. 공간 복잡도 역시 결과를 저장하는 배열로 인해 O(n)입니다. 각 숫자를 이진수로 직접 변환하며 비트를 세는 단순한 방식(약 O(n log n))보다 훨씬 효율적이므로, 코딩 테스트나 대용량 입력 처리에 유리합니다.