📔 이.코.테 Part2. 다이나믹 프로그래밍(DP) 정리노트

Chap8. 다이나믹 프로그래밍(Dynamic Programming)

본 포스팅은 나동빈 저자의 '이것이 취업을 위한 코딩테스트다'를 공부하며 정리한 노트입니다.

한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

Intro

Question - 컴퓨터로도 해결하기 어려운 문제에는 무엇이 있을까요?

• 우리는 컴퓨터로 대부분의 문제를 해결할 수 있지만 컴퓨터로 해결하기 어려운 문제도 존재합니다
• 최적의 해를 구하기에 시간이 매우 많이 필요한 문제나 메모리 공간이 많이 필요한 문제 등이 있습니다

이렇게 제한된 자원을 최대한 효율적으로 활용할 수 있는 알고리즘이 필요합니다

이번 시간에 배울 다이나믹 프로그래밍(Dynamic Programing 또는 동적 계획법)이란 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법입니다

이번 시간에는 다음의 것들을 배우게 됩니다

• 다이나믹 프로그램 개요
• 탑다운 바텀업
• 메모이제이션(Memoization)

다이나믹 프로그래밍에 대해 알아보기 전에 기존의 알고리즘으로 해결하기 어려운 문제 중에서 다이나믹프로그래밍으로 해결할 수 있는 문제를 살펴보도록 하겠습니다

# 8-1.py 피보나치 함수 소스코드

def fibo(x):
    if x == 1 or x == 2:
        return 1
    else:
        return fibo(x-1) + fibo(x-2)

print(fibo(4))

 

피보나치 수열의 시간 복잡도 분석해보겠습니다

• 피보나치 수열의 시간복잡도는 매우 높습니다
  • 매우, 매우!!
  • 빅오 표기법으로 표현하면 O(2**N)의 지수 시간이 소요됩니다
    • e.g. 가령 n이 30이면 10억 가량의 연산을 수행해야 합니다
• 이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없습니다
• 문제를 다이나믹 프로그래밍을 사용해서 효율적으로 해결해보도록 하겠습니다

 

피보나치 수열의 효율적인 해법

다이나믹 프로그래밍의 사용조건을 만족하는지 확인합니다

1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있습니다
2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결합니다

• 피보나치 수열은 다이나믹 프로그래밍의 사용 조건을 만족하는 대표적인 문제입니다
• 문제를 Memoization(메모이제이션) 기법을 사용해서 해결해보도록 하겠습니다

 

1. 메모이제이션 (Memoization)

• 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나입니다
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법입니다
  • 같은 정보를 다시 호출하면 메모했던 결과를 그대로 가져옵니다
  • 값을 기억해둔다는 점에서 캐싱(caching)라고 합니다

'한 번 계산한 결과를 메모리 공간에 기록했다가 필요할 때 가져오자'

'다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오자'는 아이디어입니다

단순히 코드를 따라치기 보다는 '다이나믹 프로그래밍'과 '재귀함수'의 원리를 떠올리며 코드로 표현해보도록 하겠습니다

# 8-2.py 피보나치 수열 소스코드(재귀적)
"""
1. 한 번 계산된 결과를 메모이제이션(caching)하기 위한 리스트 초기화
2. 피보나치 함수를 재귀함수로 구현
    - 단순히 매번 계산하도록 문제를 풀기 보다는
    - 한 번 구현한 정보를 리스트에 저장하는 것이다(caching)
    * 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 리스트로 부터 가져오면 된다
"""

# Memoization, 리스트 초기화
# d = [0] * 100
d = [0 for i in range(100)]

# Fibonacci Function을 재귀함수로 구현
def fibo(x):
    # 종료조건: x가 1 또는 2라면 1을 반환
    if x == 1 or x == 2:
        return 1
    # 이미 한 번 계산한 적이 있었다면 값을 반환한다
    if d[x] != 0:
        return d[x]
    else:
        d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(99))

218922995834555169026

다이나믹 프로그래밍이란 큰 문제를 작게 나누고,
같은 문제라면 한 번씩만 풀어서 문제를 효율적으로 해결하는 알고리즘 기법이다

Question. 다이나믹 프로그래밍을 적용한 피보나치 수열 알고리즘의 시간 복잡도는 어떻게 될까?
Answer. O(N)이다.

왜 시간의 복잡도가 O(N)인지 생각해보면 좋을 것 같습니다 -21.01.12.Tue-

# 8-3.py 호출되는 함수 확인
d = [0] * 100

def pibo(x):
    print('f(' + str(x) + ')', end=' ')
    if x == 1 or x ==2:
        return 1
    if d[x] != 0:
        return d[x]
    # return pibo(x-2) + pibo(x-1)
    d[x] = pibo(x-1) + pibo(x-2)
    return d[x]

pibo(6)

f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

8

Top-down 방식

• 이처럼 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식을 탑다운(Top-Down)방식이라고 한다.
• 반면에 작은 문제부터 차근차근 답을 도출하는 방식을 보텀업(Bottom-Up)방식이라고 말한다

2. 탑다운 vs 보텀업

작은 문제부터 해결해서 큰 문제를 해결할 것인가.
큰 문제부터 해결해서 작은 문제를 해결해 나갈 것인가

• 탑다운 방식(Memoization)은 하향식이라고 하며 보텀업 방식은 상향식이라고 한다
• 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다
  • 결과 저장용 리스트는 DP 테이블이라고 부른다
• 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미한다

# 8-4.py 피보나치 수열 소스코드(반복적)

"""
Botton-Up 방식
"작은 문제부터 차근차근 답을 도출해 나간다"
"""

# DP 테이블 초기화(보텀업 방식에서 사용되는 결과 저장용 리스트)
d = [0 for i in range(100)]

# 피보나치 수열 초기화
d[1] = 1
d[2] = 1


def fibo(x):
    for i in range(3, x+1):
        d[i] = d[i-1] + d[i-2]

    return d[x]

print(fibo(99))​

218922995834555169026

---

DP 정리

• 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식입니다
• 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라 부릅니다
• 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현입니다

---

문제를 대하는 방법

1. 주어진 문제가 다이나믹 프로그래밍 유형인지 파악합니다
2. 특정한 문제를 완전탐색으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 확인합니다
   • 중복되는 부분문제들이 있는지 확인하는게 중요합니다
3. 일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어가 됩니다
4. 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장합니다

✅ 피보나치 수열을 다시 한번 구현하면서 주요 개념을 익혀보자
✅ 실전 문제를 통해 DP 유형의 문제를 파악해보자!

• Reviewed it! -21.01.12.Tue- pm12:30

Steve-YJ/Python-Algorithm