Gosper's Hack Algorithm

이번 시간에는 Gosper’s Hack Algorithm을 소개하겠습니다.

Gosper’s Hack 알고리즘이란?

Hamming Weight란 비트 집합에서 1로 설정된 비트의 숫자를 의미합니다. population count(popcount)라고도 부릅니다.

Gosper’s Hack은 정수와 같은 Hamming Weight를 가진 바로 다음 정수를 O(1)의 시간복잡도로 구하는 알고리즘입니다.

즉, 어떤 정수 x에 대해 x < y이면서 count_bit(x) == count_bit(y)를 만족시키는 가장 작은 정수 y를 구하는 알고리즘입니다.

이 알고리즘은 수학자이자 컴퓨터 과학자인 Bill Gosper에 의해 개발되어 조합 최적화 문제의 해결에 사용되고 있는 알고리즘입니다.

설명

‘어떤 정수 n에 대하여, 1부터 n까지의 정수 중 Hamming Weight가 k인 모든 정수를 구해라’와 같은 문제가 주어졌을 때, 어떻게 해결할 수 있을까요?

Brute-Force

Brute-Force로 풀 경우, 1부터 n까지의 모든 정수의 비트의 개수를 계산하고 k와 비교해야 합니다. O(n log n)의 시간 복잡도가 나오니, n이 커질수록 시간이 기하급수적으로 늘어나게 됩니다. 코딩 테스트에서는 못 써먹겠죠.

def find_int_with_same_pop_counts(n: int, k: int) -> List[int]:
    answer = []

    for i in range(1, n + 1):
        j = i
        bits = 0
        while j > 0:
            bits += j & 1
            j >>= 1
        if bits == k:
            answer.append(i)

    return answer

Gosper’s Hack

Gosper’s Hack 알고리즘을 이용하면, 모든 정수를 계산할 필요 없이 정확히 Hamming Weight가 k인 값들만을 순서대로 구할 수 있습니다. 이게 어떻게 가능한 것일까요?

계산 요약

어떤 수보다 크면서 동일한 Hamming Weight를 가진 가장 작은 수는 어떻게 구할까요? 이진 표현의 예시를 통해 알아보겠습니다.

숫자는 커지되 1비트의 개수는 동일해야 하므로 1비트가 왼쪽으로 이동해야 합니다. 그러므로 어떤 위치에 있는 1비트든 그보다 왼쪽에 있는 0비트와 위치를 바꾸면 이 조건을 만족하는 수가 됩니다.

101110 -> 110011, 110101, 110110, 111010, 111100...

그렇다면 위 조건을 만족하는 수 중 가장 작은 수는 어떻게 구할까요? 눈치 빠른 분들은 위의 예시를 보며 감을 잡으셨을 것 같습니다.

숫자가 증가하기 위해서는 1비트를 반드시 이동시켜야 하므로, 숫자를 증가시키면서도 가장 작은 수를 얻기 위해서는 가장 작은 자릿수의 1비트와 그 왼쪽의 0비트를 바꿔야 합니다. 자릿수가 올라갔으므로, 올라간 자릿수 뒤의 1비트들은 어떻게 배열하더라도 원래 수보다 큽니다. 따라서, 올라간 자릿수 뒤의 1비트들을 가장 낮은 자릿수로 옮기면 조건을 만족하는 가장 작은 수를 구할 수 있습니다.

101110 -> 110110 -> 110011

정리하자면, 왼쪽에 0이 있는 가장 오른쪽의 1비트를 찾고 - 그 비트만큼 더해 왼쪽의 0비트를 1로 바꾸고 -> 바뀐 비트 오른쪽의 1비트들을 찾고 -> 찾은 1비트들을 가장 오른쪽으로 이동시킨다 의 순서로 계산합니다.

비트 연산

Gosper’s Hack 알고리즘을 이해하기 위해서는 먼저 세 가지 비트 연산의 성질에 대해 이해해야 합니다.

비트 연산자

비트 단위의 연산은 별도의 연산자를 사용하여 표기하며, 연산자(게이트)별로 다른 논리적 속성을 가지고 있습니다.

