프로그래밍과 알고리즘이 점점 더 중요해지고 있는 오늘날, 많은 기업들이 취업 시 알고리즘 및 코딩 테스트를 필수적으로 요구하고 있습니다. 그 중 하나의 인기 있는 문제는 2*N 타일 채우기 입니다. 이번 글에서는 이 문제를 분석하고 해결하는 과정을 상세하게 설명하겠습니다. 이 문제를 통해 동적 프로그래밍(DP)의 개념도 배우고, 이를 활용한 파이썬 코드 구현도 살펴보겠습니다.
문제 설명
문제는 다음과 같습니다:
2 x n 크기의 직사각형 공간을 1 x 2 또는 2 x 1 크기의 타일로 채우는 방법의 수를 구하세요.
예를 들어, n=3일 때는 다음과 같은 방법으로 타일을 채울 수 있습니다:
- 1 x 2 타일 3개 수직 배치
- 1 x 2 타일 1개 수평, 나머지 2개 수직 배치
- 1 x 2 타일 2개 수평, 나머지 1개 수직 배치
- 2 x 1 타일 1개, 1 x 2 타일 2개 배치
- 2 x 1 타일 3개 수직 배치
이 문제의 해결 방법은 동적 프로그래밍을 통해 접근할 수 있습니다. 각 타일을 놓는 방식에 따라 재귀적으로 문제를 나누고, 이를 메모이제이션(Memoization) 기법을 사용하여 저장함으로써 중복 계산을 피하는 것이 핵심입니다.
문제 해결 접근 방법
이 문제는 다음과 같은 규칙을 기반으로 해결할 수 있습니다:
- 기본 경우: n=1일 경우, 1 x 2 타일을 세로로 놓는 방법만 가능합니다. 따라서 경우의 수는 1입니다.
- 더욱 일반적인 경우: n=2일 경우, 1 x 2 타일 2개를 수평으로 놓거나, 2 x 1 타일 1개를 세로로 놓을 수 있는 두 가지 방법이 있습니다. 따라서 경우의 수는 2입니다.
- 재귀식: n > 2일 경우, 두 가지 방법으로 나눌 수 있습니다:
- 1 x 2 타일을 배치하고 나머지 2 x (n-1) 공간을 채우는 경우
- 2 x 1 타일을 배치하고 나머지 2 x (n-2) 공간을 채우는 경우
따라서 재귀 관계는 다음과 같이 표현할 수 있습니다:
f(n) = f(n-1) + f(n-2)
동적 프로그래밍 구현
이제 위의 재귀 관계에 따라 동적 프로그래밍(DP)을 활용하여 문제를 해결하는 파이썬 코드를 작성해 보겠습니다.
def tile_fill(n):
# DP 배열을 초기화합니다.
dp = [0] * (n + 1)
# 기본 경우를 설정합니다.
dp[0] = 1 # 아무 것도 채우지 않는 경우
if n >= 1:
dp[1] = 1 # 1 x 2 타일을 세로로 놓는 경우
# DP 배열을 채웁니다.
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
코드 설명
위 코드에서 먼저 0부터 n까지의 DP 배열을 초기화합니다. 기본 경우로 f(0)과 f(1)의 값을 설정한 후, 반복문을 통해 f(2)부터 f(n)까지의 값을 채우는 방식으로 진행됩니다. 최종적으로 dp[n]의 값이 2 x n 크기의 직사각형을 채우는 방법의 수입니다.
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(n)입니다. 매 반복마다 여는 DP 배열이 n개의 요소를 가진 데이터 구조만큼만 반복하기 때문입니다. 공간 복잡도 역시 O(n)입니다.
종합 정리
이번 글에서는 2*N 타일 채우기 문제를 통해 동적 프로그래밍 기법을 활용하는 방법을 배워보았습니다. 문제를 정의하고, 반복적인 수식을 통해 해를 구하는 방식, 그리고 이를 코드로 구현해보는 과정을 통해 알고리즘적 사고를 기를 수 있었습니다. 실제 코딩 테스트에서 이와 유사한 문제가 출제될 수 있으므로, 반복적으로 연습하시기 바랍니다.
문제 변형 및 응용
만약 이 문제에서 주어진 직사각형의 크기가 2 x N이 아닌 다른 형태로 변한다면, 예를 들어 3 x N으로 바뀌게 된다면, 어떻게 접근할지 고민해보세요. 문제를 변형하는 연습을 통해 알고리즘적 사고를 더욱 깊이 있게 발전시키는데 큰 도움이 될 것입니다.
결론적으로, 알고리즘 문제를 해결할 때는 문제를 분해하고, 가능한 해결 방안을 모색하는 것이 중요합니다. 2*N 타일 채우기 문제는 그러한 사고를 체화하는데 좋은 예제입니다.