[알고리즘] 다이나믹 프로그래밍(동적 계획법) - 1

공부 : 동빈나 유튜브 < (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍 >
         + 책 < 이것이 취업을 위한 코딩테스트다 >

 

 

다이나믹 프로그래밍

 

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

- 구현은 일반적으로 Top-Down(하향식)/Bottom-Up(상향식)으로 구성된다.

- Top-Down은 재귀로 / Bottom-Up은 반복문으로 구현 가능

- 다이나믹 프로그래밍의 전형적인 형태는 Bottom-Up 방식

  결과 저장용 리스트는 DP 테이블이라고 부른다.

- 다이나믹은 자료구조의 동적과 다르게 별다른 의미 없이 사용된 단어

자료구조에서 동적 할당(Dynamic Allocation)

: 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법

 

Top-Down(하향식)

: 큰 문제를 해결하기 위해 작은 문제를 호출

 

Bottom-Up(상향식)

: 작은 문제부터 차근차근 답을 도출

 

메모이제이션(Memoization)

 

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

- 다이나믹 프로그래밍을 구현하는 방법 중 하나이지만 다이나믹 프로그래밍에 국한된 개념은 아님

- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다

- 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.

- Top-down 방식

 

 

다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용 가능

 

1. 최적 부분 구조(Optimal Substructure)

   큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

2. 중복되는 부분 문제(Overlapping Subproblem)

   동일한 작은 문제를 반복적으로 해결해야 한다.

 

ex) 피보나치 수열

- 프로그래밍에서는 수열을 배열이나 리스트를 이용해 표현할 수 있다.

 

만약 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 된다. -- O(2**N)

(불필요하게 함수가 여러 번 호출됨 - 중복 부분 문제)

 

#피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

 

탑다운 다이나믹 프로그래밍 코드 ( 재귀함수 ) -- O(N)

 

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

#피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)

def fibo(x):
    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])

 

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

 

가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는 지 검토 후

다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려

- 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤 (탑다운) 작은 문제에서 구한 답이

큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있음

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

 

또한 가능하다면 재귀함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장

- 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문.

 

 

---

 

다이나믹 프로그래밍 VS 분할 정복(Divide-and-Conquer) 

 

모두 최적 부분 구조를 가질 때 사용

- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황

 

하지만 다이나믹 프로그래밍과 분할정복의 차이점은 부분 문제의 중복

- 다이나밍 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.

- 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

 

분할 정복 -- 퀵 정렬 예시

한 번 기준 원소가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않는다.

분할 이후에 해당 원소를 다시 처리하는 부분 문제는 호출하지 않는다.

 

---

실전문제 - 1로 만들기 😨

 

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 4가지

1. X가 5로 나누어 떨어지면 5로 나눈다.

2. X가 3로 나누어 떨어지면 3로 나눈다.

3. X가 2로 나누어 떨어지면 2로 나눈다.

4. X에서 1을 뺀다.

 

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다.

연산을 사용하는 횟수의 최솟값 출력

 

입력 예시	출력 예시
26	3

 

답안 예시  :  동빈나 정답 코드 github 주소

 

Top-Down으로 생각하다가 어려워서 풀이 확인 결과 답안 예시는 Bottom-Up 방식으로 풀었다.

내가 이해한 바로는 2부터 입력 값 X 까지의 모든 숫자의 연산을 사용한 횟수의 최솟값을 계산한다.

마지막으로 X의 최솟값을 구한 후 출력

최솟값을 구하는 방법은 각 조건을 만족할 때 구해지는 횟수의 최솟값을 계산해 테이블에 넣는다.

 

 

실전문제 - 개미전사

 

개미전사가 메뚜기 마을의 식량창고를 공격한다.

식량창고는 일직선으로 이어져있고 서로 인접한 식량창고가 공격 받으면 메뚜기 정찰병이 알아챌 수 있다.

개미 전사가 메뚜기 정찰병에게 들키지 않고 얻을 수 있는 식량의 최댓값 구하기

 

입력 예시	출력 예시
4 1 3 1 5	8
7 1 8 9 1 4 5 6	20

 

직접 작성한 코드

--> i-1번째 창고는 들키기 때문에 i-2번째 또는 i-3번째 중 음식을 많이 털고 있는 음식 개수를 더해준다.

 

N = int(input()) #(3<=N<=100)
warehouse = list(map(int, input().split()))

food_list = [0]*N

food_list[0] = warehouse[0]
food_list[1] = warehouse[1]
food_list[2] = warehouse[2] + warehouse[0]

#1 8 9 1 4 5 6 --> 20
for i in range(3, N):
    food_list[i] = max(warehouse[i] + food_list[i-2], warehouse[i] + food_list[i-3])

print(food_list)
print(food_list[N-1])

 

 

답안 예시  :  동빈나 정답 코드 github 주소

--> i-1의 값, i-2번째 창고와 현재 창고의 식량값 더해준 것 중 max값 가져오기

--> 코드가 간결하고 조금 더 직관적인 느낌