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의 수가 몇..
자료알고/알고리즘
2019. 11. 22. 04:02
최근댓글