99클럽 코테 스터디 9일차 TIL + 동적 계획법

오늘의 공부 키워드

• 동적계획법의 개념
• 338. Counting Bits

동적 계획법의 개념

동적 계획법(Dynamic Programming, DP)은 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 재사용함으로써 전체 문제를 효율적으로 해결하는 방법입니다. 이 문제에서는 각 숫자 iii의 이진 표현에서 1의 개수를 계산할 때, 이전에 계산한 결과를 재사용하여 중복 계산을 피할 수 있습니다.

 

338. Counting Bits

문제 해석

주어진 정수 n이 있을 때, 길이가 n+1인 배열 ans를 반환하는 문제입니다. 배열 ans는 다음과 같은 조건을 만족해야 합니다: 각 iii (0 <= i <= n)에 대해, ans[i]는 iii의 이진 표현에서 1의 개수입니다.

 

예시

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

제약 조건

• 0≤n≤105

추가 도전 과제

• 시간 복잡도를 O(nlog⁡n)이 아닌 O(n)으로 줄일 수 있는지 확인합니다.
• 내장 함수(__builtin_popcount와 같은)를 사용하지 않고 문제를 풀 수 있는지 확인합니다.

문제 풀이 방법

이 문제를 풀기 위한 최선의 방법은 동적 계획법(DP)을 이용하는 것입니다. 각 숫자 iii에 대해, iii가 짝수인지 홀수인지에 따라 1의 개수를 다르게 계산할 수 있습니다.

• 짝수 iii: 이진수로 나타낸 iii는 마지막 비트가 0입니다. 따라서 iii를 2로 나눈 몫의 1의 개수와 동일합니다. 즉, ans[i]=ans[i//2]입니다.
• 홀수 iii: 이진수로 나타낸 iii는 마지막 비트가 1입니다. 따라서 iii를 2로 나눈 몫의 1의 개수에 1을 더한 값과 같습니다. 즉, ans[i//2]+1입니다.

이 규칙을 이용하면 시간 복잡도 O(n)에 문제를 해결할 수 있습니다.

 

코드 설명

def countBits(n):
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        ans[i] = ans[i >> 1] + (i & 1)
    return ans

# 예시 테스트
print(countBits(2))  # [0, 1, 1]
print(countBits(5))  # [0, 1, 1, 2, 1, 2]

 

 

코드 설명

1. 배열 ans를 크기 n+1n + 1n+1로 초기화합니다.
2. 1부터 nnn까지 반복하면서 각 숫자에 대해 1의 개수를 계산하여 ans에 저장합니다.
   • i >> 1은 i를 2로 나눈 몫입니다.
   • i & 1은 i의 마지막 비트가 1인지 0인지를 나타냅니다.
3. 최종적으로 배열 ans를 반환합니다.

오늘의 회고

 

• 새로운 개념인 동적계획법을 배울수 있었다.
• 좀더 끈질기게 고민하고 문제를 풀어야 하는데 쉽게 포기하는게 아닌가 하고 반성하게 된다.
• 코드 리뷰와 문제 이해는 정말 중요한거 같다.
• 코딩테스트 문제만 풀지말고 기록도 남겨야 함을 느낀다.
• 공부할것은 더욱 많음을 느낀다.
• 문제를 지금 거의 풀수는 없지만 복습하고 복습하고 복습하기 위해 기록을 남긴다.
• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자