음수의 처리

컴퓨터는 덧셈 회로로만 연산을 처리하기 때문에, 음수를 2의 보수 형태로 처리합니다.

보수란 어떤 기준이 되는 수에 도달하기 위해 부족한 값을 채워 주는 수로, 이진 연산에서는 0이 기준입니다. 즉, 어떤 수의 음수는 양수와 덧셈 연산을 했을 때 값이 0이 되는 수입니다.

그렇다면 2의 보수는 어떻게 구할 수 있을까요? 방법은 간단합니다. 8비트 이진수 00000101에 NOT(~) 연산을 적용하면 결과값은 1의 보수, 11111010이 됩니다. 여기에 1을 더하면 결과값은 2의 보수, 11111011이 됩니다.

원래 수에 2의 보수(음수)를 더하는 연산을 할 시, 00000101 + 11111011 = (1)00000000이 됩니다. 8비트 환경이므로 모든 수를 올림하여 생긴 가장 왼쪽의 1비트는 오버플로우로 사라지고 0만 남게 됩니다. 즉, 2의 보수를 이용하여 덧셈 회로만으로 A - B = A + (-B) = A + (~B + 1)와 같이 뺄셈을 구현할 수 있는 것입니다.

마지막 비트 구하기

위에서 알아본 음수의 특성을 이용해 손쉽게 가장 작은 1비트의 위치를 알아낼 수 있습니다.

 x     = 00000101
~x     = 11111010
~x + 1 = 11111011
x & -x = 00000001

음수, 즉 2의 보수는 x에 NOT(~) 연산을 적용하여 모든 비트를 뒤집고 1을 더하여 구할 수 있습니다. 그렇다면, 2의 보수의 이진 표현은 가장 오른쪽의 1을 기준으로 왼쪽은 모두 원본과 비트가 반대이고 오른쪽은 모두 0일 것입니다. 따라서, AND(&) 연산을 적용하여 가장 오른쪽의 1비트의 위치(값)를 정확하게 알아낼 수 있습니다.

위의 세 가지 개념들을 이해했다면 Gosper’s Hack을 문제 없이 이해하실 수 있습니다.

구현

def find_int_with_same_pop_counts(n: int, k: int) -> List[int]:
        answer = []
        curr = (1 << k) - 1

        while curr <= n:
            answer.append(curr)

            lowest_bit = curr & -curr
            highest_bit = curr + lowest_bit
            changed_bits = curr ^ highest_bit
            changed_bits >>= 2
            trailing_ones = changed_bits // lowest_bit

            curr = highest_bit | trailing_ones

        return answer

Gosper’s Hack을 구현한 코드입니다. 위에서 요약한 계산 과정에 대응하는 코드를 한 줄씩 설명하겠습니다.

curr = (1 << k) - 1

계산할 숫자의 시작 위치에 해당합니다. 1을 k만큼 왼쪽으로 밀고 1을 빼서 k개의 1비트만으로 구성된 정수를 만듭니다.

ex) k = 3일 때 1 << 3 = 1000, 1000 - 1 = 0111

while curr <= n:

curr의 범위를 최대 n으로 제한합니다.

lowest_bit = curr & -curr

왼쪽에 0이 있는 가장 오른쪽의 1비트를 찾는 부분에 해당합니다. 위에서 설명하였듯, 음수의 특성을 이용해 마지막 1비트의 위치(값)을 구할 수 있습니다.

ex) 100110 & 011010 = 000010

highest_bit = curr + lowest_bit

그 비트만큼 더해 왼쪽의 0비트를 1로 바꾸는 부분에 해당합니다. 왼쪽에 0비트가 있는 가장 낮은 자릿수의 1비트에 1을 더해줌으로서 0비트에 도달할 때까지 올림을 전달하여 자릿수를 한 칸 이동시킵니다.

ex) 100110 + 000010 = 101000

가장 낮은 자릿수에서 0까지 올림을 전달하였으므로, 올림한 자릿수는 0이 됩니다. 따라서 highest_bit는 자릿수 올림은 되었으나 count_bits(highest_bit) <= k인 상태, 즉 왼쪽만 정답 상태인 변수가 됩니다.

