다이나믹 프로그래밍(DP)

  • 메모리를 적절히 활용하여 수행시간 효율성을 비약적으로 향상시키는 방법
  • 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산되지 않도록 캐싱한다.

구현 종류

- Top down

- Bottom up

DP의 조건

  • 최적 부분 구조(Optimal Substructure)
    • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결
  • 중복되는 문제 (Overlapping Subproblem)
    • 동일한 작은 문제를 반복적으로 해결해야함

피보나치 수열

피보나치 수열은 다음과 같은 형태를 가지는 수열이다.

- 점화식이란 인접한 항들 사이의 관계식

- 피보나치 수열을 점화식으로 표현한다면?

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

print(fibo(4))
>> 3

 

 

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));
        }
 }

다만 위와 같이 재귀함수로 단순히 구현한다면 지수 시간 복잡도를 가지게 된다.

O(2N2) -> O(N2)

 

따라서 fib(30)을 계산해야한다면 대략 10억 가량의 연산을 수행해야하므로 비효율적이다.

 

 

다이나믹 프로그래밍 구현

메모이제이션 (Memoization)

  • top down 방식에서 사용
  • 한 번 계산한 결과를 메모리 공간에 메모하는 기법
    • 같은 문제가 다시 호출되면 메모했던 결과를 그대로 가져옴
    • 캐싱(Caching)이라고도 함

Top Down VS Bottom Up

  • Top dowon은 하향식, Bottom Up은 상향식
  • 전형적인 형태는 Bottom up 방식
    • 결과 저장용 리스트는 DP 테이블
  • 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념 의미
    • DP에만 국한된 개념 아님

Top Down

특징

  • 재귀적 접근: 큰 문제를 재귀적으로 작은 문제로 나눕니다. 
  • 메모이제이션: 이미 계산된 값을 저장하여 중복 계산을 방지합니다. 
  • 코드 구조: 재귀 함수와 조건문을 통해 구현됩니다.

Bottom Up

특징

  • 반복적 접근: 작은 문제부터 시작하여 점진적으로 큰 문제를 해결합니다.
  • 테이블 초기화: 처음부터 작은 문제의 해를 계산하고 저장합니다.
  • 코드 구조: 반복문과 배열을 통해 구현됩니다.

 

  1. 구현 방식
    1. Top dowon : 재귀 함수와 메모이제이션을 사용하여 큰 문제를 작은 문제로 나누어 해결.
    2. Bottom Up : 반복문을 사용하여 작은 문제부터 해결해 나가며 큰 문제를 해결. 
  2. 메모리 사용 
    1. Top dowon : 재귀 호출을 위해 스택 메모리를 사용하고, 메모이제이션을 위한 추가 메모리가 필요. 
    2. Bottom Up : 주로 배열을 사용하여 결과를 저장. 
  3. 초기화
    1. Top dowon : 함수 호출 시점에서 필요한 값이 계산됨. 
    2. Bottom Up : 모든 값을 순차적으로 계산하고 저장.
  4. 중복 계산 방지
    1. Top dowon : 메모이제이션을 통해 중복 계산을 방지. 
    2. Bottom Up : 한 번만 계산하여 배열에 저장하므로 중복 계산이 없음.

 

 

피보나치 함수를 재귀함수로 구현 (Top down)

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

# 피보나치 함수를 재귀함수로 구현 (Top down)
def fibo(x):
	# 종료 조건(1 or 2일 때 1 반환)
    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

피보나치 수열: Bottom Up 방식 DP (Python)

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

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

# 피보나치 함수 반복문으로 구현(Bottom up)
for i in range(3, n+1):
	d[i] = d[i-1] + d[i-2]
print(d[n])# 실행 결과: 218922995834555169026

 

피보나치 수열

메모이제이션 동작 분석

- 시간 복잡도 O(N)

d =[0]*100

def fibo(x):
    print('f('+str(x)+')',end=' ')
    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]
