이코테 5. 다이나믹 프로그래밍

다이나믹 프로그래밍이란?

• 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법입니다.
• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다.
• 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성됩니다.

• 다이나믹 프로그래밍은 동적 계획법이라고도 부릅니다.
• 일반적으로 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까요?
  
  • 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미합니다.
  • 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어입니다.

 

 

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

 

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

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

 

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

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

 

 

 

피보나치 수열: 단순 재귀 소스코드(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));
    }
}

 

 

 

 

피보나치 수열: 보텀업 다이나믹 프로그래밍 소스코드(Java)

import java.util.*;

public class Main {
	public static long[] d = new long[100];
    
    public static void main(String[] args){
    	d[1] = 1;
        d[2] = 1;
        int n = 50;
        
        for(int i=3; i<=n; i++){
        	d[i]=d[i-1]+d[i-2];
        }
        System.out.println(d[n]);
    }
}

 

 

 

 

 

 

 

개미전사 정답코드 (Java)

import java.util.*;

public class Main {

    // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 
    public static int[] d = new int[100];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 정수 N을 입력받기
        int n = sc.nextInt();

        // 모든 식량 정보 입력받기
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
        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]);
    }
}

 

 

 

 

1로 만들기 정답 코드(Java)

import java.util.*;

public class Main {

    // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 
    public static int[] d = new int[30001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();

        // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
        for (int i = 2; i <= x; i++) {
            // 현재의 수에서 1을 빼는 경우
            d[i] = d[i - 1] + 1;
            // 현재의 수가 2로 나누어 떨어지는 경우
            if (i % 2 == 0)
                d[i] = Math.min(d[i], d[i / 2] + 1);
            // 현재의 수가 3으로 나누어 떨어지는 경우
            if (i % 3 == 0)
                d[i] = Math.min(d[i], d[i / 3] + 1);
            // 현재의 수가 5로 나누어 떨어지는 경우
            if (i % 5 == 0)
                d[i] = Math.min(d[i], d[i / 5] + 1);
        }

        System.out.println(d[x]);
    }
}

 

 

Reference.

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