99클럽 코테 스터디 21일차 TIL + 동적계획법(DP)

오늘의 문제 - 동적계획법(DP)

프로그래머스 - 피보나치 수

https://school.programmers.co.kr/learn/courses/30/lessons/12945

---

내 풀이 및 접근 방식

def solution(n):
    answer = 0
    d= [0] * 100001
    
    d[0] = 0
    d[1] = 1
    
    for i in range(2, n+1):
        d[i] = d[i-1] + d[i-2]
        
    answer = d[n] % 1234567
    
    
    return answer

 

풀이

1. 각 단계의 피보나치 수열의 값을 저장하기 위해 d를 초기화한다.
2. 반복문을 이용하여 피보나치 수열 점화식 f(n) = f(n-1) + f(n-2)을 따라 2부터 n까지의 값을 계산하여 d에 저장한다.
3. n의 피보나치 수 d[n]을 1234567로 나눈 나머지를 결과로 반환한다.

시간 복잡도

• 배열을 초기화하는 작업은 O(1), for 루프는 O(n)이다.
• for문을 돌 때 각 i에 대해서 점화식에 따른 계산은 O(1)이다. 

따라서, 시간복잡도는 O(n)이다.

 

공간복잡도 최적화

메모리를 초기화하지 않고도, 2개의 변수만을 사용하여 위 코드를 최적화할 수 있다. 값을 저장하지 않고 각 단계에서 현재 값을 갱신하는 방식이다. 위 코드와 시간 복잡도는 같지만 공간복잡도가 작다.

def solution(n):
    
    prev2 = 0
    prev1 = 1
    
    for i in range(2, n + 1):
        current = (prev1 + prev2) % 1234567
        prev2 = prev1
        prev1 = current
    
    return prev1

 

재귀 사용 풀이

재귀를 사용한 풀이는 아래와 같다.

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

 

재귀적 접근의 시간 복잡도는 O(2^n)이다. 각 호출마다 2개의 재귀 호출을 수행하며 각각 다시 2개의 호출을 수행하는 형태이기 때문이다. f(n)을 계산하기 위해  f(n-1)과 f(n-2)를 계산해야하고 이 2개의 계산이 또 다시 f(n-2)와 f(n-3) 등을 재귀적으로 호출하게 된다. 이로 인해 같은 하위 문제가 여러 번 반복되어 계산된다. 결과적으로 재귀 호출의 수가 급격히 증가하면서 시간 복잡도가 지수적으로 증가한다.

 

재귀 사용 풀이는 간단하고 직관적일 수 있으나, 중복 계산 문제, 시간 복잡도, 호출 스택 증가 등으로 인한 O(n)의 공간 복잡도 측면에서 DP를 사용한 풀이보다 비효율적이다.

---

회고

 

동적계획법(DP)

동적계획법이란 복잡한 문제를 간단한 하위 문제로 나누어 해결하는 알고리즘 기법이다. 이 기법은 중복된 계산을 피하고, 문제를 효율적으로 해결하기 위해 부분 문제의 결과를 저장하여 재사용한다.

• 핵심 개념
  • 최적 부분 구조 (Optimal Substructure): 큰 문제를 작은 문제로 나누어 해결할 수 있는 문제 구조를 의미한다. 즉, 문제를 부분 문제로 쪼개어 각 부분 문제의 최적해를 통해 원래 문제의 최적해를 구할 수 있는 경우이다.
  • 중복되는 부분 문제 (Overlapping Subproblems): 재귀적으로 문제를 해결할 때 동일한 하위 문제가 여러 번 반복해서 계산되는 문제다. 동적 계획법은 이러한 중복된 계산을 피하기 위해 부분 문제의 결과를 저장해두고, 필요할 때 재사용한다.
  • 메모이제이션(Memoization): 계산한 부분 문제의 결과를 저장해두고, 동일한 부분 문제가 다시 나타날 때 저장된 값을 사용하는 기술입니다. 메모이제이션은 재귀적 방식과 함께 사용되며, 반복적인 계산을 피하는 데 중요한 역할을 한다.
  • 탑다운(TOP-DOWN)과 바텀업(BOTTOM-UP):
    • 탑다운(TOP-DOWN): 재귀적으로 큰 문제를 풀다가 작은 부분 문제로 나누어가며 해결하는 방식. 이 과정에서 메모이제이션을 활용해 계산된 값을 저장한다.
    • 바텀업(BOTTOM-UP): 작은 부분 문제부터 시작하여 큰 문제를 해결하는 방식. 반복문을 통해 문제를 해결하며, 메모이제이션 없이도 중복 계산을 피할 수 있다.
• 사용 사례
  • 피보나치 수열 문제: 피보나치 수열의 n번째 수를 계산하기
  • 최대 부분 배열 합 (Maximum Subarray Sum, Kadane’s Algorithm): 배열에서 연속된 부분 배열의 합 중 가장 큰 값을 찾는 문제. 이 문제는 DP를 사용하여 각 위치에서의 최대 부분 배열 합을 계산해 나가는 방식으로 해결한다.
  • 배낭 문제 (Knapsack Problem): 제한된 용량의 배낭에 최대 가치를 가지도록 물건을 담는 문제. DP를 사용하여 각 물건을 선택할 때마다 최적의 값을 계산하고, 이를 기반으로 최종 결과를 도출한다.
  • 최단 경로 문제: 특정 지점에서 다른 지점까지의 최단 경로를 찾는 문제. 다익스트라(Dijkstra) 알고리즘이나 플로이드-와샬(Floyd-Warshall) 알고리즘 등에서 DP가 활용된다.
  • LIS(최장 증가 부분 수열): 주어진 수열에서 부분 수열 중 증가하는 부분의 길이가 가장 긴 부분 수열을 찾는 문제. DP를 사용하여 각 원소를 기준으로 이전 원소들의 최장 증가 부분 수열을 계산해 나간다.