[알고리즘] Dynamic Programming(동적 계획법, DP)

알고리즘

[알고리즘] Dynamic Programming(동적 계획법, DP) | 백준 1463. 1로 만들기 _Java

3o14 2023. 8. 29. 15:11

728x90

피보나치 수열로 메모이제이션의 필요성 알아보기

피보나치 수열이란?

0과 1로 시작하고 이전의 두 수의 합을 다음 항으로 하는 수열을 피보나치 수열이라 함
- 0, 1, 1, 2, 3, 5, 8, 13, …
피보나치 수열의 i번째 값을 계산하는 함수 F를 정의하면 다음과 같다
- F0 = 0, F1 = 1
- Fi = Fi-1 + Fi-2 for i ≥ 2
위의 정의로부터 피보나치 수열의 i번째 항을 반환하는 함수를 재귀함수로 구현할 수 있음

fibo(n)
	IF n < 2: RETURN n
	ELSE    : RETURN fibo(n-1) + fibo(n-2)

피보나치 수열의 문제점

앞의 예에서 피보나치 수를 구하는 함수를 재귀함수로 구현한 알고리즘은 아래와 같은데

이는 엄청난 중복 호출 문제를 초래함을 알 수 있다.

여기서 얼마나 중복되었는지, 중복을 피할 수 있는 방법은 무엇인지 알아 볼 수 있다.

메모이제이션 (Memoization)

컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하는 것 → 실행 속도가 빨라짐 (동적 계획법의 핵심)
memoization 글자 그대로 해석하면 ‘메모리에 넣기(to put in memory)’라는 의미이며 ‘기억되어야 할 것’이라는 뜻의 라틴어 memorandum에서 파생되었다.

피보나치 수를 구하는 알고리즘에서 fibo1(n)의 값을 계산하자마자 저장하면 (memoize), 실행 시간을 O(n)으로 줄일 수 있다.

Memoization을 적용한 알고리즘

// memo를 위한 배열을 할당하고, 모두 0으로 초기화한다
// memo[0]을 0으로 memo[1]는 1로 초기화한다

fibo1(n)
	IF n >= 2 AND memo[n] = 0
		memo[n] <- fibo1(n-1) + fibo1(n-2)
	RETURN memo[n] // 메모해둔 값이 있다면 그거 사용하기

코드 구현

단순 재귀호출로 구현한 피보나치 수열

// 단순 재귀 호출로 피보나치 구현하기
private static long fibo1(int n) { // 피보나치 n항 구하기
    totalCnt1++;
    callCnt1[n]++;
    if(n<2) return n;
    return fibo1(n-1) + fibo1(n-2);
}

메모이제이션을 이용해 구현한 피보나치 수열

// 메모이제이션을 통한 피보나치 구현
private static long fibo2(int n) {
    totalCnt2++;
    callCnt2[n]++;

    if(memo[n] == -1) { // 메모 안되어있을 경우 재귀 호출
        memo[n] = fibo2(n-1) + fibo2(n-2);
    }
    return memo[n]; // 메모 되어있을 경우 바로 메모값 반환
}

전체 코드

package Algorithm;
import java.util.*;
import java.io.*;
public class FibonacciTest {

