Counting Bits

Q: Counting Bits의 시간 복잡도는 무엇인가요?

가장 좋은 해결책은 O(n) 시간에 실행됩니다. n+1 개의 항목은 각각 이전 항목 하나에 덧셈 한 번을 적용해 얻습니다. 모든 숫자의 비트를 하나씩 세면 O(n log n) 시간이 걸립니다. n 이하의 숫자는 이진수로 약 log2 n자리이기 때문입니다. 두 방법 모두 출력 배열 외에는 O(1) 메모리를 사용합니다.

Q: bits[i] = bits[i >> 1] + (i & 1)는 왜 작동하나요?

i >> 1 은 마지막 이진 숫자를 제거한 i 이고, i & 1 은 제거된 숫자입니다. i 의 1의 개수는 더 짧은 수의 1의 개수에 마지막 숫자를 더한 값입니다. 1011 인 11의 경우, 더 짧은 수는 5( 101 , 1이 두 개)이고 마지막 숫자는 1이므로 11에는 1이 세 개 있습니다.

Q: Counting Bits를 위한 다른 O(n) 점화식이 있나요?

네. i & (i-1) 은 i 의 가장 낮은 1비트를 지우므로, 1 이상의 모든 i 에 대해 bits[i] = bits[i & (i-1)] + 1 입니다. 12( 1100 )의 경우 12 & 11 은 8( 1000 )이며, 여기에 1이 하나 있으므로 12에는 1이 두 개 있습니다. 시프트 규칙만큼 빠르고 왼쪽에서 오른쪽으로 채우는 방식도 같습니다.

Q: 내장 popcount 함수를 사용할 수 있나요?

대부분의 언어에는 Java의 Integer.bitCount 나 C 및 C++의 __builtin_popcount 와 같은 함수가 있으며, 모든 숫자에 대해 이를 호출하면 올바른 답을 얻을 수 있습니다. 면접관은 보통 이 함수 없이 구현하는 버전을 요청하는데, 이 문제의 핵심은 이미 계산한 답을 재사용하는 것이기 때문입니다. 이 점화식은 이러한 함수가 없는 언어에서도 작동합니다.

쉬움비트 조작 동적 계획법

+10

0 이상인 정수 n이 주어집니다. 0부터 n까지의 각 숫자 i에 대해, i를 이진수로 나타냈을 때 1이 몇 번 나타나는지 세세요. n+1개의 항목이 있는 배열로 개수를 반환하세요. 여기서 항목 i는 숫자 i에 대한 개수입니다.

함수

countBits(n: integer) → integer-array

ninteger: 마지막으로 셀 숫자, 0 이상
반환값integer-array: n+1개의 개수를 담은 배열로, 항목 i는 i의 1비트 개수입니다

제약 조건

0 ≤ n ≤ 2 × 10⁴

예제

입력: n = 2
출력: [0, 1, 1]
설명: 2진수에서 0은 0, 1은 1, 2는 10입니다. 즉, 1이 하나도 없는 경우, 그다음은 하나, 그다음도 하나입니다.

입력: n = 5
출력: [0, 1, 1, 2, 1, 2]
설명: 3은 11이고 5는 101로 각각 1이 두 개 있으며, 4는 100으로 1이 하나만 있습니다. 첫 번째 예시의 0, 1, 2와 함께 보면 0부터 5까지의 개수는 0, 1, 1, 2, 1, 2입니다.

제출 시 숨은 테스트 +15개

후속 질문

비트를 세는 내장 함수도 사용하지 않고 각 숫자를 처음부터 다시 세지도 않으면서 O(n) 시간에 배열 전체를 채울 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

각 숫자의 1을 따로 세는 방법은 작동하지만, 같은 작업을 반복합니다. 13은 1101이고 6은 110입니다. 13의 비트는 6의 비트 뒤에 숫자 하나가 더 붙은 것입니다. 답을 오름차순으로 채우면 i에 필요한 개수가 이미 배열에 들어 있으며, 각 항목을 계산하는 데 덧셈 한 번이면 됩니다.

각 숫자의 비트 수를 세세요

핵심 아이디어

0부터 n까지 각 숫자를 하나씩 살펴보며 1비트의 개수를 직접 셉니다. x의 가장 낮은 비트는 x & 1입니다. 이를 카운터에 더한 다음 x >> 1로 x를 오른쪽으로 시프트하면 다음 비트가 가장 낮은 비트가 됩니다. x가 0이 되면 멈춥니다.

13은 1101이므로 오른쪽부터 비트는 1, 0, 1, 1 순서로 나오고, 따라서 개수는 3입니다. 각 숫자는 이진 자릿수마다 한 단계씩 필요하며, n 이하의 숫자는 약 log2 n개의 자릿수를 가집니다.

따라서 전체 실행의 시간 복잡도는 O(n log n)입니다. n = 2 × 10^4이면 약 20,000 × 15 = 300,000단계이므로 제한 시간 안에 실행됩니다. 하지만 여전히 중복 작업을 합니다. 13을 셀 때 6에서 이미 수행한 모든 단계를 반복합니다. 출력 배열을 제외한 공간 복잡도는 O(1)입니다.

알고리즘

