Counting Bits

Q: 비트 세기의 시간 복잡도는 무엇인가요?

최적의 해법은 O(n) 시간에 실행됩니다. n+1 개의 항목은 각각 이전 항목 하나에 덧셈 한 번을 적용해 얻습니다. 각 숫자의 비트 수를 따로 세면 O(n log n)이 걸립니다. 두 방법 모두 출력 배열 외에는 O(1) 메모리만 사용합니다.

Q: 비트 개수를 세는 또 다른 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가 i의 이진 표현에 있는 1의 개수인 n+1개의 항목을 가진 배열을 반환합니다.

함수

countBits(n: integer) → integer-array

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

제약 조건

0 ≤ n ≤ 2 × 10⁴

예제

입력: n = 2
출력: [0, 1, 1]
설명: 이진수에서 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, 1, 1, 2, 1, 2입니다.

후속 질문

비트를 세는 내장 함수 없이, 각 숫자를 처음부터 세지 않고 O(n) 시간에 배열 전체를 채울 수 있나요?

힌트

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

3개 중 0개 열림

풀이

모든 숫자를 처음부터 세면 작업이 반복됩니다. 13은 1101이며, 6의 비트(110) 끝에 숫자 하나를 더한 것입니다. 답을 오름차순으로 채우면 각 항목은 더 작은 항목에 덧셈 한 번을 더해 재사용합니다.

각 숫자의 비트 수 세기

핵심 아이디어

각 숫자의 1비트를 직접 세세요. 카운터에 x & 1을 더하고, 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단계입니다.

알고리즘

빈 결과 목록을 시작합니다.
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 & 1은 그 숫자입니다. 따라서 i의 1 비트 개수는 i >> 1의 1 비트 개수에 마지막 숫자를 더한 값입니다: bits[i] = bits[i >> 1] + (i & 1).

1 이상의 모든 i에 대해 i >> 1은 i보다 작으므로, bits[0] = 0에서 시작해 배열을 왼쪽에서 오른쪽으로 채우면 읽는 항목은 항상 준비되어 있습니다. n = 5인 경우: 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+1개 대신 n개의 항목을 반환하는 경우. n = 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은 1이 세 개 있는 111이고, 8은 1이 하나 있는 1000입니다.
Lua와 R에서는 배열이 1부터 시작하므로, i의 개수는 인덱스 i+1에 있고 i >> 1의 조회 위치는 floor(i/2) + 1입니다. Lua 5.1에는 시프트 연산자가 없으므로 math.floor(i / 2)로 나누세요.

자주 묻는 질문3

비트 세기의 시간 복잡도는 무엇인가요?

최적의 해법은 O(n) 시간에 실행됩니다. n+1개의 항목은 각각 이전 항목 하나에 덧셈 한 번을 적용해 얻습니다. 각 숫자의 비트 수를 따로 세면 O(n log n)이 걸립니다. 두 방법 모두 출력 배열 외에는 O(1) 메모리만 사용합니다.

비트 개수를 세는 또 다른 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처럼 각 숫자마다 하나씩 호출하면 정답을 얻을 수 있습니다. 면접관들은 보통 이를 사용하지 않는 버전을 요구합니다. 문제의 핵심은 이미 계산한 답을 재사용하는 것이기 때문입니다.

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

테스트 #1

테스트 #2

인자

n = 2

예상 출력

[0, 1, 1]