fibo(6) # 실행결과: f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

 

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

  • 모두 최적 부분 구조를 가질 때 사용
    • 큰 문제를 작은문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결
  • 차이점: 부분 문제의 중복
    • DP의 경우 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
    • 분할 정복의 경우 동일한 부분 문제가 반복으로 계산되지 않음
    • 분할 정복 대표 -> 퀵 정렬
      • 한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면 그 기준원소는 위치 바뀌지 않고, 분할 이후에 해당 피벗을 다시 처리하는 부분 문제에서 호출하지 않음


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

  • 다이나믹 문제인지 유형 파악
  • 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는 지 검토
    • 풀이 방법이 떠오르지 않으면 다이나믹 프로그램이 고려
  • 일단 재귀함수로 완전탐색 작성 후 (탑다운) 작은 문제에서 구한 답이 큰 문제에 그대로 사용가능하면, 코드 개선

 

 

 

문제 1, 개미전사


식량창고 N개가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램문제 해결 방법

 

  • ai= i번째 식량창고까지의 최적의 해 (얻을 수 있는 식량의 최댓값)
  • ki = i번째 식량창고에 있는 식량의 양

 

  • 한 칸이상 떨어진 식량 창고는 항상 털 수 있기에 (i - 3)번쨰 이하는 고려할 필요가 없다.
n = int(input())
array = list(map(int,input().split()))

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

# 다이나믹 프로그래밍 Bottom up
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])

 

public static int[] d = new int[100];

public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i<n; i++){
    	arr[i] = sc.nextInt();
    }
    
    d[0] = arr[0];
    d[1] = Math.max(arr[0], arr[1]);
    for (int i = 2; i < n; i++){
    	d[i] = Math.max(d[i-1],d[i-2]+arr[i]);
   }
   System.out.println(d[n-1]);
   }
 }

 

 

문제2, 1로 만들기

 

정수 X 가 주어졌을 때, 연산 4개를 적절히 사용하여 값을 1로 만들기 

연산을 사용하는 횟수의 최솟값 구하기

 

연산

  1. X가 5로 나누어 떨어지면 5로 나누기
  2. X가 3으로 나누어 떨어지면 3으로 나누기
  3. X가 2로 나누어 떨어지면 2로 나누기
  4. X에서 1 빼기


    e.g. 26 -> 25 -> 5 -> 1 => 횟수 3

 

문제 해결 방법

ai = i를 1로 만들기 위한 최소 연산 횟수

 

 

x = int(input())
# x가 30,000까지 들어올 수 있기 때문에 거기에 맞춰서 dp 테이블 초기화
d = [0] * 30001 # 1일 경우 자기자신이 그대로 1이기때문에 연산 수행할 필요없음 -> 0으로 초기화 되어있다고 가정, 2부터 시작

# Bottom up
for i in range(2, x+1):
	# 현재의 수에서 1을 빼는 경우
    d[i] = d[i-1] + 1
    # 현재의 수에서 2로 나누어 떨어지는 경우
    if i % 2 == 0:
    	d[i] = min(d[i],d[i//2]+1)
    # 현재의 수에서 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
    	d[i] = min(d[i],d[i//3]+1)
    # 현재의 수에서 5로 나누어 떨어지는 경우
    if i % 5 == 0:
    	d[i] = min(d[i],d[i//5]+1)
print(d[x])
public static int[] d = new int[30001];

public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
    
    int x = sc.nextInt();
    for (int i = 0; i<=x; i++){
    	d[i] = d[i-1]+1;
    	if (i%2==0)
        	d[i] = Math.min(d[i],d[i/2]+1);
        if (i%3==0)
        	d[i] = Math.min(d[i],d[i/3]+1);
        if (i%5==0)
        	d[i] = Math.min(d[i],d[i/5]+1);
    }
   System.out.println(d[x]);
   }
 }

 

 

 

티스토리툴바