방법1 : O(nlogn)

• 직관적, 현실적
• 각 k에 대하여 2로 나눠가면서 bitwise 1의 개수를 더하는 방식
• Max n = 10^5이므로, 충분히 가능한 방식

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = []
        # O(logN)
        for elmt in range(n+1):          
          tmp = 0 
          # O(logN)         
          while(elmt != 0):            
            if(elmt % 2 != 0):
              tmp += 1
            elmt //= 2
          ans.append(tmp)        
        return ans

⭐방법2 :  O(n)

• DP
• Bitwise 표현의 성질을 이용한다.
• 각 숫자를 2의 거듭제곱을 기준으로 분류했을때, 이전 구간의 형태가 다음 구간에서 나타나는 성질을 이용한다.
• 따라서, rightShift한 값에 없어진 rightmost bit의 값을 더해주면 해당 elmt의 값이 나온다.

rightShift 했을때 값 : ans[i >> 1]

없어진 bit : i & 1

→ BottomUp 방식

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)
        return ans