[코테] 다이나믹 프로그래밍

목차

1. 다이나믹 프로그래밍 개념

- 개념: 큰 문제를 작은 문제로 나누어 해결하고 그 결과를 재사용하는 알고리즘 기법이다.
- 사용 시기: 동일한 계산이 반복될 때 사용한다.
- 특징: 중복 계산을 방지하여 성능을 최적화한다.
- 시간복잡도: 메모이제이션 사용 시 O(N)이다.

- 퀵 정렬 과의 차이점
    - 다이나믹 프로그래밍은 퀵 정렬과 같은 분할 정복과 다음과 같은 차이가 있다:
        - 다이나믹 프로그래밍: 중복되는 부분 문제를 저장하고 재활용한다.
        - 퀵 정렬: 문제를 독립적으로 해결한 후 병합한다.

 

2. 동작 원리 상세 설명

2.1. 피보나치 수열의 재귀 구현 문제점

1. 단순 재귀의 비효율성
단순 재귀로 구현한 피보나치 수열의 코드이다:

def fibo(x):
    # 첫 번째와 두 번째 피보나치 수는 1
    if x == 1 or x == 2:
        return 1
    # x번째 피보나치 수 = (x-1)번째 + (x-2)번째 
    # 문제점: 같은 값을 여러번 계산하게 됨
    return fibo(x - 1) + fibo(x - 2)

이 구현의 문제점은 다음과 같다:

- 동일한 값을 여러 번 반복 계산한다
- 시간복잡도가 O(2^N)으로 매우 비효율적이다
- 깊은 재귀 호출로 스택 메모리가 부족할 수 있다

2. 재귀 호출 트리로 보는 문제점
붉은색으로 표시된 노드들은 중복 계산되는 부분이다. fibo(3)이 총 2번 계산되며, fibo(2)는 총 3번 계산된다. 입력값이 커질수록 이러한 중복 계산은 기하급수적으로 증가한다.

 

2.2 구현 방식

위의 문제는 DP를 통해 해결할 수 있다:

2.2.1 메모이제이션 (하향식)

# 한 번 계산된 결과를 메모리에 저장하여 재활용
d = [0] * 100  # 계산 결과를 저장할 DP 테이블 초기화

def fibo(x):
    # 첫 번째와 두 번째 피보나치 수는 1
    if x == 1 or x == 2:
        return 1
        
    # 이미 계산한 적 있는 문제라면 그대로 반환
    # d[x]가 0이 아니라면 이미 계산했던 값
    if d[x] != 0:
        return d[x]
        
    # 아직 계산하지 않은 문제라면 점화식에 따라 피보나치 계산
    # 계산 결과를 DP 테이블에 저장하고 반환
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

2.2 반복문 (상향식)

# 작은 문제부터 차근차근 답을 도출
d = [0] * 100  # 계산 결과를 저장할 DP 테이블 초기화
d[1] = 1  # 첫 번째 피보나치 수는 1
d[2] = 1  # 두 번째 피보나치 수는 1

# 피보나치 함수 반복문으로 구현
for i in range(3, n + 1):
    # 바로 앞의 두 피보나치 수의 합을 현재 위치에 저장
    # 작은 문제부터 차근차근 해결하여 큰 문제의 답을 구함
    d[i] = d[i - 1] + d[i - 2]

3. 코딩테스트 꿀팁

1. 리스트와 딕셔너리 활용
    - 메모이제이션 구현 시 리스트뿐만 아니라 딕셔너리(dict) 자료형도 사용 가능
    - 딕셔너리는 수열처럼 연속적이지 않은 경우에 유용
    - 예시: ai를 계산하고자 할 때 a(i) - a(j) 모두가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우

2. 코딩 테스트 문제 유형
    - 코딩 테스트에서는 대체로 간단한 형태로 출제
    - 다만 높은 난이도의 문제에서는 다른 알고리즘과의 복합적인 구현이 필요할 수 있음

3. 재귀 함수 사용 시 주의사항
    - 재귀 제한이 있는 경우, sys 라이브러리의 setrecursionlimit() 함수를 사용하여 제한을 완화
    - 재귀적 피보나치 수열의 스택 크기가 한정되어 있을 수 있음을 주의
    - 실제 구현 시에는 가급적 내장 함수나 반복문을 사용하는 것이 안전

4. 문제 해결 접근법
    1. 문제를 푸는 첫 번째 단계는 다이나믹 프로그래밍 유형임을 파악
    2. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 오래 걸린다면 다이나믹 프로그래밍을 적용
    3. 일단 완전 탐색으로 접근 후, 중복되는 부분을 찾아 메모이제이션 적용을 고려