	static long totalCnt1, totalCnt2, callCnt1[], callCnt2[], memo[];
	
// 단순 재귀 호출로 피보나치 구현하기
	private static long fibo1(int n) { // 피보나치 n항 구하기
		totalCnt1++;
		callCnt1[n]++;
		if(n<2) return n;
		return fibo1(n-1) + fibo1(n-2);
		
	}
	
// 메모이제이션을 통한 피보나치 구현
	private static long fibo2(int n) {
		totalCnt2++;
		callCnt2[n]++;
		
		if(memo[n] == -1) { // 메모 안되어있을 경우 재귀 호출
			memo[n] = fibo2(n-1) + fibo2(n-2);
		}
		return memo[n]; // 메모 되어있을 경우 바로 메모값 반환
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		totalCnt1 = totalCnt2 = 0;
		callCnt1 = new long[N+1];
		callCnt2 = new long[N+1];
		memo = new long[N+1];
		
		
		Arrays.fill(memo, -1); // 메모 배열 초기값 -1로 세팅
		
		memo[0] = 0;
		memo[1] = 1;
		
		System.out.println(fibo1(N));
		System.out.println("fibo1: " + totalCnt1);
		for (int i = 0; i < N; i++) {
			System.out.println("fibo1["+i+"] : " + callCnt1[i]);
		}
		System.out.println("-------------------");
		System.out.println(fibo2(N));
		System.out.println("fibo2: " + totalCnt2);
		for (int i = 0; i < N; i++) {
			System.out.println("fibo2["+i+"] : " + callCnt2[i]);
		}
	}

}

5를 입력했을때 결과값 차이

5
5
fibo1: 15
// 각 fibo1[n]이 호출된 횟수
fibo1[0] : 3
fibo1[1] : 5
fibo1[2] : 3
fibo1[3] : 2
fibo1[4] : 1
-------------------
5
fibo2: 9
// 각 fibo1[n]이 호출된 횟수
fibo2[0] : 1
fibo2[1] : 2
fibo2[2] : 2
fibo2[3] : 2
fibo2[4] : 1

입력값: 45 일 때 결과값 차이 보기

45를 입력했을때 결과값 차이

45
1134903170
fibo1: 3672623805
fibo1[0] : 701408733
fibo1[1] : 1134903170
fibo1[2] : 701408733
fibo1[3] : 433494437
fibo1[4] : 267914296
fibo1[5] : 165580141
fibo1[6] : 102334155
fibo1[7] : 63245986
fibo1[8] : 39088169
fibo1[9] : 24157817
fibo1[10] : 14930352
fibo1[11] : 9227465
fibo1[12] : 5702887
fibo1[13] : 3524578
fibo1[14] : 2178309
fibo1[15] : 1346269
fibo1[16] : 832040
fibo1[17] : 514229
fibo1[18] : 317811
fibo1[19] : 196418
fibo1[20] : 121393
fibo1[21] : 75025
fibo1[22] : 46368
fibo1[23] : 28657
fibo1[24] : 17711
fibo1[25] : 10946
fibo1[26] : 6765
fibo1[27] : 4181
fibo1[28] : 2584
fibo1[29] : 1597
fibo1[30] : 987
fibo1[31] : 610
fibo1[32] : 377
fibo1[33] : 233
fibo1[34] : 144
fibo1[35] : 89
fibo1[36] : 55
fibo1[37] : 34
fibo1[38] : 21
fibo1[39] : 13
fibo1[40] : 8
fibo1[41] : 5
fibo1[42] : 3
fibo1[43] : 2
fibo1[44] : 1
-------------------
1134903170
fibo2: 89
fibo2[0] : 1
fibo2[1] : 2
fibo2[2] : 2
fibo2[3] : 2
fibo2[4] : 2
fibo2[5] : 2
fibo2[6] : 2
fibo2[7] : 2
fibo2[8] : 2
fibo2[9] : 2
fibo2[10] : 2
fibo2[11] : 2
fibo2[12] : 2
fibo2[13] : 2
fibo2[14] : 2
fibo2[15] : 2
fibo2[16] : 2
fibo2[17] : 2
fibo2[18] : 2
fibo2[19] : 2
fibo2[20] : 2
fibo2[21] : 2
fibo2[22] : 2
fibo2[23] : 2
fibo2[24] : 2
fibo2[25] : 2
fibo2[26] : 2
fibo2[27] : 2
fibo2[28] : 2
fibo2[29] : 2
fibo2[30] : 2
fibo2[31] : 2
fibo2[32] : 2
fibo2[33] : 2
fibo2[34] : 2
fibo2[35] : 2
fibo2[36] : 2
fibo2[37] : 2
fibo2[38] : 2
fibo2[39] : 2
fibo2[40] : 2
fibo2[41] : 2
fibo2[42] : 2
fibo2[43] : 2
fibo2[44] : 1

