leetcode 338 counting bits : 마지막 켜진 비트만 알면 된다.

 leetcode 338번, Counting bits를 풀어보도록 합시다. 1부터 n까지 켜진 비트의 수를 구하려고 합니다. 그런데 이것을 O(n)에 구하려고 합니다. 어떻게 하면 좋을까요? n이 100만까지 있을 때, 20개의 비트를 일일히 보는 것은 꽤 큰 낭비입니다. 이를 어떻게 하면 좋을까요? 이전에 계산했던 정보를 다시 재사용하는 방법은 없을까요?

 

 

---

 먼저 dp[x]를 위와 같이 정의합니다. 그러면, dp[0]은 0일 겁니다. 0을 2진수로 표현하면 00..00입니다. 비트 값이 1인 것이 없습니다. 따라서, dp[0]의 값은 0으로 초기화를 합니다. 그러면, dp[x]의 값은 어떻게 구하면 좋을까요?

 

 

 6을 생각해 봅시다. 이것은 2진수로 0110로 나타낼 수 있습니다. 켜져 있는 비트 1의 수가 몇 개인가요? 2개입니다. 이것은 어떻게 나왔나요? 2^1을 표현하는 비트가 켜져 있고, 2^2를 표현하는 것 또한 켜져 있기 때문에 2개가 나온 것입니다. 그러면, 2^1을 표현하는 bit를 꺼 봅시다.

 

 

 그러면, 이것을 10진수로 표현하면 4가 됩니다. 6에서 2를 뺀 것이죠. 4는 켜져 있는 상태 수가 1개입니다. 여기에서, 상태 2^1을 켰기 때문에, 6은 2개가 켜져 있다고 말을 할 수 있나요?

 

 

 그러면 우리는 자연수 6이, 가장 마지막으로 켜진 bit를 찾아야 합니다. 6이 x라면, -x는 1..1010으로 표현할 수 있습니다. 이 둘을 and 연산을 하면, 0..010이 나옵니다. 즉, x가 6일 때, x&(-x)의 값은 2가 나옵니다. 따라서, dp 식은 다음과 같이 작성할 수 있습니다.

 

 

 단, dp[0]의 값은 0입니다. 이것을 그대로 코드로 구현하면 아래와 같습니다.

 

 시간 복잡도는 O(n)입니다. 이미 구한 정보를 토대로, 필요 없는 정보는 재계산하지 않습니다.

 

 

---

 여기서 끝내면 시시하니, 다른 코드를 봅시다. 다음과 같은 approach는 어떤가요?

 

 

 다이나믹 프로그래밍을 이용하지 않았습니다. 단지, 간단한 bit 연산을 이용했을 뿐인데요. (cur&(-cur))는, 현재 켜진 비트 중, 최하위 비트만을 가진 정수를 결과값으로 리턴합니다. 예를 들어 cur의 값이 6이였다면 2를, cur가 7이였다면 1이 될 겁니다.

 

 

 그러면, cur에서 (cur&(-cur))을 뺀다는 것은, 켜져 있는 bit 하나를 지우겠다는 말과 동치임을 알 수 있습니다. 그러면, 위 코드의 시간 복잡도는 어떻게 될까요? n = 2^20 - 1인 경우를 생각해 봅시다. 일단, 구간 [0,1]까지 켜진 비트의 총 갯수는 1개, [0,3]까지는 4개입니다.

 

 

 그러면, [0, 2^n-1]까지 켜진 총 bit의 수가 X개라면, [0,2^(n+1)-1]까지 켜진 총 bit 수는 몇 개일까요? [2^n, 2^(n+1)-1] 구간에 있는 정수의 갯수는 2^n개입니다. 이는 노란색 부분으로 칠한, 켜져 있는 상태의 수와 같습니다. 다음에, 0..0, 1..1 패턴은 [0,2^(n+1)-1]과 동일하게 나타납니다.

 

 따라서, [0,2^(n+1)-1]까지 켜진 총 bit 수는 2X + 2^n이 될 겁니다. 2^n-1을 t로 치환해 봅시다. 계산을 편하게 하기 위해서, 2^n도 대략 t로 치환하고, 2^(n+1)-1은 2t로 치환하도록 합시다. t가 2의 거듭제곱 꼴이라면 아래 수식이 성립합니다.

 

 이것을 계속 풀어서 쓰면, 켜진 bit의 총 갯수는, nlogn/2 라는 것을 알 수 있습니다. 단, t가 2의 거듭제곱 - 1일 때요. 각 비트마다 켜져 있을 확률이 정확히 1/2이다라는 것을 간파했다면, 복잡한 수식을 풀어 헤치치 않아도 됩니다.

 

 그러면 t가 2의 거듭제곱 - 1이 아닐 때에는 어떨까요? 보라색 구간에 있는 경우인데요. [0,2^k-1]까지의 켜진 총 비트수는, (k2^k)/2입니다. 그리고, [0,2^(k+1)-1]까지 켜진 총 비트수는, (k+1)2^(k+1)/2입니다. t는 2^k-1보다 크고, 2^(k+1)-1보다 작거나 같으므로, [0,t]까지의 켜진 총 비트 수는 (k2^k)/2보다는 크고, (k+1)2^(k+1)/2보다는 작을 겁니다.

 

 그러면 밑이 2인 log(t)는, k보다는 크고 (k+1)보다는 작습니다. 그렇다면 (k+1)2^(k+1)은, 무엇보다는 작은가요? 밑이 2인 log(t)+1 보다는 k+1이 작습니다. 그리고 2t보다는, 2^(k+1)가 더 작습니다. 따라서, 비트 수의 상한은 O(tlogt)급임을 알 수 있습니다. 그러면 최소한 무엇보다는 큰가요? 밑이 2인 log(t)는, k보다는 크다고 했고, t는 2^k보다 크다고 했기 때문에, 하한 역시 O(tlogt)급입니다. 따라서, 켜진 비트를 계속 제거하면서 결과값을 도출하는 알고리즘은, 복잡도가 O(nlogn)입니다.