2×n 타일링 점화식 완벽 이해 - 알고노트

2×n 타일링이란?

2×n 타일링은 폭이 2칸이고 길이가 n칸인 직사각형 복도를, 1×2(가로로 눕힌)와 2×1(세로로 세운) 타일로 빈틈도 겹침도 없이 채우는 경우의 수를 구하는 문제입니다.

동적 계획법(DP)을 처음 배울 때 가장 직관적인 예시 중 하나입니다. 정답을 그림으로 그려보면 "끝 칸을 어떻게 덮느냐"에 따라 경우가 깔끔하게 둘로 갈리는 것이 눈에 보입니다.

왜 중요한가?

• •점화식 설계의 정석: "마지막 한 조각"을 기준으로 경우를 나누는 사고법을 익힐 수 있습니다.
• •피보나치와 동일한 구조: dp[i]=dp[i-1]+dp[i-2]로, 점화식 입문에 최적입니다.
• •코딩 테스트 빈출 유형: 타일링/격자 채우기 계열 문제의 기본기입니다.

점화식 세우기

복도의 맨 끝 열을 어떻게 덮을지 생각해봅시다.

경우 1. 끝을 세로 타일(2×1) 1개로 덮는다 → 앞쪽에 길이 i-1 복도가 남습니다 → dp[i-1]가지

경우 2. 끝을 가로 타일(1×2) 2개를 위아래로 쌓아 덮는다 → 앞쪽에 길이 i-2 복도가 남습니다 → dp[i-2]가지

두 경우는 겹치지 않으므로 더하면 됩니다.

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

기저 조건

• •dp[1] = 1 (세로 1개)
• •dp[2] = 2 (세로 2개 / 가로 2개)

값 채워보기

dp[3]=2+1=3, dp[4]=3+2=5, dp[5]=5+3=8, dp[6]=8+5=13. 정확히 피보나치 수열의 형태입니다.

시간복잡도와 공간복잡도

모든 부분 문제를 한 번씩만 계산하므로 O(n)입니다. 직전 두 값만 기억하면 배열 없이 O(1) 공간으로도 풀 수 있습니다.

자주 하는 실수

• •기저 조건 혼동: dp[1]=1, dp[2]=2를 정확히 설정해야 합니다. dp[2]를 1로 두면 전부 어긋납니다.
• •타일 종류 오해: 회전만 허용되는 1×2와 2×1 두 종류뿐입니다. L자 등 다른 모양을 섞으면 다른 문제가 됩니다.
• •중복 계산: 재귀로만 풀면 O(2^n)으로 폭발합니다. 반드시 메모이제이션 또는 상향식 DP를 씁니다.

알고노트에서 직접 확인하세요

길이가 늘어날 때마다 dp[i]가 어떻게 dp[i-1]과 dp[i-2]에서 만들어지는지, 알고노트에서 한 단계씩 시각적으로 확인할 수 있습니다.

복도 타일 깔기 시각화 바로가기 →