[DP (Dynamic Programming)] 백준 11726 - 2xN 타일링

다이나믹 프로그래밍은 한 문제를 풀 때 반복적으로 계산되는 불필요한 과정을 방지하기 위해 한문제당 한번만 계산하여 문제를 푸는 방식을 말한다. 방식은 "메모이제이션"이라는 값을 저장하는 방법을 사용하는데, 다이나믹 프로그래밍의 대표적인 예는 '피보나치 수열'이 있다.

public class DynamicProgramming {
    public static int dp(int x){
        if(x == 1) return 1;
        if(x == 2) return 1;
        return dp(x-1) + dp(x-2);
    }

    public static void main(String[] args) {
        System.out.println(dp(10));
    }
}

10을 넣었을 때는 55라는 값이 바로 나오지만 대략 더 큰 숫자인 50이라는 숫자를 넣었을 땐 어떻게될까?

연산을 하긴 하겠지만 너무 오랜시간이 걸린다. 

 

 

 

n이라는 숫자를 계산한다 예시를 들면, n의 값은 (n-1) + (n-2) 이고 각각 (n-1)와 (n-2)의 값을 구할 때도 점점 두개의 값이 합쳐져야 하기 때문에 결국은 2의 n제곱만큼 숫자가 늘어나는 거라고 할 수 있다. 그렇게되면 반복되는 계산이 너무 많아지고 계산이 느려지게 되며 효율적이지 못한 방법이 된다. 따라서 이제 계산이 된 값은 저장하여 바로 사용할 수 있도록 설정하는 과정이 필요하다.

public class DynamicProgramming {
    static int[] d = new int[100];
    public static int dp(int x){
        if(x == 1) return 1;
        if(x == 2) return 1;

        if(d[x] != 0){
            return d[x];
        }else{
            return d[x] = dp(x-1) + dp(x-2);
        }
    }

    public static void main(String[] args) {
        System.out.println(dp(30));
    }
}

먼저 전역에서 사용할 수 있도록 static int[] d = new int[100]; 로 설정해주었다. 배열의 길이를 100으로 초기화 시킨 뒤

조건을 걸어서 d[x] 값이 0이 아니라면 (배열에 이미 저장되어있는 값이라면) 그대로 그 값을 출력하고,

배열의 d[x] 번째 값이 0 이라면 아직 저장되지 않은 값이라는 뜻이기 때문에 피보나치 수열 계산법을 이용하여 연산해주고 저장한다.

이러한 메모이제이션 기법을 사용하여 중복되는 연산을 확 줄이면 시간복잡도 또한 줄어들고 효율적인 계산을 할 수 있다.

 

 

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

처음엔 위와 같은 코드로 계속 시도했는데 계속 0이 나오길래 for문을 이용하여 값을 다 넣어주었다.

public class B11726Re {
    public static void main(String[] args) {
        int[] dp = new int[1001];
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();

        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= x; i++)
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;

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