[Python] 프로그래머스 - 2xn 타일링

 

문제

https://programmers.co.kr/learn/courses/30/lessons/12900

코딩테스트 연습 - 2 x n 타일링

---

문제 요구 조건

가로 길이가 n으로 주어지고, 세로 길이는 2로 고정되어 있다. 세로를 2로 고정하기 때문에 고려할 사항은 가로 길이뿐이다. 따라서 가로 n을 어떻게 채울 것인가에 대해 생각하면 된다. 그렇게 되면 두 가지 선택지가 있다. 직사각형 모양 타일을 세로로 쌓거나 혹은 가로로 쌓거나이다. 즉, 1과 2를 사용해서 n을 잘 채우면 된다. 처음에는 중복조합 등으로 풀 수 있나 했으나, 순서가 중요하지만 1만으로 이루어질 때는 또 같은 케이스로 치기 때문에 중복조합이나 순열 등으로는 풀 수 없었다.

 

문제 요건 분석

• 1과 2의 가지치기가 특정 조건에 도달할 때까지 반복된다. → 재귀 풀이
• 특정 조건은 가지치기를 이어나가면서 숫자를 더해가며 n과 비교하는 것이다. n보다 크면 0(n 만들기 실패)을 반환하며, n과 같으면 1을 반환한다.
• n = 4일 경우, 다음과 같이 도식화 가능하다.

재귀적 풀이

 

재귀 풀이

위의 도식을 그대로 코드로 구현하면 아래와 같이 구현이 가능하다.

def recursive(n, s):
    """
    s: 누적합을 담고 있는 변수
    """
    if s < n:
    	return recursive(n, s+1) + recursive(n, s+2) # 1과 2로 가지치기
    elif s == n: # 탐색 성공
    	return 1
    else: # 탐색 실패
    	return 0
        
def solution(n):
    return recursive(n, 0) % 1000000007

위와 같이 누적합 s를 함수의 인자로 받는 것은 비효율적이다. 생각해보면, 재귀 깊이가 1씩 증가할 때마다 합을 더해서 그 합을 n과 비교하는 것은 반대로 n에서 1 혹은 2씩 빼주면서 0과 비교하는 것과 동일하다.

따라서, 다음과 같이 코드 변경이 가능하다.

# 수정된 풀이
def recursive(n):
	if n < 0:
    	return recursive(n-1) + recursive(n-2)
    elif n == 0: # 탐색 성공
    	return 1
    else: # 탐색 실패
    	return 0
        
 def solution(n):
 	return recursive(n) % 1000000007

실은 이 문제의 경우, 재귀 풀이는 굉장히 비효율적이라 시간초과가 발생한다. 왜 비효율적인지를 파악하기 위해서 위의 코드를 다시 도식화해보자. 이번엔 각 노드를 함수 호출로 표현해본다.

n=4일 때, 재귀함수 호출 도식화

 도식에서 알 수 있듯이, 같은 함수가 중복되어 호출됨을 알 수 있다 (하이라이트 표시). 따라서 기존에 계산되었던 함수를 다시 계산해야하기 때문에 비효율적으로 동작할 수밖에 없다. 이러한 중복 계산을 방지하기 위해서는 해당 함수의 결과값을 다른 곳에 저장해두면 된다.

 

동적계획법 풀이

즉, 이 문제는 동적계획법(Dynamic Programming)으로 풀이를 하게 된다. 이미 계산된 함수값을 다시 저장해두는 것을 메모이제이션(memoization)이라고 한다.

메모이제이션을 통해, 함수 호출 트리는 다음과 같이 pruning될 수 있다.

메모이제이션 후, 함수 호출

 

DP 풀이는 위의 재귀 풀이에서 함수값을 담아둘 배열만 선언해주면 된다. 코드는 다음과 같다.

import sys
sys.setrecursionlimit(60000) # 재귀 깊이를 n의 최대 범위만큼 늘려줌.

def solution(n):
    def dp(n):
        if mem[n] != -1:
            return mem[n] # 그렇게 되면 mem은 어디서 업데이트 시키는지가 중요함.
        if n > 0:
            mem[n] =  (dp(n-1) + dp(n-2)) % 1000000007
            return mem[n]
        elif n == 0:
            return 1
        else: # n is non-negative
            return 0
    
    mem = [-1 for _ in range(60000)]
    answer = dp(n)
        
    return answer

 

mem 배열에 해당 n의 값이 존재하는지 확인하는 부분을 추가해주고, 어디에서 mem[n]에 dp(n)값을 할당해줄 것인지를 추가해준다면 문제 없이 풀이가 가능하다.

추가적으로, mem에 함수값을 저장할 때 나머지 연산(%1000000007)을 수행해줘야 효율성 테스트 통과가 가능하다. 또한, 파이썬은 재귀 호출 시 깊이가 얕게 설정되어 있기 때문에 강제적으로 재귀 깊이 제한을 늘려주는 것이 필요하다. 호출 트리를 보면 트리의 높이는 n이기 때문에 재귀 깊이 제한은 문제에서 주어진 n의 최대 크기인 60000으로 지정해주면 된다. 

 

각 풀이의 시간복잡도

재귀 풀이의 시간복잡도와 같은 경우에는 함수 호출 트리의 노드 개수와 동일하다. 함수 호출은 2개의 가지로 뻗어나가기 때문에, 이진 트리로 구성되며 이 경우에 노드 개수는 최악의 경우 $O(2^n)$이다. 

DP 풀이의 시간복잡도는 (대략적으로) 경사 트리의 노드 개수(혹은 호출 트리의 높이)와 마찬가지이므로 (재귀적으로 n=0이 될 때까지 호출하면서 0부터 n까지의 함수값이 모두 배열에 저장이 되기 때문에 함수 호출 트리는 경사 트리와 유사하게 구성이 될 것), $O(n)$의 시간복잡도를 갖게 된다.

---

정리

전체적으로 풀이는 피보나치 수열과 매우 유사하다. 재귀함수와 친하지 않아서 처음에 재귀로 어떻게 구현할지가 조금 까다로웠던 것 같다. 피보나치 수열과 유사하다는 걸 깨닫는 순간 풀이가 매우 쉬워지는 듯하다. 다만, 위의 DP 풀이는 공간복잡도를 포기하면서 시간복잡도를 줄였기 때문에 공간 복잡도도 효율적으로 가져가면서 풀이가 가능할지 또한 추후에 생각해볼 사항인 듯하다.