[99클럽 코테 스터디] 7일차 TIL - 동적계획법, Counting Bits

[7일차] 동적계획법

 

문제: https://leetcode.com/problems/counting-bits/description/

* 대충 번역: 정수 n이 주어졌을 때, 길이가 n + 1인 배열 ans를 반환하라. 각 i (0 <= i <= n)에 대해 ans[i]는 i의 이진 표현에서 1의 개수이다.

Solution

이진수의 개념을 정확히 알면, 동적계획법을 적용할 수 있다. 이진수에서 오른쪽으로 한 비트를 이동한다는 것은, 숫자를 2로 나누는 것과 동일한 효과를 가지기 때문이다.

위의 핵심 개념 없이도 오래 걸리는 풀이로 해결이 가능하긴 하다. 내장 함수를 적극 활용했다.

class Solution(object):
    def countBits(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        result = []

        for i in range(n+1):
            one = 0
            binary = list(format(bin(i)[2:]))
            for k in binary:
                if k == '1':
                    one += 1
            result.append(one)

        return result

Better Solution

정수 i를 2로 나누면, 그 결과는 i의 이진 표현에서 오른쪽으로 한 비트를 이동시키는 것과 같다.

예를 들어, 숫자 8의 이진 표현은 '1000'이다. 8을 2로 나누면 4가 되고, 4의 이진표현은 '100'이다. 이는 '1000'을 오른쪽으로 한 비트 이동시킨 '100'과 같은 것이다.

위와 같은 개념으로 DP(동적계획법)을 적용할 수 있다. 8과 8 / 2 의 결과(1의 갯수)가 같기 때문에, 기존의 결과를 재사용하는 셈이기 때문이다.

 

우선 DP는 다음과 같은 순서로 해결할 수 있다.

1. DP테이블 정의하기 (ex. D[i] = i번째 문제 조건일 때의 값)
2. 점화식 찾기
3. 초기값 설정하기

해당 문제에 적용하면 다음과 같다.

1. DP테이블 정의

D[i] = 정수 i를 이진수로 변환했을 때, 1의 갯수

2. 점화식

k가 짝수일 때, 2로 나눈 수의 이진수 표현에 0을 붙인 값과 같다.   

D[k] = D[k//2]

k가 홀수일 때, k-1은 항상 짝수이다. k는 k-1에 1을 더한 값이므로 항상 마지막 비트가 1이되어, D[k-1]에 1의 갯수가 하나 추가된다.

D[k] = D[k-1]+1

3. 초기값 설정

D[0] = 0

D[1] = 1

class Solution(object):
    def countBits(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        ret = [0]
        for i in range(1, n + 1):
            if i % 2 == 0:
                ret.append(ret[i // 2])
            else:
                ret.append(ret[i - 1] + 1)
        return ret

나다어

• 이진수의 개념을 잘 숙지하자.
• 이진수를 반환해주는 파이썬 내장함수는 bin()이다.
• bin()의 결과는 '0b ...' 이므로, 뒷 문자열만 가져오기 위해서 내장함수 format()[인덱스]를 활용할 수 있다.