99클럽 코테 스터디 17일차 TIL + 동적 프로그래밍 Dynamic Programming, [leetcode] Counting Bits

✨ 문제 

Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

 

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

 

 

 

✨ 개념

동적 프로그래밍 Dynamic Programming

- 복잡한 문제를 작은 문제로 분해하여 해결하는 알고리즘 기법.

- 동적 프로그래밍을 적용하기 위해서는 다음 2가지 조건이 필요하다.

최적 부분 구조 : 전체 문제의 최적해를 부분 문제의 최적해로부터  찾을 수 있어야함.

중복되는 부분 문제 : 부분 문제가 여러번 중복되어 반복계산 되어야함.

 

동적 프로그래밍의 두 가지 접근 방식

상향식 접근법 Bottom-up

- 작은 하위 문제부터 해결해 나가며 차례로 큰 문제를 해결하는 방식.

- 일반적으로 반복문을 사용하여 구현됨.

 

하향식 접근법 Top-down

- 큰 문제를 해결하기 위해 재귀적으로 하위 문제를 호출하는 방식

- 하위 문제의 결과를 저장하기 위해 메모이제이션을 사용함.

 

 

 

✨ 최종코드

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            result[i] = result[i / 2] + (i % 2);
        }
        return result;
    }
}