[코딩테스트연습] 2 x n 타일링
문제 설명
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.
- 타일을 가로로 배치 하는 경우
- 타일을 세로로 배치 하는 경우
예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 가로의 길이 n은 60,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
입출력 예
| n | result |
|---|---|
| 4 | 5 |
입출력 예 설명
입출력 예 #1
다음과 같이 5가지 방법이 있다.
코드 풀이
동적 계획법으로 풀 수있는 쉬운 문제 중에 하나이다. 동적 계획법을 풀 때 보통 메모라이제이션(memorization) 혹은 bottom-up 방식을 사용한다. 처음에는 가장 쉬운 bottom-up 방식을 이용해서 풀어 보았다.
def solution(n):
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n] % 1000000007이렇게 풀어도 정답은 맞지만, 효율성 체크에서 시간초과가 뜨고 만다. 아마 매우 큰 숫자를 입력했을때 파이썬 리스트의 속도가 느려지는 것 같았다.
이를 개선 하기 위해 리스트를 사용하지 않는 메모라이제이션 방식을 사용했다 스택오버플로우 에서는 Naive한 방식이라고 소개 되어있었는데 효율성 검사를 잘 통과 할 수 있었다.
def solution(n):
a,b = 1,2
for _ in range(n-1):
a,b = b, a + b
return a % 1000000007
추가 기록 - 동적 계획법
동적 계획법으로 여러가지 방식이 존재한다. 스택오버플로우 를 참고 하여, bottom-up, memorization, a naive 한 방식을 설명하고자 한다. 가장 쉬운 예로 피보나치 수열을 예로 들어 본다.
from the bottom up
가장 쉬운 방식으로 저장된 이전의 값을 사용해서 다음 값을 계산한다.
>>> def fib_to(n):
... fibs = [0, 1]
... for i in range(2, n+1):
... fibs.append(fibs[-1] + fibs[-2])
... return fibs피보나치 수열 20을 구해보면 다음과 같다.
>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]Memoization
다음은 메모라이제이션 방식이다. bottom-up 방식보다 조금 복잡하지만, 빠르다고 알려져 있다. bottom-up 방식의 문제점은 이미 계산한 값을 다시 계산하는 것이 문제이다. 이를 개선 하기 위해 이미 계산한 값을 어딘가 저장 해놓고 필요할때 다시 사용하는 방식을 메모라이제이션 방식이라고 한다.
>>> def fib(n, computed = {0: 0, 1: 1}):
... if n not in computed:
... computed[n] = fib(n-1, computed) + fib(n-2, computed)
... return computed[n]