본문으로 건너뛰기

1. 재귀를 통한 문제 해결​

1.1 재귀의 개념과 구조​

  • 재귀는 문제를 동일한 형태의 작은 문제로 나누어 해결하는 방식입니다
  • 재귀 함수는 자기 자신을 호출하여 문제를 해결합니다

1.2 재귀의 핵심 요소​

  • 재귀의 핵심 요소는 종료 조건(Base Case)과 재귀 호출(Recursive Case)입니다

1.2.1 종료 조건 예제​

def factorial(n):
    # 종료 조건
    if n <= 1:
        return 1
    # 재귀 호출
    return n * factorial(n-1)
  • 재귀 호출이 끝나는 시점을 명확히 정의해야 합니다
  • 종료 조건이 없으면 무한 재귀에 빠질 수 있습니다

1.2.2 재귀 호출 특징​

  • 문제를 더 작은 단위로 나누어 자신을 다시 호출합니다
  • 각 호출마다 문제의 크기가 감소해야 합니다

1.3 재귀로 피보나치 수열 구현하고 문제점 분석​

1.3.1 기본 재귀 구현​

def fibonacci(n):
    # 종료 조건
    if n <= 1:
        return n
        
    # 재귀 호출
    return fibonacci(n-1) + fibonacci(n-2)
  • 시간 복잡도: O(2ⁿ)
  • 중복된 계산이 많아 성능이 떨어집니다
    • 예) fibonacci(3) = fibonacci(2) + fibonacci(1) = fibonacci(1) + fibonacci(0) + fibonacci(1)
    • fibonacci(1)이 중복 호출됩니다
  • 메모리 문제
    • 재귀 호출마다 스택 프레임이 쌓임
    • 깊은 재귀의 경우 스택 오버플로우 발생 가능
    • 각 호출마다 지역 변수와 반환 주소가 스택에 저장됨

2. 다이나믹 프로그래밍의 등장​

2.1 DP가 필요한 이유​

  • 재귀의 치명적인 문제: 중복 계산
  • DP의 핵심 아이디어: 계산 결과 재사용
  • 한 번 계산한 결과를 저장하고 재활용하여 중복 계산을 방지합니다

2.2 DP가 적용 가능한 문제의 특징​

  1. 최적 부분 구조(Optimal Substructure)
    • 큰 문제의 최적해가 작은 문제의 최적해로 구성됨
    • 간단히 말하면 점화식을 세울 수 있다면 Optimal Substructure를 가진다고 할 수 있습니다
    • 피보나치 예시: F(n) = F(n-1) + F(n-2)
  2. 중복되는 부분 문제(Overlapping Subproblem)
    • 동일한 작은 문제들이 반복해서 나타남
    • 피보나치 예시: F(3)이 F(5), F(4) 계산시 중복 등장
    • 이항 계수 계산: nCr = n-1Cr + n-1Cr-1에서 여러 항의 계산이 중복됨

3. DP의 구현 방식​

  • DP는 크게 하향식(Top-down)과 상향식(Bottom-up) 방식으로 구현할 수 있습니다
  • 메모이제이션(Memoization): 하향식 방식으로 구현하는 기법
    • 이미 계산한 값을 저장해두고 재활용하는 기법
  • 타뷸레이션(Tabulation): 상향식 방식으로 구현하는 기법
    • 작은 문제부터 차례대로 해결해 나가는 기법

3.1 하향식(Top-down) - 메모이제이션​

  • 메모이제이션(Memoization): 계산 결과를 저장해두고 재활용하는 기법
  • 재귀 호출을 사용하며 중복 계산을 피합니다
  • 이미 계산한 값은 저장해두고 필요할 때 꺼내 사용합니다

3.1.1 메모이제이션 구현​

