[ TIL - PGS ] 99클럽 코테 스터디 21일차 TIL + 오늘의 학습 가이드

💡 오늘의 학습 키워드

• 동적계획법

 

✅ 오늘 공부한 내용

• 오늘의 프로그래머스 문제! 피보나치 수

프로그래머스

 

 

👀 오늘의 회고

🤣 오늘의 문제점

• 재귀를 쓸 때 조건을 잘 세우자!
• 특정 함수명일 때는 통과하고... 아닐 땐 탈락하는 상황이 발생했다 🤔
• fibonachi로 해서 하면 바로 통과인데 함수명을 fibonacci로 하니 테스트 코드 14번에서 런타임 에러가 발생하는...? 이게 무슨 일이지...

import java.util.*;

class Solution {
    private Map<Integer, Integer> map = new HashMap<>();
    
    public int solution(int n) {
        int answer = fibonachi(n) % 1234567;
        return answer;
    }
    
    public int fibonachi(int num){
        if(num == 0) return 0;
        if(num == 1) return 1;
        
        if(map.containsKey(num)){
            return map.get(num);
        }     
        
        int sum = (fibonachi(num - 1) + fibonachi(num - 2)) % 1234567;
        map.put(num, sum);
        return sum;
    }
}

 

🔥 어떤 시도를 했는가?

• 초반에는 간단하게 피보나치 수열 함수를 만들어서 재귀하면 되겠다! 라는 생각을 했다.
• 그런데 return 조건을 초반에 하는 것을 까먹어서 에러가 났다.
• 그 뒤 조건을 다시 맞춰줬는데 시간초과가 발생했다. 아무래도 큰 숫자로 갈 수록 반복되는 횟수 때문이었다.
• Map을 추가하여 시간을 단축했다! 
• 이게 돌아가는 코드가 바로 윗 코드인데..그래도 DP로 풀어야 한다해서 다시 풀어보았다..

 

• 조건은 재귀랑 다르진 않고 대신 구조가 좀 바뀌었다.
• 0과 1일 때는 미리 지정해주고, n만큼 반복해주고 해당 하는 수를 return 해주면 끝이다.
• 확실히 DP로 푸니 메모리와 실행시간이 배로 줄어드는 매직✨을 경험해 볼 수 있었다!

import java.util.*;

class Solution {
    public int solution(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
        }

        return dp[n];
    }
}

 

👏 무엇을 새로 알았는가?

• DP를 써야할 때와 재귀를 써야할 때를 구분할 것!
• 힌트에서 런타임 에러가 13, 14번이 발생하는 이유는 무엇인가요? 하는 프로그래머스 설명이 많이 도움이 되었다.
• 그리고 ChatGPT한테 물어봤는데
  • 재귀 방식은 다양하고 직관적이지만, 중복 계산으로 인해 매우 비효율적이고
  • DP 방식은 중복 계산을 피하고, 각 부분 문제를 한 번만 계산하여 성능을 크게 향상시킨다.
• 라고 설명해주었다. 그래서 큰 입력 값에 따라서는 DP 방식이 훨씬 효율적이라고 설명해주었다!

 

👩‍💻 내일은 무엇을 학습할 것인가?

• 항해99 문제 풀기
• 책 진짜 빡세게 읽기
• 이력서 넣기
• 코드 개선할 거 개선해보기..