LeetCode의 338번째 문제인 Counting Bits를 함께 풀어보도록 하겠습니다.
문제
정수 n이 주어졌을 때, 길이가 n + 1인 배열 ans를 반환하시오.
ans[i]는 i에 대한 이진수로 표현했을 때, 1의 개수를 담고 있어야 합니다.
예제
입력: n = 2
출력: [0,1,1]입력: n = 5
출력: [0,1,1,2,1,2]풀이 1
이 문제를 푸는 가장 단순한 방법은 0부터 n까지의 정수를 이진수로 바꾼 후에 그 안에 들어 있는 1의 개수를 세는 것입니다.
십진수를 이진수로 바꾸려면 0이 될 때까지 2로 계속해서 나눠봐야 하죠?
그리고 나머지가 1인 경우만 세면 될 것입니다.
그럼 이 알고리즘을 파이썬으로 구현해볼까요?
class Solution:
def countBits(self, n: int) -> List[int]:
def count(num):
cnt = 0
while num:
cnt += num % 2
num //= 2
return cnt
return [count(num) for num in range(n + 1)]이 풀이의 시간 복잡도는 O(n * log n)이 되는데요.
1의 개수를 세어주는 내부 함수의 복잡도가 O(log n)인데, 이 작업을 n + 1번 수행해야하기 때문입니다.
공간 복잡도는 결과 배열을 제외하면 고정된 개수의 변수만 사용하므로 O(1)이 되겠습니다.
풀이 2
이전 풀이를 보면 2로 나누고 나머지를 구하는 작업을 0부터 n까지 모든 숫자를 상대로 하고 있기 때문에 상당히 비효율적입니다.
어떻게 하면 더 작은 숫자를 상대로 구한 이진수 내의 1의 개수를 더 큰 숫자를 상대로 구할 때 활용할 수 있을까요?
우리 한번 0부터 15까지의 이진수를 구해서 표로 나타내보겠습니다.
| 십진수 | 이진수 | 패턴 |
|---|---|---|
| 0 | 0000 | 0 |
| 1 | 0001 | 1 |
| 2 | 0010 | 1 + 0 |
| 3 | 0011 | 1 + 1 |
| 4 | 0100 | 1 + 00 |
| 5 | 0101 | 1 + 01 |
| 6 | 0110 | 1 + 10 |
| 7 | 0111 | 1 + 11 |
| 8 | 1000 | 1 + 000 |
| 9 | 1001 | 1 + 001 |
| 10 | 1010 | 1 + 010 |
| 11 | 1011 | 1 + 011 |
| 12 | 1100 | 1 + 100 |
| 13 | 1101 | 1 + 101 |
| 14 | 1110 | 1 + 110 |
| 15 | 1111 | 1 + 111 |
위 표를 자세히 살펴 보시면 다음과 같이 반복되는 패턴을 찾으실 수 있으실 거에요.
숫자가 2배가 될 때 마다 이진수로 나타내었을 때 맨 앞에 새로운 1이 붙게 되기 때문이죠.
1의 이진수 내의1의 개수 =1+0의 이진수 내의1의 개수2부터3사이의 이진수 내의1의 개수 =1+0부터1사이의 이진수 내의1의 개수4부터7사이의 이진수 내의1의 개수 =1+0부터3사이의 이진수 내의1의 개수8부터15사이의 이진수 내의1의 개수 =1+0부터7사이의 이진수 내의1의 개수
이 패턴을 수식으로 나타내보면 dp[num] = 1 + arr[num - MSB]게 될텐데요.
여기서 MSB(Most Significant Bit), 즉 최상위 비트는 1, 2, 4, 8, 16, ... 식으로 2배씩 커지게 되는데, 숫자가 커질수록 MSB가 천천히 커지는 것을 볼 수 있습니다.
정확히 얘기하면 숫자가 기존 MSB의 정확히 2배가 될 때마다 MSB가 2 배로 늘어나게 됩니다.
| 이진수 | 십진수 | 최상위 비트 | 1의 개수 |
|---|---|---|---|
| 0 | 0 | 0 | |
| 1 | 1 | 1 | 1 + dp[1 - 1] = 1 |
| 10 | 2 | 2 | 1 + dp[2 - 2] = 1 |
| 11 | 3 | 2 | 1 + dp[3 - 2] = 2 |
| 100 | 4 | 4 | 1 + dp[4 - 4] = 1 |
| 101 | 5 | 4 | 1 + dp[5 - 4] = 2 |
| 110 | 6 | 4 | 1 + dp[6 - 4] = 2 |
| 111 | 7 | 4 | 1 + dp[7 - 4] = 3 |
| 1000 | 8 | 8 | 1 + dp[8 - 8] = 1 |
| 1001 | 9 | 8 | 1 + dp[9 - 8] = 2 |
| 1010 | 10 | 8 | 1 + dp[10 - 8] = 2 |
| 1011 | 11 | 8 | 1 + dp[11 - 8] = 3 |
| 1100 | 12 | 8 | 1 + dp[12 - 8] = 2 |
| 1101 | 13 | 8 | 1 + dp[13 - 8] = 3 |
| 1110 | 14 | 8 | 1 + dp[14 - 8] = 3 |
| 1111 | 15 | 8 | 1 + dp[15 - 8] = 4 |
결국은 동적 계획법(Dynamic Programming)으로 해결할 수 있다 문제라는 것을 알 수 있게 되었네요!
지금까지 설명드린 알고리즘을 파이썬으로 구현해보겠습니다.
class Solution:
def countBits(self, n: int) -> List[int]:
dp = [0] * (n + 1)
msb = 1
for num in range(1, n + 1):
if msb << 1 == num:
msb = num
dp[num] = 1 + dp[num - msb]
return dp이 풀이는 단순히 O(1)의 시간이 걸리는 로직을 1부터 n까지 한 번 루프를 돌고 있기 때문에 시간 복잡도가 O(n)으로 향상이 됩니다.
풀이 3
이번에는 MSB(Most Significant Bit) 대신에 LSB(Most Significant Bit), 즉 최하위 비트를 활용해보면 어떨까요?
최하위 비트는 숫자를 2로 나눈 나머지나, 비트 연산 & 1을 해주면 구할 수 있는데요.
숫자가 1씩 커짐에 따라 0과 1이 계속해서 반복될 것입니다.
그럼 우리는 최하위 비트를 제외한 이진수의 나머지 부분에서 1의 개수만 세면 될텐데요.
최하위 비트를 제외하려면 숫자를 2로 나눈 몫이나, 비트 연산 >> 1을 해주면 구할 수 있습니다.
그러면 현재 숫자보다 적은 숫자가 나오므로 동적 계획법을 사용할 수 있게 됩니다.
| 십진수 | 이진수 | 최하위 비트 제외 | 최하위 비트 | 1의 개수 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 1 | 1 | 1 | dp[0] + 1 = 1 | |
| 2 | 10 | 1 | 0 | dp[1] + 0 = 1 |
| 3 | 11 | 1 | 1 | dp[1] + 1 = 2 |
| 4 | 100 | 10 | 0 | dp[2] + 0 = 1 |
| 5 | 101 | 10 | 1 | dp[2] + 1 = 2 |
| 6 | 110 | 11 | 0 | dp[3] + 0 = 2 |
| 7 | 111 | 11 | 1 | dp[3] + 1 = 3 |
| 8 | 1000 | 100 | 0 | dp[4] + 0 = 1 |
| 9 | 1001 | 100 | 1 | dp[4] + 1 = 2 |
| 10 | 1010 | 101 | 0 | dp[5] + 0 = 2 |
| 11 | 1011 | 101 | 1 | dp[5] + 1 = 3 |
| 12 | 1100 | 110 | 0 | dp[6] + 0 = 2 |
| 13 | 1101 | 110 | 1 | dp[6] + 1 = 3 |
| 14 | 1110 | 111 | 0 | dp[7] + 0 = 3 |
| 15 | 1111 | 111 | 1 | dp[7] + 1 = 4 |
나누기를 사용해서 알고리즘을 구현해보겠습니다.
class Solution:
def countBits(self, n: int) -> List[int]:
dp = [0] * (n + 1)
for num in range(1, n + 1):
dp[num] = dp[num // 2] + (num % 2)
return dp비트 연산을 사용해서 구현할 수도 있습니다.
class Solution:
def countBits(self, n: int) -> List[int]:
dp = [0] * (n + 1)
for num in range(1, n + 1):
dp[num] = dp[num >> 1] + (num & 1)
return dp이전 풀이보다 코드가 살짝 더 간결해지기는 했지만, 시간 복잡도와 공간 복잡도는 모두 여전히 O(n)이므로 빅오 계산법 기준으로는 의미있는 차이가 없습니다.
마치면서
이 문제가 너무 어려우셨다면 비슷하지만 좀 더 쉬운 문제인 Number of 1 Bits도 풀어보시라고 추천드립니다.