99클럽 코테 스터디 8일차 338. counting bits

338. counting bits

문제 설명: 비트 개수 세기 (Counting Bits)

문제: 0부터 n까지의 각 숫자에 대해, 2진수 표현에서 1의 개수를 담고 있는 배열을 구하시오.

예시:

• 입력: n = 2 출력: [0, 1, 1] 설명:
  • 0 → 0 (1의 개수: 0)
  • 1 → 1 (1의 개수: 1)
  • 2 → 10 (1의 개수: 1)
• 입력: n = 5 출력: [0, 1, 1, 2, 1, 2] 설명:
  • 0 → 0 (1의 개수: 0)
  • 1 → 1 (1의 개수: 1)
  • 2 → 10 (1의 개수: 1)
  • 3 → 11 (1의 개수: 2)
  • 4 → 100 (1의 개수: 1)
  • 5 → 101 (1의 개수: 2)

제약 조건:

• 0 ≤ n ≤ 10^5

 

 

문제 설명

주어진 숫자 n에 대해 0부터 n까지의 각 숫자에 대해 2진수로 변환했을 때 1의 개수를 구한다

접근 방법

1. 비트 연산 사용: 각 숫자를 2진수로 변환한 뒤 1의 개수를 세는 방법을 사용
2. 동적 프로그래밍 활용: 이전 계산 결과를 이용하여 빠르게 계산한다

class Solution:
    def countBits(self, n: int) -> List[int]:
        # 결과를 저장할 리스트를 0으로 초기화
        result = [0] * (n + 1)
        
        # 1부터 n까지 반복하면서 각 숫자에 대해 1의 개수를 계산
        for i in range(1, n + 1):
            # i >> 1은 i를 2로 나눈 값과 동일 (즉, 오른쪽으로 1 비트 이동)
            # i & 1은 i의 가장 오른쪽 비트가 1인지 0인지 확인
            result[i] = result[i >> 1] + (i & 1)
        
        # 최종 결과 반환
        return result

 

코드 단계별 설명

1. 리스트 초기화:
   • result = [0] * (n + 1)를 통해 길이 n + 1인 리스트를 생성하고 모든 값을 0으로 초기화한다. (리스트로 반환해야 하기 때문에 리스트를 생성)
2. 반복문:
   • for i in range(1, n + 1)를 통해 1부터 n까지 각 숫자 i에 대해 2진수의 1의 개수를 계산합니다.
3. 비트 연산

=====================================================================

비트 연산을 하기에 앞서, result[i] = result[i >> 1] + (i & 1) 가 무슨뜻인지 알아보자

3-1 비트 연산 이해

1. i >> 1 (비트 시프트 연산):
   • 이 연산은 i를 오른쪽으로 1비트 이동시킨다즉, i를 2로 나눈 몫과 같음
   • 예를 들어, i가 5라면 i >> 1은 2가 됨
     • ex (이진수: 101) >> 1 = 2 (이진수: 10)
2. i & 1 (비트 AND 연산):
   •  i의 가장 오른쪽 비트가 1인지 0인지를 확인
   • i & 1은 i를 2로 나눴을 때 나머지와 같음
   • 예를 들어, i가 5라면 i & 1은 1이 됨
     • ex 5 (이진수: 101) & 1 (이진수: 001) = 1 (이진수: 001)

=====================================================================

3-2 코드 설명

• result[i]는 i의 1의 개수를 의미
• result[i >> 1]은 i를 2로 나눈 값의 1의 개수
• i & 1은 i의 가장 오른쪽 비트가 1인지 확인

즉, result[i] = result[i >> 1] + (i & 1)는 다음과 같은 의미

• i를 2로 나눈 값의 1의 개수 (result[i >> 1])에 i의 마지막 비트가 1이면 1을 더하고, 아니면 0을 더합니다.

예시

• i = 5일 때:
  • i >> 1은 2입니다. result[2]는 1입(2의 이진수 10에서 1의 개수).
  • i & 1은 1(5의 이진수 101에서 마지막 비트는 1).
  • 따라서, result[5] = result[2] + 1이 되어 result[5]는 2

이와 같은 방식으로 0부터 n까지 모든 숫자에 대해 1의 개수를 계산할 수 있다