계단 오르기(Dynamic Programing)

계단 오르기

 

동적계획법이란?

수학과 컴퓨터 과학, 그리고 경제학에서 
동적 계획법(dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

 

 

동적 프로그래밍 방법

큰 문제를 작은 문제로 쪼개어 푼다. 정답을 구한 작은 문제를 어딘가에 메모해 놓고 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의  결괏값을 이용한다. (메모이제이션 사용)

 

메모이제이션이란?

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

 

메모이제이션 예시 코드 

package recursive;

/**
 * 피보나치 재귀
 */
public class Recursive3 {

    static int[] fibo;
    public int DFS(int n) {
        if (fibo[n] > 0) return fibo[n]; // 메모이제이션
        if (n == 1) return fibo[n] = 1;
        else if (n == 2) return fibo[n] = 1  ;
        else return fibo[n] = DFS(n - 2) + DFS(n - 1);

    }

    public static void main(String[] args) {
        Recursive3 T = new Recursive3();
        int n = 45;

        fibo = new int[n + 1];
        T.DFS(n);
        for (int i = 1; i <= n ; i++) {
            System.out.print(fibo[i] + " ");
        }
    }
}

 

 

---

 

문제

문제

 

 

코드

package dynamic;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 계단 오르기
 */
public class Dynamic1 {
    static int[] dy;

    static int solution(int n) {
        // 첫 번째와 2번째 계단의 경우의 수는 미리 저장
        dy[1] = 1;
        dy[2] = 2;
		
        // 피보나치 수열과 같은 구조
        for (int i = 3; i <= n; i++) {
            dy[i] = dy[i - 2] + dy[i - 1];
        }

        return dy[n];
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        dy = new int[N + 1];

        System.out.println(solution(N));


    }
}

 

dy [1] = 1 첫 번째 계단까지 가는 방법의 수

dy [2] = 2 두 번째 계단까지 가는 방법의 수

 

dy [i] → i 번째까지 가는 방법의 수는 계단을 오를 때 한 계단 또는 두 계단 씩만 갈 수 있으므로 dy [i-1] + dy [i-2]가 정답이 된다.