cleanUrl: /posts/counting-bits-difference-division-and-multiple
Counting Bits 라는 알고리즘을 풀게 되었다. 이 문제는 2020년 6월에 4일 동안 고민했으나 풀지 못했던 나에게 알고리즘의 좌절을 주었던 문제이다. 2021년 1월 10일날 이 문제를 푼건 나에게 여러모로 기쁜 의미가 있다
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
어떤 양의 정수 n이 주어지면 0~n 까지 총 n+1 개의 배열을 만들어 이진수로 변환시 1의 개수를 반환하는 것이다.
사실 이 문제를 처음 접했을때 막막함은 이루 말할 수 없었다. 2진수로 바꾸어 1의 개수를 세자니 $O(n^2)$ 이 될 것이다. 그런데 follow up 을 보면 $O(n)$ 으로 풀라는 것이다.
심지어 c++ 에서 제공하는 2진수의 1을 count 하는 기능은 사용도 하지 말라고 한다
혼자 연습장에 쓰면서 접근한걸 보면 얼마나 멘붕이었는지 보여줄 수 있을것 같다.
하지만 여기서 특정한 숫자가 반복되어서 나타남을 확인할 수 있다.
그 반복 범위는 0~1, 2~3, 4~7, 8~15 와 같이 2의 제곱근의 범위에서 그 규칙성을 찾을 수 있다.
문제를 설명하기 위해 사용할 변수의 정의를 먼저 설명한다.
num: param으로 입력 받은 변수result: 결과로 반환할 배열재미있는 규칙은