[99클럽 코테 스터디] 41일차 TIL - N-th Tribonacci Number

Hoxy?·2024년 8월 31일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99클럽 코테 스터디

목록 보기

41/42

오늘의 학습 키워드

</> 동적계획법

공부한 내용 본인의 언어로 정리하기

class Solution {
    public int tribonacci(int n) {
        if(n == 0){
            return 0;
        } else if(n == 1 || n == 2){
            return 1;
        }

        int T0 = 0, T1 = 1, T2 = 1;
        int Tn = 0;

        for(int i = 3; i <= n; i++){
            Tn = T0 + T1 + T2;
            T0 = T1;
            T1 = T2;
            T2 = Tn;
        }
        return Tn;
    } 
}

//트리보나치 수열
// 수열의 정의는 문제에 있음
//n이 주어질때 Tn의 값을 반환하여라
//동적 계획법으로 이전 항 저장하자

오늘의 회고

오늘 문제는 주어진 n의 값을 이용해 트리보나치 공식을 이용해서 Tn의 값을 반환하는 문제였다.

오늘도 동적계획법을 이용하여 풀이했는데 문제를 보니 메모이제이션이 생각나 이전 항을 저장면서 올라가다 보면 n의 결과가 나올것이라 생각하고 진행하였다.

우선 기본적으로 주어진 T0,T1,T2 값을 정의 해주었고, Tn의 값을 0으로 초기화 해주었다.

if(n == 0){
	return 0;
} else if(n == 1 || n == 2){
	return 1;
}
int T0 = 0; T1 = 1; T2 = 1;
int Tn = 0;

기본 케이스와 초기값 설정이 끝났으면 n번째 트라보나치 수를 계산하여야 한다.
앞의 기본 케이스 3개가 있으므로 건너뛰고 진행하기 위해 i는 3부터 시작하고 n의 값이 같아질때 까지만 증가 시켜주도록하고 Tn번째 문제에서 주어진 트리보나치 공식에 따라 작성해주되 이후로 설정되는 값은 n의 값이 증가함에 따라 맞게 적용이 되게 변경시키는 과정을 추가해준다.

for(int i = 0; i <= n; i++){
	Tn = T0 + T1 + T2;
    T0 = T1;
    T1 = T2;
    T2 = Tn;
}

마지막 까지 완료가 되었다면 Tn의 값을 반환해준다.

return Tn;

AI 코드리뷰

현재 코드의 장점

간결함: 코드가 매우 간결하고, 이해하기 쉬운 구조로 작성되어 있습니다.
반복문 사용: 반복문을 사용하여 메모리를 절약하고, 스택 오버플로우 문제를 방지했습니다. 재귀를 사용하지 않아서 스택 메모리 오버헤드가 없습니다.
효율적인 공간 사용: 추가적인 배열을 사용하지 않고, 필요한 변수들(T0, T1, T2)만을 사용하여 공간 복잡도를 최소화했습니다.

현재 코드의 단점

기본 케이스 처리: if-else 블록이 여러 개 나와서 조금 더 가독성을 개선할 수 있습니다. 물론 현재 형태도 나쁘지는 않지만, 코드가 조금 더 세련될 수 있습니다.
불필요한 변수 초기화: Tn 변수를 초기화할 때 int Tn = 0;로 초기화하고 있지만, 이 초기화는 불필요합니다. for 루프 내에서 첫 번째로 Tn이 할당되므로, 초기화할 필요가 없습니다.

시간 복잡도

시간 복잡도: O(n)
for 루프가 n-2번 반복되므로, 시간 복잡도는 O(n)입니다.
공간 복잡도: O(1)
추가적인 배열이나 데이터 구조를 사용하지 않고, 상수 크기의 변수를 사용하기 때문에 공간 복잡도는 O(1)입니다.

개선된 코드 제안

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        int T0 = 0, T1 = 1, T2 = 1;

        for (int i = 3; i <= n; i++) {
            int Tn = T0 + T1 + T2;
            T0 = T1;
            T1 = T2;
            T2 = Tn;
        }
        return T2;
    }
}

개선된 코드의 장점

가독성 향상: Tn 변수를 루프 안에서 선언하여 불필요한 초기화를 제거하고, 변수의 유효 범위를 좁혔습니다. 이는 코드의 가독성을 조금 더 향상시킵니다.
불필요한 변수 제거: Tn 변수를 루프 밖에서 선언하는 대신, 루프 내에서만 사용하도록 하여, 변수가 사용되지 않는 곳에서의 혼동을 줄였습니다.

개선된 코드의 단점