changed_bits = curr ^ highest_bit

바뀐 비트 오른쪽의 1비트들을 찾는 부분에 해당합니다. XOR(^) 연산은 원본과 다른 부분만 남기므로, highest_bit를 계산할 때 뒤집힌 비트의 자릿수만 1이고 나머지가 모두 0인 비트 마스크, 즉 올림 과정에서 소실한 1비트들을 포함한 비트 마스크가 생성됩니다.

ex) 100110 ^ 101000 = 001110

changed_bits >>= 2

위 비트 마스크는 뒤집힌 0과 맨 왼쪽의 1, 즉 소실되지 않은 1비트 2개를 포함하고 있기 때문에 2번의 Shift로 소실되지 않은 비트의 몫을 지워줘야 합니다.

trailing_ones = changed_bits // lowest_bit

찾은 1비트들을 가장 오른쪽으로 이동시키는 부분에 해당합니다. 생성한 비트 마스크를 가장 낮은 비트로 나눔으로서 가장 낮은 비트 오른쪽의 0 비트들을 제거합니다. 이를 통해 위에서 찾은 1비트들을 우측 정렬하고, trailing_ones는 오른쪽만 정답 상태인 변수가 됩니다.

curr = highest_bit | trailing_ones

앞서 설명하였듯, 뒤집힌 0의 위치를 기준으로 highest_bit는 왼쪽만 정답 상태인 변수, trailing_ones는 오른쪽만 정답 상태인 변수입니다. 따라서, 이 둘을 OR(|) 연산으로 합침으로써 하나의 정답을 도출할 수 있습니다.

시간 & 공간 복잡도

각 비트 연산은 O(1)의 시간 복잡도를 가지므로 다음 조합을 찾는 데 걸리는 시간은 O(1)입니다.

전체 n비트 중에서 k개를 선택하는 모든 조합의 개수는 이항 계수 식 O(_nC_k)로 결정됩니다. 알고리즘은 정확히 이 횟수만큼만 루프를 도므로, 전체 시간 복잡도는 O(_nC_k)가 됩니다.

재귀 호출 스택과 별도 메모리를 사용하지 않으므로, 공간 복잡도는 O(1)입니다.

응용

오늘도 하나 더 배웠네요. 좋습니다! 그런데, 이 빠른 알고리즘을 단순 비트 연산 외에 어디에 응용할 수 있을까요?

1. 정해진 크기의 모든 부분 집합 생성

n개의 요소 중 k개를 선택하는 경우의 수, 즉 정수로 표현할 수 있는 범위 내의 조합을 찾을 때 응용할 수 있습니다.

Gosper’s Hack 알고리즘은 k개의 1비트를 사용하여 그 안에서 나올 수 있는 모든 경우의 수를 찾습니다. 각 비트를 대응하는 정수로 치환하면? 조합이 됩니다.

2. 비트마스크 DP 최적화

n개의 상태 중 정확히 k단계까지 진행된 상태들만 골라 다음 상태를 계산할 때 응용할 수 있습니다.

일반적인 비트마스크 DP는 0부터 2^n − 1까지 모든 정수를 순회하며 비트 개수를 확인하지만, Gosper’s Hack을 응용하면 정확히 k개의 비트가 켜진 정수들만 바로 찾아내어 불필요한 탐색을 건너뛰도록 최적화할 수 있습니다.

연습 문제

LeetCode 401. Binary Watch

k개의 비트로 이루어진 이진 표현의 모든 조합을 찾는 문제입니다. Gosper’s Hack을 바로 써먹을 수 있습니다.

LeetCode 77. Combinations

1부터 n까지의 숫자 중, k개로 만드는 모든 조합을 찾는 문제입니다. 정해진 크기의 모든 부분 집합 생성 응용을 연습할 수 있습니다.

LeetCode 1879. Minimum XOR Sum of Two Arrays

두 배열의 요소를 재배열하여 XOR 합의 최솟값을 구하는 문제입니다. 비트마스크 DP 최적화 응용을 연습하기에 좋으나. Hard임을 감안해주세요.