음이 아닌 정수 num이 주어졌을 때, 0부터 num까지의 모든 숫자 i에 대해 각 숫자를 이진수로 변환했을 때 포함된 1의 개수를 계산하고, 그 결과를 리스트 형태로 반환하는 문제입니다.
예를 들어 num이 5라면 대상 숫자는 [0, 1, 2, 3, 4, 5]이며, 각 숫자의 이진수 표현은 각각 0, 1, 10, 11, 100, 101입니다. 따라서 각 숫자에 포함된 1의 개수는 [0, 1, 1, 2, 1, 2]가 됩니다.
해결 전략
이 문제는 동적 계획법(DP)과 비트 연산을 함께 활용하면 선형 시간 O(n) 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 이미 계산해 둔 작은 값들의 결과를 재활용하는 것입니다.
구체적인 단계는 다음과 같습니다.
- result := num + 1 크기만큼 0으로 초기화된 배열을 생성합니다.
- offset := 0으로 초기화합니다.
- i를 1부터 num까지 반복하면서 다음을 수행합니다.
i & (i-1) == 0이라면 i는 2의 거듭제곱이므로 result[i] = 1로 설정하고 offset을 0으로 초기화합니다.- 그렇지 않다면 offset을 1 증가시킨 후, result[i] = 1 + result[offset]으로 계산합니다.
- 모든 반복이 끝나면 result 배열을 반환합니다.
여기서 i & (i-1) 연산은 i가 2의 거듭제곱일 때만 0이 된다는 성질을 이용한 것입니다. 2의 거듭제곱 지점마다 새로운 자릿수가 시작되므로 offset을 초기화하고, 그 이후의 숫자들은 직전 거듭제곱 지점의 결과에 1을 더한 값이 됩니다.
파이썬 구현 예제
아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
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 result
ob1 = Solution()
print(ob1.countBits(6))
실행 결과 확인
입력
6
출력
[0, 1, 1, 2, 1, 2, 2]
출력 결과를 살펴보면, 0부터 6까지 각 숫자의 이진수 표현인 0, 1, 10, 11, 100, 101, 110에 포함된 1의 개수가 순서대로 저장되어 있는 것을 확인할 수 있습니다. 이처럼 비트 연산과 동적 계획법을 결합하면 각 숫자를 매번 이진수로 변환하는 것보다 훨씬 빠르게 답을 구할 수 있습니다.