자바스크립트 코딩테스트 강좌, 2 N 타일 채우기

문제 정의

2*N 직사각형을 1*2 또는 2*1 크기의 타일로 채우는 방법의 수를 계산하는 문제입니다. 즉, 주어진 길이 N에 대해, 타일을 이용해 직사각형을 완전히 채우는 경우의 수를 구하는 것입니다. 이 문제는 동적 프로그래밍(Dynamic Programming) 기법을 사용하여 해결할 수 있습니다.

문제 설명

예를 들어, N=3일 때, 2*3 직사각형을 다음과 같이 채울 수 있습니다:

• 1->1->1
• 1->2
• 2->1
• 2->2
• 2->1->1

타일을 어떻게 배치하느냐에 따라 다양한 경우가 생성됩니다. 따라서, 적절한 규칙을 찾아 재귀적으로 모든 조합을 탐색할 수 있습니다.

문제 접근 방법

1. 재귀적 접근

가장 기본적인 방법은 재귀를 이용하여 모든 경우의 수를 탐색하는 것입니다. 하지만 이는 비효율적이며 시간 복잡도가 크기 때문에 실용적이지 않습니다.

2. 동적 프로그래밍

동적 프로그래밍을 사용하여 이전의 계산 결과를 저장하고 이를 활용함으로써 중복 계산을 피할 수 있습니다. 이 접근 방식은 시간 복잡도를 O(N)으로 줄일 수 있습니다.

동적 프로그래밍 구현

점화식 설정

다음과 같은 점화식을 설정할 수 있습니다:

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

마지막 열을 1×2 면으로 채울 경우에는 dp[n-1]의 경우를 고려하며, 2×1 면으로 채울 경우에는 dp[n-2]의 경우를 고려합니다. 기초 조건은 다음과 같습니다:

• dp[1] = 1 (1*2 타일로 채우기)
• dp[2] = 2 (2*1 또는 1*2 타일로 채우기)

자바스크립트 예제 코드

function tileWays(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;

    let dp = new Array(n + 1);
    dp[1] = 1;
    dp[2] = 2;

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

console.log(tileWays(3)); // Output: 3
    

결론

2*N 타일 채우기 문제는 코딩테스트에서 자주 출제되는 기본적인 동적 프로그래밍 문제입니다. 이 문제를 통해 알고리즘 문제를 해결할 때 효율적인 접근 방식을 선택하는 것이 얼마나 중요한지를 배울 수 있습니다.
동적 프로그래밍의 기초를 잘 이해하고, 이를 활용하여 복잡한 문제를 단계별로 해결하는 능력을 키우는 것이 중요합니다. 다양한 문제에 대한 실습을 통해 더 나은 개발자가 되어가기를 바랍니다.