빈 결과 목록을 시작합니다.
0부터 n까지 각 i에 대해 count를 0으로 설정하고 x를 i로 설정합니다.
x가 0보다 큰 동안 x & 1을 count에 더하고 x를 오른쪽으로 한 비트 이동합니다.
count를 결과에 추가합니다.
결과를 반환합니다.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

숫자의 절반을 바탕으로 만들기

핵심 아이디어

i를 오른쪽으로 한 비트 이동하면 마지막 이진 숫자가 삭제됩니다. 따라서 i에는 i >> 1의 1 비트가 모두 있고, 마지막 숫자가 1이면 비트가 하나 더 있습니다. 이 마지막 숫자는 i & 1이므로, 규칙은 bits[i] = bits[i >> 1] + (i & 1)입니다.

1 이상의 모든 i에 대해 i >> 1은 i보다 작습니다. bits[0] = 0에서 시작해 배열을 왼쪽에서 오른쪽으로 채우면, 조회하는 항목은 항상 이미 채워져 있습니다. 이것이 동적 프로그래밍입니다. 각 답은 더 작은 답을 바탕으로 만들어집니다.

n = 5인 경우: bits[1] = bits[0] + 1 = 1, bits[2] = bits[1] + 0 = 1, bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2. 각 항목을 계산하는 데 시프트 한 번, AND 연산 한 번, 덧셈 한 번이 필요하므로 시간 복잡도는 O(n)이며 출력 외에는 메모리가 필요하지 않습니다.

알고리즘

n+1개의 0으로 이루어진 배열 bits를 만듭니다. bits[0]은 0으로 유지됩니다.
1부터 n까지의 i에 대해 bits[i]를 bits[i >> 1] + (i & 1)로 설정합니다.
bits를 반환합니다.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

함정과 경계 사례

규칙은 한 줄이면 충분하지만, 그 주변에 버그가 숨어 있습니다.

배열에는 n개가 아니라 n+1개의 항목이 있습니다. n = 0일 때 답은 [0]입니다. 항목은 하나이며, 숫자 0에 해당합니다.
연산자 우선순위에 주의하세요. Python, C, Java, JavaScript에서는 +가 &보다 우선순위가 높으므로, bits[i >> 1] + i & 1은 (bits[i >> 1] + i) & 1로 해석됩니다. (i & 1)을 괄호로 묶어 두세요.
bits[i >> 1] 대신 bits[i-1]을 조회하는 경우입니다. 이웃한 수에는 단순한 규칙이 없습니다. 7은 111로 1이 세 개이고, 8은 1000으로 1이 하나입니다.
Lua와 R에서는 배열 인덱스가 1부터 시작하므로, i의 개수는 인덱스 i+1에 있고 i >> 1의 조회 위치는 인덱스 floor(i/2) + 1입니다. 러너의 Lua에는 시프트 연산자가 없으므로 math.floor(i / 2)로 반으로 나누세요.
각 숫자를 이진 문자열로 바꾼 다음 1 문자의 개수를 세면 올바른 답을 얻지만, 숫자마다 새 문자열을 만듭니다.

자주 묻는 질문4

Counting Bits의 시간 복잡도는 무엇인가요?

가장 좋은 해결책은 O(n) 시간에 실행됩니다. n+1개의 항목은 각각 이전 항목 하나에 덧셈 한 번을 적용해 얻습니다. 모든 숫자의 비트를 하나씩 세면 O(n log n) 시간이 걸립니다. n 이하의 숫자는 이진수로 약 log2 n자리이기 때문입니다. 두 방법 모두 출력 배열 외에는 O(1) 메모리를 사용합니다.

bits[i] = bits[i >> 1] + (i & 1)는 왜 작동하나요?

i >> 1은 마지막 이진 숫자를 제거한 i이고, i & 1은 제거된 숫자입니다. i의 1의 개수는 더 짧은 수의 1의 개수에 마지막 숫자를 더한 값입니다. 1011인 11의 경우, 더 짧은 수는 5(101, 1이 두 개)이고 마지막 숫자는 1이므로 11에는 1이 세 개 있습니다.

Counting Bits를 위한 다른 O(n) 점화식이 있나요?

네. i & (i-1)은 i의 가장 낮은 1비트를 지우므로, 1 이상의 모든 i에 대해 bits[i] = bits[i & (i-1)] + 1입니다. 12(1100)의 경우 12 & 11은 8(1000)이며, 여기에 1이 하나 있으므로 12에는 1이 두 개 있습니다. 시프트 규칙만큼 빠르고 왼쪽에서 오른쪽으로 채우는 방식도 같습니다.

내장 popcount 함수를 사용할 수 있나요?

대부분의 언어에는 Java의 Integer.bitCount나 C 및 C++의 __builtin_popcount와 같은 함수가 있으며, 모든 숫자에 대해 이를 호출하면 올바른 답을 얻을 수 있습니다. 면접관은 보통 이 함수 없이 구현하는 버전을 요청하는데, 이 문제의 핵심은 이미 계산한 답을 재사용하는 것이기 때문입니다. 이 점화식은 이러한 함수가 없는 언어에서도 작동합니다.

Python

def countBits(n):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

입력

n = 2

기대값

[0, 1, 1]