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

 

 

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

피보나치 수열이란?

• 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로 만들기

 

 

 

분류

다이나믹 프로그래밍

문제 설명

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 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));
	}
}