99클럽 스터디 코테 스터디 41일차 TIL (N-th Tribonacci Number) - LeetCode

말하는 감자·2024년 8월 31일

99클럽 99클럽3기 dynamic programming leetcode python 동적 프로그래밍 코딩테스트 코딩테스트 준비 파이썬 향해99

99클럽 3기

목록 보기

41/42

99클럽 코테 스터디 41일차입니다. 내일이 99클럽 코테 스터디의 마지막이군요.. 오늘 문제를 확인해볼까요?

1. 오늘의 학습 키워드

Dynamic Programming

2. 문제: 1137. N-th Tribonacci Number

단계: Easy
주제: Math, Dynamic Programming, Memoization

1137. N-th Tribonacci Number

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25
Output: 1389537

Constraints:

0 <= n <= 37
The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

3. 나의 풀이

문제 접근

이번 문제는 Tribonacci 수열을 계산하는 문제로, 주어진 숫자 n에 대해 Trinacci 수열의 Tn 값을 구하는 것입니다. Trinacci 수열은 피보나치 수열과 비슷하지만, 이전 세 개의 수의 합으로 다음 수를 계산하는 점이 다릅니다. 문제는 수열의 초기값으로 주어진 T0, T1, T2를 이용하여 Tn을 계산하도록 요구합니다.

이 문제를 해결하기 위해서 동적 프로그래밍(Dynamic Programming) 접근 방식을 사용할 수 있습니다. 동적 프로그래밍은 하위 문제를 먼저 해결하고 그 결과를 저장하여, 상위 문제를 해결할 때 반복된 계산을 피할 수 있도록 하는 방법입니다. 이 문제에서 dp 배열을 이용하여 계산된 Trinacci 수열 값을 저장하고, 이후 값을 효율적으로 계산할 수 있습니다.

코드 분석

다음은 문제를 해결하기 위한 코드입니다:

class Solution(object):
    def tribonacci(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0:
            return 0
        elif n == 1 or n == 2:
            return 1

        dp = [0] * (n+1)
        dp[1] = 1
        dp[2] = 1

        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

        return dp[n]

기본 조건 처리

n == 0인 경우 Trinacci 수열의 첫 번째 값 T0이므로 0을 반환합니다.
n == 1 또는 n == 2인 경우 Trinacci 수열의 초기 값 T1과 T2는 1이므로 1을 반환합니다.

이러한 기본 조건들은 수열의 시작 값을 정의하며, 이를 통해 dp 배열의 초기값을 정확하게 설정할 수 있습니다.

동적 프로그래밍 배열 초기화

dp 배열을 n+1 크기로 초기화합니다. 이 배열은 Tn 값을 저장하는데 사용됩니다.
dp[1]과 dp[2]는 1로 설정됩니다. 이 값들은 수열의 정의에 따라 초기값으로 주어집니다.

동적 프로그래밍을 통한 값 계산

n이 3 이상일 때, dp 배열을 순차적으로 채워나갑니다. Tn은 dp[i-1] + dp[i-2] + dp[i-3]로 계산됩니다. 이 방식은 이전 세 값의 합을 이용하여 현재 값을 구하는 방식입니다.

최종 결과 반환

dp[n]을 반환하여 n번째 Trinacci 수열 값을 결과로 반환합니다.

이 코드는 효율적으로 Trinacci 수열을 계산하기 위해 동적 프로그래밍을 활용하고 있으며, 문제의 조건을 충족하는 방식으로 설계되었습니다. n의 크기가 최대 37이므로, 이 방식은 충분히 효율적이고, 메모리 사용도 최적화되어 있습니다.

여기서 제가 초반에 했던 실수들이 있습니다.

코드를 다시 한 번 살펴보면, dp 배열은 크기가 n+1로 초기화됩니다. 그러나 n이 0, 1, 또는 2일 때 기본 조건을 생략하면, 다음과 같은 상황이 발생합니다:

n = 0일 때:
- dp 배열의 크기는 n + 1 = 1로 초기화됩니다. 이 경우 dp[1]과 dp[2]에 접근하려고 하면 배열의 크기를 넘어가게 되어 IndexError가 발생합니다.
n = 1일 때:
- dp 배열의 크기는 n + 1 = 2로 초기화됩니다. 이 경우 dp[2]에 접근하려고 하면 배열의 크기를 넘어가서 IndexError가 발생합니다.
n = 2일 때:
- dp 배열의 크기는 n + 1 = 3으로 초기화됩니다. 이 경우에는 dp[2]까지 접근할 수 있으므로 에러가 발생하지 않지만, 기본 조건이 없다면 잘못된 로직이 적용될 수 있습니다.

이 문제를 피하기 위해서는 n이 0, 1, 2인 경우에 대해 미리 값을 반환하는 기본 조건이 필요합니다. 이 기본 조건을 추가함으로써 dp 배열에 접근하기 전에 이러한 경우를 처리할 수 있어, 배열 크기 문제로 인한 IndexError를 피할 수 있습니다.

따라서 기본 조건을 생략할 경우 dp 배열이 너무 작게 초기화되어 발생하는 인덱스 오류를 방지하기 위해 기본 조건이 꼭 필요합니다.

결과

https://leetcode.com/problems/n-th-tribonacci-number/submissions/1373896679

마무리

이번 문제는 동적 프로그래밍을 활용하여 Trinacci 수열을 계산하는 방법을 다뤘습니다. 동적 프로그래밍은 반복되는 계산을 피하고 효율적으로 문제를 해결할 수 있는 강력한 도구입니다. 이 문제를 통해 작은 문제부터 시작하여 점차 큰 문제를 해결하는 방식에 익숙해질 수 있었으며, 이는 다양한 알고리즘 문제에서 중요한 기초가 됩니다.

내일은 99클럽 코테 스터디의 마지막 날입니다. 그동안의 노력이 결실을 맺는 순간이니 끝까지 최선을 다해 봅시다! 함께 성장해온 이 시간이 큰 자산이 되길 바랍니다. 끝까지 파이팅입니다!