백준 알고리즘, 11726 문제

---

개요

이 문제는 Dynamic Programming 분류에 속하는 문제이다.

앞으로 문제를 풀며 기억해야 할 점은

문제에서 언급되는 알고리즘 이외에 언어들.. 예를 들면 타일링, 직사각형, CCTV ... 등의 단어에 집착하지 말아야한다는 점이다.

가장 중요한 것은

규칙을 찾고

그 규칙에 따른 식을 만드는 것이다.

---

풀이

입력받는 n 에 따라 2 x n 의 타일이 생성된다.

그 생성된 타일에 2 x 1 모양, 혹은 1 x 2 모양의 직사각형을 채워나가는 방법의 수를 구하는 문제이다.

직접 그려보기로 하는데 주의해야할 점이 있다.

2 x 4 만 되더라도 그려나가는 규칙이 제대로 성립되어 있지 않으면 빼먹기 쉽고 매우 헷갈린다.

먼저 규칙을 정해야 한다.

(1) 2 x 1

(2) 2 x 2

(3) 2 x 3

이 그림은 마구잡이로 그린 것이 아니라 규칙을 가지고 그려나간 것이다.

2 x 3 의 첫번째와 두번째 타일은 2 x 2 의 각각의 그림의 오른쪽에 타일 하나(빨간색)를 세로로 위치시켜서 만들었다.

2 x 3 의 세번째 타일은 2 x 1 의 그림의 오른쪽에 타일 두개(빨간색)를 가로로 위치시켜서 만들었다.

이제 한번만 더 그려보자.

(4) 2 x 4

2 x 4 의 첫번째, 두번째, 그리고 세번째 타일은 2 x 3 각각의 그림의 오른쪽에 타일 하나(분홍색)를 세로로 위치시켜서 만들었다.

2 x 4 의 세번째, 다섯번째 타일은 2 x 2 각각의 그림의 오른쪽에 타일 두개(분홍색)를 가로로 위치시켜서 만들었다.

이렇게 만들어야만 직접 그려서 확인해보는 과정에서도 중복되지 않는 그림을 그릴 수 있다.

이제 점화식을 만들어보자.

앞으로 만들어나갈 n 번째 타일의 개수는 n - 2 번째와 n - 1 번째 타일의 개수의 합이므로

DP[n] = DP[n - 1] + DP[n - 2]

로 나타낼 수 있다.

---

Fibonacci 수열과의 유사성, Top-Down, Bottom-Up, Memoization

DP[n] = DP[n - 1] + DP[n - 2] 

Fibonacci 수열의 알고리즘과 정확히 일치한다. (값은 다르다.)

Fibonacci 를 풀어내는 방법은 총 3가지가 존재한다.

1. Top-Down == Recursive == Divide And Conquer

Top-Down 전략은 재귀함수를 이용해서 하나의 문제를 그보다 더 작은 단위의 문제를 해결한 뒤 (분할, Divide) 

그 후에 해결한 모든 문제를 합치는 방식 (정복, Conquer) 으로 해결하는 것을 말한다.

Fibonacci 수열에서 이 방식을 사용하는 것은 어리석은 짓이다.

수많은 재귀 호출로 구하려는 수가 조금만 커져도 많은 memory 와 시간을 잡아먹는다.

실제로 O(2^n) 의 시간복잡도를 가지는 방식이다. 

2. Bottom-Up == Iterative Dynamic Programming

Bottom-Up 전략은 문제해결 자체를 가장 밑에서 부터 시작한다는 개념이다.

예를 들어 5 번째 값을 구할때 1 -> 2 -> 3 -> ... 과정을 통해 5번째 값을 구한다는 개념이다.

이 글에서 채택한 방법이다.

3. Memoization Dynamic Programming

1 번 Top-Down 전략은 알고리즘 자체는 아주 훌륭하다.

그러나 Fibonacci 수열을 구하기에는 부적합할 뿐이다.

그럼 적합하도록 만드는 방법은 무엇일까?

Fibonacci 수열을 풀 때 Recursive 를 사용한다면 불필요한 재귀호출이 시간과 Memory 를 잡아먹는 범인이다.

그렇다면, 불필요한 재귀호출, 즉 이미 알고있는 값에 대해서는 재귀호출을 하지 않으면 된다.

이미 알고있는 값은 따로 메모를 해두어 필요할때 꺼내 쓴다는 개념이다.

O(2^n) 이었던 시간복잡도는 O(n) 으로 개선된다.

아래에서 코드를 참고할 수 있다.

---

코드

@github 에서 확인하기

# Iterative Dynamic Programming

/**
 * @site: https://www.acmicpc.net/problem/11726
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 07. 18
 */
#include <iostream>
using namespace std;
int main() {
    int DP[1001];
    int i, n;
    cin >> n;
    DP[0] = 0;
    DP[1] = 1;
    DP[2] = 2;
    for (i = 3; i <= n; i++) {
        DP[i] = (DP[i-1] % 10007) + (DP[i-2] % 10007);
    }
    cout << DP[n] % 10007 << endl;
    return 0;
}

# Memoization Dynamic Programming

/**
 * @site: https://www.acmicpc.net/problem/11726
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 07. 18
 */
#include <iostream>
using namespace std;
// Memoization DP
int memo_dynamic_programming(int n, int * memo) {
    if (memo[n] != 0) return memo[n];
    if (n == 1) {
        return 1;
    }
    else if (n == 2) {
        return 2;
    }
    else {
        memo[n] = memo_dynamic_programming(n-1, memo) + memo_dynamic_programming(n-2, memo);
    }
    return (memo[n] % 10007);
}
int main() {
    int memo[1001] = { 0, };
    int n;
    cin >> n;
    cout << memo_dynamic_programming(n, memo) << endl;
    return 0;
}

DP 배열에 값이 매우 커져 int 자료형의 범위를 넘을 수 있으므로

문제에서 요구한 바와 같이 10007 로 나눈 나머지 계산을 적용하였다.