메모이제이션의 단점

추가적인 메모리 공간이 필요하다.
재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 되고 실행 속도 저하 또는 오버플로우가 발생할 수 있다.
해결책은?

동적 계획법 (Dynamic Programming)

동적 계획법은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.
- 경우의 수 구할 때도 동적 계획법을 사용할 수 있다.
동적 계획법은 먼저 작은 부분 문제들의 해를 구하고 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법이다.

동적 계획법의 적용 요건

중복 부분문제 구조(Overlapping subproblems)
최적 부분문제 구조(Optimal substructure)

중복 부분문제 구조(Overlapping subproblems)

DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고, 작은 문제들의 최적해(Optimal Solution)을 이용하여 순환적으로 큰 문제를 해결한다.
- 순환적인 관계(recurrence relation)를 명시적으로 표현하기 위해서 동적 계획법에서는 일반적으로 수학적 도구인 점화식을 사용한다.
DP는 문제의 순환적인 성질 때문에 이전에 계산되었던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데(Overlapping subproblems) 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 어떤 저장 공간(table)에 저장하게 된다.
그리고 이렇게 저장된 해들이 다시 필요할 때 마다 해를 얻기 위해 다시 문제를 재계산하지 않고 table의 참조를 통해서 중복 계산을 피할 수 있다.

최적 부분문제 구조(Optimal substructure)

동적 계획법이 최적화에 대한 어느 문제에나 적용될 수 있는 것은 아니다. 주어진 문제가 최적화의 원칙(Principle of Optimality)을 만족해야만 동적 계획법을 효율적으로 적용할 수 있다.
최적화의 원칙이란 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다. 동적 계획법의 방법 자체가 큰 문제의 최적 해를 작은 문제의 최적해들을 이용하여 구하기 때문에 만약 큰 문제의 최적해가 작은 문제들의 최적해들로 구성되지 않는다면 이 문제는 동적 계획법을 적용할 수 없다.

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net

분류

다이나믹 프로그래밍

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

🎯 시간복잡도 3^n 이 나오는 풀이법

import java.util.*;
import java.io.*;

public class Main {

	static long []arr;
	private static int func(int n, int cnt) {
		if(n == 1) {
			return 0;
		}
		
		int min = func(n-1, cnt+1) +1;
		
		if(n%2 == 0) {
			int min1 = func(n/2, cnt+1) +1;
			min = Math.min(min, min1);
		}
		if(n%3 == 0) {
			int min1 = func(n/3, cnt+1) +1;
			min = Math.min(min, min1);
		}
		
		return min;
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int cnt = 0;
		int ans = func(N, cnt);
		
		System.out.println(ans);
	}

}

🎯 dp를 이용한 풀이법

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int N;
	static int res = Integer.MAX_VALUE;
	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		//구현
		dp = new int[N+1]; //0
		dp[1] = 0;
		for(int i = 2; i <= N; i++) {
			//1빼기
			dp[i] = dp[i-1] + 1;
			//2로 나누어 보기(나누어 떨어지면)
			if(i % 2 == 0) {
				dp[i] = Math.min(dp[i], dp[i/2]+1);
			}
			//3으로 나누어보기(나누어 떨어지면)
			if(i % 3 == 0) {
				dp[i] = Math.min(dp[i], dp[i/3]+1);
			}
		}
		System.out.println(dp[N]);
		
	}
}

🎯 dp없이 제일 효율적인 방법

재귀 호출할 때 연산 횟수를 같이 갱신시키는 방법이다.

import java.util.*;
import java.io.*;

public class Main {

	static int []dp;
	private static int func(int n, int cnt) {
		if(n < 2) return cnt;
		
		return Math.min(func(n/2, cnt+1 + (n%2)), func(n/3, cnt+1 + (n%3)));
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		System.out.println(func(N, 0));
	}
}

LIST

저작자표시