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의 개수를 구한다
접근 방법
- 비트 연산 사용: 각 숫자를 2진수로 변환한 뒤 1의 개수를 세는 방법을 사용
- 동적 프로그래밍 활용: 이전 계산 결과를 이용하여 빠르게 계산한다
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
코드 단계별 설명
- 리스트 초기화:
- result = [0] * (n + 1)를 통해 길이 n + 1인 리스트를 생성하고 모든 값을 0으로 초기화한다. (리스트로 반환해야 하기 때문에 리스트를 생성)
- 반복문:
- for i in range(1, n + 1)를 통해 1부터 n까지 각 숫자 i에 대해 2진수의 1의 개수를 계산합니다.
- 비트 연산
=====================================================================
비트 연산을 하기에 앞서, result[i] = result[i >> 1] + (i & 1) 가 무슨뜻인지 알아보자
3-1 비트 연산 이해
- i >> 1 (비트 시프트 연산):
- 이 연산은 i를 오른쪽으로 1비트 이동시킨다즉, i를 2로 나눈 몫과 같음
- 예를 들어, i가 5라면 i >> 1은 2가 됨
- ex (이진수: 101) >> 1 = 2 (이진수: 10)
- 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의 개수를 계산할 수 있다
'Algorithm > 릿코드' 카테고리의 다른 글
99클럽 코테 스터디 10일차 509. Fibonacci Number (0) | 2024.06.09 |
---|---|
99클럽 코테 스터디 9일차 118. Pascal's Triangle (1) | 2024.06.08 |
99클럽 코테 스터디 7일차 1221. Split a String in Balanced Strings (0) | 2024.06.05 |
99클럽 코테 스터디 5일차 104. Maximum Depth of Binary Tree (1) | 2024.06.03 |
99클럽 코테 스터디 4일차 226. Invert Binary Tree (0) | 2024.06.03 |