[이코테 자료구조] 6. 다이나믹 프로그래밍

다이나믹 프로그래밍

by 나동빈님

링크 : https://www.youtube.com/watch?v=5Lu34WIx2Us&t=144s

 

• 메모리를 적절히 사용해서 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하는 것을 방지
• 두 가지 방식(탑다운, 바텀업)으로 구성
• 동적 계획법이라고도 부른다
• 다이나믹 프로그래밍의 '다이나믹'은 큰 의미 없이 사용된 단어

 

 

조건

• 문제가 다음의 조건을 만족 할 때 사용할 수 있다
  1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 때
  2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 할 때

피보나치 수열의 모든 가능성을 계산하려면 굉장히 많은 연산과정을 필요로 한다

​ ex) 30번째 피보나치 연산을 위해 약 10억가량의 연산을 수행해야 함

 

 

하향식 방법

• Top-Down 방식

 

- 메모이제이션

​ 한 번 계산한 결과를 메모리 공간에 메모하는 방법

• 같은 문제를 호출하면 메모했던 결과를 그대로 가져온다
• 값을 기록해 놓는다는 점에서 캐싱이라고도 한다

 

리스트의 크기를 설정하고 초기화 시키는 방식은 메모이제이션에 해당

# 탑다운 방식 : 큰 문제 → 작은 문제

# 한 번 계산된 결과를 메모이제이션하기 위한 DP 리스트 초기화
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건(1 혹은 2일 때)
    if x==1 or x==2:
        return 1
    # 이미 계산한적 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
    # 아직 계산하지 않은 문제라면 점화식에 따라 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(99))

# 바텀업 방식 : 작은 문제 → 큰 문제

# 계산된 결과를 저장하기 위해 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수 설정
d[1] = 1
d[2] = 1
n = 99

# 피보나치 반복문으로 구현(바텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[n])

메모이제이션을 이용하는 경우 피보나치 수열의 시간복잡도는 O(N)에 해당한다.

​ cf. 다이나믹 프로그래밍을 이용하지 않을 때의 시간복잡도 : O(2**N)

 

 

- 다이나믹 프로그래밍 vs 분할 정복

• 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분구조를 가질 때 사용
• 큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
• 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복
  • 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다
  • 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다

 

※ 분할 정복의 대표 예시 : 퀵 정렬

• 한 번 기준 원소가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않는다
• 분할 이후에 해당 피벗을 다시 처리하는 부분 문제는 호출하지 않는다

 

 

다이나믹 프로그래밍 문제에 접근하는 방법

• 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요
• 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있다
  • 다른 알고리즘으로 풀이 방법이 떠오르지 않을 때 다이나믹 프로그래밍을 고려하자

1.  일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 
2.  작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있다면
3.  다이나믹 프로그래밍으로 코드를 개선하는 방법을 사용할 수 있다

• 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다

 

※ 예시 문제 : [개미 전사, 1로 만들기, 효율적인 화폐 구성, 금광, 병사 배치하기]

• d = [0] * n 과 같이 DP 리스트를 만들 때, n의 값은 문제의 조건을 참고한다 (가능한 모든 경우의 범위)
• 함수가 호출되는 과정을 트리구조 그림으로 그려보면서 '최적 부분 구조'와 '중복되는 부분 문제'를 만족하는지 확인해볼 것
  • 작은 값의 결합으로 큰 값을 구할 수 있는 지
  • 동일한 값이 여러번 계산되는 지
• 가장 긴 증가하는 부분수열 (Longest Increasing Subsequencem ; LIS) 문제는 다이나믹 프로그래밍 유형에 해당