[알고리즘 + Python] DP(Dymanic Programming, 다이나믹 프로그래밍)

728x90

 

해당 게시물은 동빈나님 유튜브 "(이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍"을 보고 학습용으로 기록한 것입니다.

 

DP 사용조건

다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다.

1. 최적 부분 구조(Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있다.
2. 중복되는 부분 문제(Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결한다.

 

DP 예시

대표적인 문제로는 피보나치 수열이 있다.

(cf. 점화식: 인접항들의 관계식을 의미한다.)

// 피보나치 수열
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

 

* 피보나치 수열의 점화식

 

이미지 출처: https://velog.io/@doodung/Algorithm-DP

 

재귀함수를 통해서 점화식을 소스코드로 구현할 수 있다.

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

 

단순 재귀를 통한 피보나치 수열 구현(X)

* [Python] 단순 재귀를 통한 피보나치 수열

 

# 피보나치 함수를 재귀함수로 구현
def fibo(x):
	if x == 1 or x == 2:
    	return 1
    return fibo(x-1) + fibo(x-2)
    
print(fibo(4))  # 3

 

* [Java] 단순 재귀를 통한 피보나치 수열

 

import java.util.*;

public class Main {
	// 피보나치 함수를 재귀함수로 구현
    public static int fibo(int x) {
    	if(x == 1 || x == 2) {
        	return 1;
        }
        return fibo(x - 1) + fibo(x - 2);
    }
    
    public static void main(String[] args) {
    	System.out.println(fibo(4));  // 3
    }
}

 

단순 재귀함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 된다.

아래 이미지와 같이 f(2)가 중복 호출되는 문제가 발생한다.

(cf. 빅오표기법 기준으로 f(30)을 계산하기 위해 약 10억 가량 연산을 수행해야한다.)

 

이미지 출처: https://velog.io/@doodung/Algorithm-DP

 

DP 구현방식과 DP를 통한 피보나치 수열 구현

• DP는 메모이제이션(탑다운, 하향식)과 상향식(또는 바텀업)으로 구현할 수 있다.
• DP의 전형적인 형태는 바텀업 방식이다.
  • 결과 저장용 리스트는 DP 테이블이라고 부른다.

• 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해놓는 넓은 개념이다.
  • 따라서 메모이제이션은 DP에 국한된 개념은 아니다.
  • 한 번 계산된 결과를 담아놓기만 하고 DP를 위해 활용하지 않을 수도 있다.

• 피보나치 수열은 DP 사용 조건을 만족한다.

 

* 메모이제이션(Memoization) - 하향식(Top Down) 방식

• 메모이제이션은 DP를 구현하는 방법 중 하나이다.
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.
  • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
  • 값을 기록해놓는다는 점에서 캐싱(Caching)이라고도 한다.

 

* [Python] 탑다운 DP

 

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

# 피보나치 함수를 재귀함수로 구현(탑다운 DP)
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))  # 218922995834555169026

 

* [Python] 바텀업 DP

 

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

# 첫번째 피보나치 수와 두번째 피보나치 수는 1
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])  # 218922995834555169026

 

* [Java] 바텀업 DP

 

import java.util.*;

public class Main {
	public static long[] d = new long[100];
        public static void main(String[] args) {
            // 첫번째 피보나치 수와 두번째 피보나치 수는 1
            d[1] = 1;
            d[2] = 1;
            int n = 50; // 50번째 피보나치 수를 계산

            // 피보나치 함수 반복문으로 구현(바텀업 다이나믹 프로그래밍)
            for(int i=3; i<=n; i++) {
                d[i] = d[i-1] + d[i-2];
            }
            System.out.println(d[n]);  // 12586269025
        }
}

 

DP vs 분할정복

• DP와 분할정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
  • 즉, 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황

• DP와 분할정복의 차이점은 부분 문제의 중복이다.
  • DP 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
  • 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

 

DP 문제 접근방법

• 주어진 문제가 DP 유형임을  파악하는 것이 중요하다.
• 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있다.
  • 다른 알고리즘으로 풀이방법이 떠오르지 않는다면 DP를 고려해보자.
• 일단 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선하는 방법을 사용할 수 있다.
• 일반적인 코테 수준에서는 기본 유형의 DP 문제가 출제되는 경우가 많다.

---

 

개미전사: 문제설명

개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져있다.

각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.

이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다.

따라서 개미전사가 정찰병에게 들키지않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야한다. 

 

개미전사: 문제해결 아이디어

• 예시를 확인해 보자. N = 4일때, 다음과 같은 경우들이 존재할 수 있다.
  • 식량을 선택할 수 있는 경우의 수는 다음과 같이 8가지다.
  • 7번째 경우에서 8만큼의 식량을 얻을 수 있으므로 최적의 해는 8이다.

이미지 출처: 동빈나 유튜브 - (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍

 

이미지 출처: 동빈나 유튜브 - (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍

이미지 출처: 동빈나 유튜브 - (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍

이미지 출처: 동빈나 유튜브 - (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍

 

* [Python] 답안예시

 

import sys

input = sys.stdin.readline
# 정수 N을 입력받기
n = int(input())
# 모든 식량 정보 입력받기
array = list(map(int, input().split()))

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

# DP 진행(바텀업)
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
	d[i] = max(d[i-1], d[i-2] + array[i])
    
# 계산된 결과 출력
print(d[n-1])

 

출처: https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6