LeetCode 1137. N-th tribonacci number

728x90

출처: leetcode.com

이 문제는 피보나치 수열을 약간 변형한 tribonacci 수열에서 N번째 수를 찾는 것이다. 피보나치 수열은 정의도 간결하고 솔루션도 간단해 동적 프로그래밍(dynamic programming, DP)을 공부하기 좋은 기본 예제이다. 또한, 이 문제는 DP의 적용 효과를 뚜렷하게 보여주는 문제이기도 하다. 두 가지 방법으로 코딩을 해보았다. 

solution 1: brute force 

첫 번째 방법은 brute force로 N번째 수를 결정하는 뒤의 세 개의 수를 중복해서 찾는다. 직관적이고 tribonacci 수열의 정의에 충실하지만 아주 비효율적이다. 이 방법으로 leetcode에서 서밋을 한다면 Time Limited Error를 낸다. 문제를 처음 대할때는 레퍼런스로 삼기위해 공부차 한 번 시도해 볼 수 있겠다. 

def tribonacci_bruteForce(n):
    if n == 0:
        return 0
    
    if n == 1 or n == 2:
        return 1 
    
    return tribonacci_bruteForce(n-3)+tribonacci_bruteForce(n-2)+tribonacci_bruteForce(n-1)
            
        

 

다음과 같이 실행하고 걸린 시간을 출력해 볼 수 있다. 30번째 수를 찾는데 12초가 걸렸다. 

start = time.time()
for i in range(30):
    print(i, tribonacci_bruteForce(i))
    
print("")
print("elapsed time: ",(time.time() - start),"s")

# 결과 

0 0
1 1
2 1
3 2
4 4
5 7
6 13
7 24
8 44
9 81
10 149
11 274
12 504
13 927
14 1705
15 3136
16 5768
17 10609
18 19513
19 35890
20 66012
21 121415
22 223317
23 410744
24 755476
25 1389537
26 2555757
27 4700770
28 8646064
29 15902591

elapsed time:  12.47270393371582 s

solution 2: DP approach 

두 번째 방법은 찾은 수를 기억하며 진행하는 DP방법이다. 아래의 코드에서 볼 수 있듯이 수를 찾기 위해서는 바로 전의 세 개의 수만 기억하고 있으면 된다. 이것을 tri라는 배열에 저장하고 업데이트 해 나간다. 그래서 원하는 N번째 수까지 찾고 종료하면 된다. 

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0: 
            return 0
        if n == 1 or n == 2:
            return 1
        
        tri=[0,1,1]
        
        for _ in range(3,n+1):
            tri[0],tri[1],tri[2] = tri[1],tri[2],sum(tri)
        
        return tri[-1]

실행해보면 걸린 시간이 약 0.002초로 약 만 배가 빨라진 것을 볼 수 있다. 

import time

start = time.time()
for i in range(30):
    print(i, tribonacci(i))
    
print("")
print("elapsed time: ",(time.time() - start),"s")

# 실행결과 

0 0
1 1
2 1
3 2
4 4
5 7
6 13
7 24
8 44
9 81
10 149
11 274
12 504
13 927
14 1705
15 3136
16 5768
17 10609
18 19513
19 35890
20 66012
21 121415
22 223317
23 410744
24 755476
25 1389537
26 2555757
27 4700770
28 8646064
29 15902591

elapsed time:  0.002290964126586914 s