2 분 소요

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

📚 다이나믹 프로그래밍


다이나믹 프로그래밍이란 ?

큰 문제를 작은 문제로 나누어 해결하는 것이다.

계산 했던 것은 계산하지 않겠다!!


예) 사람은 피보나치 수열을 계산할 때 5번째 항을 구하기 위해

1 1 2 3 5 를 뚝딱 금방 생각 할 수 있다.. 물론 숫자가 작을때

우리는 효율적으로 5번째 항을 구하기 위해 3번과 4번 항만을 더하여 계산한다

하지만 컴퓨터는 5번째항을 구하기위해 3번과 4번항을 구하고, 3번을 구하기위해 1번과 2번항을

4번항을 위해 3번항과 2번항을, 4번항의 3번항을 구하기위해 2번항과 1번항을 4번항의 2번항…….

논리의 흐름에 맞춰 이미 했던 계산임에도 불구하고 반복해서 계산을 한다.


[피보나치 수열을 계산 과정]

피보나치

컴퓨터에 재귀적으로 피보나치 코드를 짠다면 다음과 같은 그래프의 모양으로 연산이 이루어질 것이다.

하지만 사람은 자연스럽게 우리가 이미 한 연산을 반복하지 않는다.

다이나믹 프로그래밍 프로그램이 빨간색선의 과정을 구현하는 것이라고 생각한다.


📌 다이나믹 프로그래밍 사용 조건


  1. 큰 문제를 작은 문제로 나눌 수 있다.

  2. 작은 문제가 반복하여 일어나야한다.

  3. 작은 문제의 답이 항상 동일하게 나와야한다.


📌 다이나믹 프로그래밍 구현방식?


  1. Top-Down방식 큰 문제를 해결하기위해 작은 문제들을 호출하는 방식이다.

    위에서 아래로 연산해 나아가는 방식이다.(메모이제이션기법이 사용됌.)

  2. Bottom-Up방식 우리가 머릿속으로 피보나치 수열을 계산하기 자연스럽게 첫항에서 부터 계산해

    나아간다. 이와 같이 아래에서 위로 연산해 나아가는 방식이다.



메모이제이션 (memoization)

메모이제이션 이란?

동적 프로그래밍에서 작은 문제들이 반복이되고 이에 대한 결과값이 동일할 때,

그 값을 저장해놓는 기법을 의미한다. (Top - Down 방식에 사용)



예시(피보나치수열)

1. 재귀함수를 활용한 피보나치수열 구현

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

»output

8

시간 복잡도(일반적으로): O($2^N$)

엄청난 속도로 복잡도가 상승하게 될것이다.


2. Top-Down 방식의 피보나치수열 구현

memo = [0]*10 #메모이제이션을 위해 DP테이블을 만듬.

def fibo(n):
    if n==1 or n==2:
        return 1
    
    if memo[n]!=0:     #메모이제이션값에 기록이 되어 있다면 ? 그냥 바로 그걸 꺼내줌.
        return memo[n]
    
    memo[n] = fibo(n-1) + fibo(n-2)
    return memo[n]
fibo(5)

»output

8

시간 복잡도: O(N)

원리

  1. 피보나치가 수열의 형태임으로 각각의 값을 저장할 수 있는 list를 만든다.(메모이제이션을 위한 DP테이블 생성)
  2. 모든 결과값을 DP테이블에 저장을 한다.
  3. 만약 DP테이블 원하는 결과값이 있으면 재귀함수를 호출하는 것이 아닌 DP에 저장된 값을 return 해준다.


3. Bottom-Up 방식의 피보나치수열 구현

d = [0]*10

d[1] = 1
d[2] = 2

n=5

for i in range(3,n+1):
    d[i] = d[i-1]+d[i-2]
    
print(d[i])

»output

8

시간 복잡도: O(N)

원리

  1. 점화식의 초기값을 DP테이블에 할당시켜놓는다.
  2. 점화식을 만들고 반복구문으로 실행시켜준다.


🔥동적 프로그래밍 연습문제

DP식을 세우는 고민을 하게 해 줄 문제들 모음

  1. [백준] 11722번: 가장 ~~ 수열
  2. [백준] 15486번: 퇴사 2
  3. [백준] 1520번: 내리막길
  4. [백준] 11066번: 파일 합치기
  5. [백준] 11049번: 행렬 곱셈 순서
  6. [백준] 9252번: LCS 2

DP에 대해서 어느정도 익숙해진 사람들을 위한 많은 사람들이 푼 검증된 좋은 문제들 모음

  1. [백준] 1562번: 계단수
  2. [백준] 11570번: 환상의 듀엣
  3. [백준] 2618번: 경찰차
  4. [백준] 6989번: 채점
  5. [백준] 2315번: 가로등 끄기
  6. [백준] 1126번: 같은 탑
  7. [백준] 1315번: RPG
  8. [백준] 2419번: 사수아탕
  9. [백준] 12766번: 지사배정
  10. [백준] 5466번: 상인

수학적인 활용도가 높은 DP문제들

  1. [백준] 2749번: 피보나치수 3
  2. [백준] 14578번: 영훈이의 색칠공부
  3. [백준] 15588번: stamp painting
  4. [백준] 2392번: 다각형의 분할
  5. [백준] 2862번: 수학 게임
  6. [백준] 15902번: split and merge

돌이 코딩하는 방님의 추천목록을 참고하여 만들었습니다.(출처 아래)

출처/참고

이것이 코딩 테스트다 - 나동빈 저

돌이 코딩하는 방

감사합니다🙇‍♂️

댓글남기기

참고