2xn 타일링 Pgs#12900

2xN 타일링 PGs#12900

Python 코드 보기

def _2x2_matrix_multi(a,b):
    new = [[0,0],[0,0]]
    for i in range(0,2):
        for j in range(0,2):
            for k in range(0,2):
                new[i][j] += a[i][k] * b[k][j]
    return new

def nth_2x2_fiboMatrix(fiboMatrix,n):
    k = 0
    new = [[1,0],[0,1]]         # 항등원
    tmp = fiboMatrix.copy()
    
    while (2**k <= n):
        if n & (1 << k) != 0:   # 6번째 -> 2^2, 2^1번째의 곱 이므로!!
            new = _2x2_matrix_multi(new,tmp)
        k += 1
        tmp = _2x2_matrix_multi(tmp,tmp)    # 매 while문 마다 2배수씩 늘어남
        
    return new

def solution(n):
    answer = 0
    fiboMatrix = [[1,1],[1,0]]  # [[fn+1, fn], [fn, fn-1]]
    
    return nth_2x2_fiboMatrix(fiboMatrix,n+1)[0][1] % 1000000007

---

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

☝ 입력 형식

직사각형의 가로의 길이 n이 매개변수로 주어집니다.

제한사항

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

🤞 출력 형식

• 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

🤟 구현 과정

1. 2x2 행렬의 곱 구현

2x2행렬의 곱을 수행하는 _2x2_matrix_multi() 함수를 정의해주었다.

matrix의 정의를 조금 수정해 가변형으로 정의하거나, 3중 for문의 범위를 2가 아닌 행렬의 크기, size를 받아 연산을 수행하면 더 큰 행렬에 대해서도 사용할 수 있다.

2. n번째 피보나치 수를 포함한 행렬 찾기

n번째 피보나치 수를 포함하는 행렬을 찾기 위해, nth_2x2_fiboMatrix()를 정의하였다.

if n & (1 << k) != 0:
	new = _2x2_matrix_multi(new,tmp)

해당 정의의 if n & (1 << k) != 0:부분이 가장 직관적이지 못한데, 이는 매 while문 시행마다 tmp가 제곱수로 늘어나는 식으로 구현되었기 때문이다.

즉, 매 시행마다 tmp는 자기 자신과 곱해지므로,항상 k번째 시행되는 while문에서 아래와 같은 꼴로 존재한다.

\[\begin{pmatrix} F_{2^k+1} & F_{2^k} \\ F_{2^k} & F_{2^k-1} \end{pmatrix}\]

이 때, 2^k이 n을 2의 배수의 합으로 나타내는데 사용되는 값이라면 누적하여 곱해주는 방식이다.

예를 들어 n=6이라면, 2^k=4,2일 때, 즉 k=2,1일 때 누적하여 곱해진다는 이야기다.

3. solution 구현

솔루션 함수는 그다지 구현이 필요하지 않다.

단순히 nth_2x2_fiboMatrix()에 값을 넣고, 1,000,000,007로 나눈 값을 return하기만 하면 된다.

🍀 Pain Points

1. 시간 복잡도

O(N)의 시간 복잡도를 갖는 DP방식으로 설계한 기존의 피보나치 알고리즘으로는 마지막 효율성 검사에서 시간초과가 발생하였다.

O(N)보다 더 작은 시간 복잡도를 갖는 피보나치 알고리즘을 찾아보니, O(logN)을 갖는 방법을 2가지 정도 더 알 수 있었다. 참고한 사이트를 링크해두었다.

1. 일반항을 이용한 값 구하기
2. 2x2행렬의 곱을 이용한 피보나치 수 구하기

일반항을 이용하여 값을 계산하면 더 쉽게 값을 찾을 수 있을 것 같았으나, numerical result out of range 에러가 발생하여 일반항으로는 계산 할 수 없었다.

행렬의 곱을 이용한 피보나치 알고리즘은 처음 계산해보았으나, 기존의 DP를 이용했을 때와 메모리나 소요 시간을 비교해보니 비교가 무색할정도로 복잡도가 줄어들었음을 알 수 있었다.

참고한 사이트

1. https://nukestorm.tistory.com/149
2. https://suhak.tistory.com/81