def fibonacci_memoization(n, memo=None):
    if memo is None:
        memo = {}
        
    # 이미 계산된 값이면 반환
    if n in memo:
        return memo[n]
        
    # 종료 조건
    if n <= 1:
        return n
        
    # 계산 결과를 메모에 저장
    memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
    return memo[n]

3.1.2 메모이제이션 장단점​

  • 장점

    • 필요한 부분만 계산합니다
    • 직관적이고 재귀적 구조를 그대로 유지합니다
    • 모든 상태를 계산할 필요가 없습니다

  • 단점

    • 재귀 호출 스택을 사용하므로 깊이가 깊어지면 스택 오버플로우가 발생할 수 있습니다
    • 함수 호출 오버헤드가 있습니다

3.2 상향식(Bottom-up) - 타뷸레이션​

  • 타뷸레이션(Tabulation): 작은 문제부터 차례대로 해결해 나갑니다
  • 반복문을 사용하며 중복 계산을 피합니다
  • 작은 문제부터 순차적으로 해결하므로 최종 답을 구할 수 있습니다
  • 메모이제이션과 달리 재귀 호출이 없어 스택 오버플로우 위험이 없습니다

3.2.1 타뷸레이션 구현​

def fibonacci_tabulation(n):
    # 테이블 초기화
    dp = [0] * (n + 1)
    dp[1] = 1
    
    # 작은 문제부터 순차적으로 해결
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

3.2.2 타뷸레이션 장단점​

  • 장점

    • 재귀 호출이 없어 스택 오버플로우 위험이 없습니다
    • 캐시 지역성이 좋아 실행 속도가 더 빠릅니다
    • 반복문을 사용하므로 예측 가능한 성능을 보입니다
    • 메모리 사용량을 쉽게 예측할 수 있습니다

  • 단점

    • 모든 부분 문제를 계산해야 합니다
    • 때로는 불필요한 상태까지 계산할 수 있습니다
    • 점화식을 직관적으로 세우기 어려울 수 있습니다

3.3 공간 최적화 버전​

3.3.1 최적화된 구현​

def fibonacci_space_optimized(n):
    if n <= 1:
        return n
        
    prev2, prev1 = 0, 1
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
        
    return prev1
  • 시간 복잡도: O(n)
  • 공간 복잡도: O(1)

4. DP 문제 해결 전략​

4.1 문제 해결 단계​

  1. DP 적용 가능성 확인
    • 최적 부분 구조 존재 여부
    • 중복되는 부분 문제 존재 여부
  2. 상태 정의
    • 문제를 작은 부분으로 나누었을 때 어떤 상태가 필요한지
    • 예: fibonacci(n)에서 n이 상태
  3. 점화식 수립
    • 현재 상태와 이전 상태의 관계 정의
    • 예: dp[i] = dp[i-1] + dp[i-2]
  4. 구현 방식 선택
    • 메모이제이션(Top-down)
    • 타뷸레이션(Bottom-up)

5. 다른 알고리즘과 차이점​

5.1 Greedy Algorithm과 차이점​

  • Greedy Algorithm은 그 순간에 최적이라고 생각되는 것을 선택하면서 풀이합니다
  • Dynamic Programming은 중복된 하위 문제들(Overlapping Subproblem)의 결과를 저장해뒀다가 풀이해 나갑니다

5.2 분할 정복과 차이점​

  • 분할 정복은 DP와 마찬가지로 최적 부분 구조를 가지는 공통점이 있으나 하위 문제가 반복되지 않습니다

5.3 알고리즘 비교 표​

알고리즘풀이 가능한 문제의 특징풀이 가능한 문제 및 알고리즘
다이나믹 프로그래밍최적 부분 구조
중복된 하위 문제		0-1 배낭 문제
피보나치 수열
다익스트라 알고리즘
그리디 알고리즘최적 부분 구조
탐욕 선택 속성		분할 가능 배낭 문제
다익스트라 알고리즘
분할 정복최적 부분 구조병합 정렬
퀵 정렬