백준 1003번 (파이썬)

Jiya·2025년 3월 9일

DP에 대해 공부하는 기회가 되었던 1003번 문제.
사실 전 알고리즘 공부를 해본 적이 없기에 처음에는 완전 탐색으로 풀려다가 계속 실패했습니다.

처음 답

T = int(input())

def split_until_base(num):
    if num == 0:
        return [0]
    elif num == 1:
        return [1]
    else:
        # 재귀적으로 분해
        return split_until_base(num-1) + split_until_base(num-2)

for i in range(T):
    N = int(input())
    result = split_until_base(N)
    count_0 = result.count(0)
    count_1 = result.count(1)
    print(count_0, count_1)

완전 탐색(또는 브루트 포스) 방식의 접근법입니다. 완전 탐색의 특징을 잘 보여주고 있습니다:

재귀적 분해: 함수가 자기 자신을 호출하면서 모든 가능한 경우를 탐색합니다.

split_until_base(num)은 num을 완전히 기본 케이스(0과 1)까지 분해합니다.

모든 경우 탐색: 피보나치 수열의 정의에 따라 모든 재귀 호출을 수행합니다.

모든 호출 트리를 따라가면서 피보나치 함수가 실제로 호출되는 패턴을 그대로 따릅니다.

중복 계산: 같은 값에 대한 계산이 여러 번 반복됩니다.

예를 들어 split_until_base(5)는 split_until_base(3)을 여러 번 계산하게 됩니다.

이런 완전 탐색 방식은 작은 입력값에는 잘 작동하지만, 입력값이 커질수록 계산량이 기하급수적으로 증가하는 문제가 있습니다. 피보나치 수열의 경우,
이 방식은 시간 복잡도가 $O(2^{n})$ 으로 매우 비효율적입니다.
문제에서 N은 최대 40까지 가능하다고 했는데, 이 완전 탐색 방식으로는 N이 40인 경우 시간 초과가 발생할 것입니다. DFS 나 완전 탐색으로 풀 수 있는 마지노선은 500만개 정도의 경우의 수입니다. $5 * 10^{6}$ < $2^{40}$ 한눈에 봐도 훨씬 큽니다.
그렇기 때문에 동적 프로그래밍 방식(결과를 저장하고 재사용하는 방식)으로 풀어야 합니다.

정답

T = int(input())

# 각 N에 대한 0과 1의 출력 횟수를 미리 계산
zero_count = [1, 0]  # fibonacci(0)은 0을 1번 출력
one_count = [0, 1]   # fibonacci(1)은 1을 1번 출력

for i in range(2, 41):  # N은 최대 40
    zero_count.append(zero_count[i-1] + zero_count[i-2])
    one_count.append(one_count[i-1] + one_count[i-2])

for _ in range(T):
    N = int(input())
    print(zero_count[N], one_count[N])

동적 프로그래밍이란?

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 나누고, 각 하위 문제의 결과를 저장해두었다가 재사용하는 문제 해결 방법입니다.

1. 동적 프로그래밍의 핵심 아이디어

동적 프로그래밍의 핵심은 두 가지입니다:

하위 문제 분할: 큰 문제를 작은 문제로 나눕니다.
결과 저장 및 재사용: 이미 계산한 작은 문제의 결과를 저장해두고 필요할 때 다시 계산하지 않고 재사용합니다.
예시: 피보나치 수열
피보나치 수열은 동적 프로그래밍을 설명하기 좋은 예시입니다.
일반적인 재귀 방식 (완전 탐색)

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

이 방식의 문제점:

fibonacci(5)를 계산하기 위해 fibonacci(4)와 fibonacci(3)을 계산
fibonacci(4)를 계산하기 위해 fibonacci(3)과 fibonacci(2)를 계산
여기서 fibonacci(3)이 중복 계산됨

이런 중복 계산 때문에 시간 복잡도가 O(2^n)으로, n이 커질수록 계산 시간이 기하급수적으로 증가합니다.

2. 동적 프로그래밍 방식

def fibonacci_dp(n):
    # 결과를 저장할 배열 초기화
    fib = [0, 1]
    
    # 나머지 값 계산
    for i in range(2, n+1):
        fib.append(fib[i-1] + fib[i-2])
    
    return fib[n]

이 방식의 장점:

각 피보나치 수를 딱 한 번만 계산
계산된 결과를 배열에 저장하고 재사용
시간 복잡도가 $O(n)$ 으로 크게 개선됨

3. 피보나치 함수 호출 횟수 문제에 적용

원래 문제로 돌아가서, 피보나치 함수 호출 시 0과 1이 출력되는 횟수를 계산해 봅시다.

초기값 설정

zero_count = [1, 0]  # fibonacci(0)은 0을 1번 출력, fibonacci(1)은 0을 0번 출력
one_count = [0, 1]   # fibonacci(0)은 1을 0번 출력, fibonacci(1)은 1을 1번 출력

점화식 설정
fibonacci(n)은 fibonacci(n-1)과 fibonacci(n-2)를 호출합니다.
따라서:

fibonacci(n)에서 0이 출력되는 횟수 = fibonacci(n-1)에서의 0 출력 횟수 + fibonacci(n-2)에서의 0 출력 횟수
fibonacci(n)에서 1이 출력되는 횟수 = fibonacci(n-1)에서의 1 출력 횟수 + fibonacci(n-2)에서의 1 출력 횟수

반복을 통한 계산

for i in range(2, 41):  # N은 최대 40
    zero_count.append(zero_count[i-1] + zero_count[i-2])
    one_count.append(one_count[i-1] + one_count[i-2])

테스트 케이스마다 결과 출력

for _ in range(T):
    N = int(input())
    print(zero_count[N], one_count[N])

4. 동적 프로그래밍의 특징

최적 부분 구조(Optimal Substructure): 큰 문제의 최적해가 작은 문제의 최적해로부터 구성됩니다.
중복되는 부분 문제(Overlapping Subproblems): 같은 작은 문제가 여러 번 재사용됩니다.

5. 동적 프로그래밍 구현 방식

상향식(Bottom-up): 작은 문제부터 차례대로 해결하며 큰 문제로 확장하는 방식

주로 반복문을 사용
위 코드는 이 방식을 사용

하향식(Top-down): 큰 문제에서 시작해 작은 문제로 나누고, 메모이제이션(결과 저장)을 통해 중복 계산을 방지하는 방식

주로 재귀와 메모이제이션을 사용

6. 메모이제이션 예시 (하향식)

def fibonacci_memoization(n, memo={}):
    # 이미 계산된 값이면 재사용
    if n in memo:
        return memo[n]
    
    # 기본 경우
    if n <= 1:
        memo[n] = n
        return n
    
    # 재귀적으로 계산하고 결과 저장
    memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
    return memo[n]