๐Ÿ”ฅ[99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋””] 21์ผ์ฐจ TIL - ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜

HOONSSACยท2024๋…„ 8์›” 11์ผ
1

99Club Coding Test Study

๋ชฉ๋ก ๋ณด๊ธฐ
21/41
post-thumbnail

โณ๋ฌธ์ œ

ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๋Š” F(0) = 0, F(1) = 1์ผ ๋•Œ, 1 ์ด์ƒ์˜ n์— ๋Œ€ํ•˜์—ฌ F(n) = F(n-1) + F(n-2) ๊ฐ€ ์ ์šฉ๋˜๋Š” ์ˆ˜ ์ž…๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด

  • F(2) = F(0) + F(1) = 0 + 1 = 1
  • F(3) = F(1) + F(2) = 1 + 1 = 2
  • F(4) = F(2) + F(3) = 1 + 2 = 3
  • F(5) = F(3) + F(4) = 2 + 3 = 5

์™€ ๊ฐ™์ด ์ด์–ด์ง‘๋‹ˆ๋‹ค.

2 ์ด์ƒ์˜ n์ด ์ž…๋ ฅ๋˜์—ˆ์„ ๋•Œ, n๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๋ฅผ 1234567์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ๋ฆฌํ„ดํ•˜๋Š” ํ•จ์ˆ˜, solution์„ ์™„์„ฑํ•ด ์ฃผ์„ธ์š”.

์ œํ•œ ์‚ฌํ•ญ

  • n์€ 2์ด์ƒ 100,000 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

nreturn
32
55

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

ํ”ผ๋ณด๋‚˜์น˜์ˆ˜๋Š” 0๋ฒˆ์งธ๋ถ€ํ„ฐ 0, 1, 1, 2, 3, 5, ... ์™€ ๊ฐ™์ด ์ด์–ด์ง‘๋‹ˆ๋‹ค.


โœ๏ธํ’€์ด

์ฒซ ๋ฒˆ์งธ ์‹œ๋„

์šฐ์„ , ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์˜ ๊ณต์‹ F(n) = F(n-1) + F(n-2)๋ฅผ ํ™œ์šฉํ•ด ์žฌ๊ท€ํ•จ์ˆ˜๋กœ ๊ตฌํ˜„์„ ํ•ด๋ณด์•˜๋‹ค.

class Solution {
    
    public int fb(int n) {
        if (n <= 2) {
            return 1;
        }
        else {
            return fb(n - 1) + fb(n - 2);
        }
    }
    
    
    public int solution(int n) {
        int answer = 0;
        
        answer = fb(n) % 1234567;
        
        return answer;
    }
}

์—ญ์‹œ๋‚˜ ์ˆซ์ž๊ฐ€ ์ปค์ง์— ๋”ฐ๋ผ ์‹คํ–‰ ์‹œ๊ฐ„์ด ๊ธฐํ•˜๊ธ‰์ˆ˜์ ์œผ๋กœ ๋Š˜์–ด๋‚˜๋ฉด์„œ, ์‹œ๊ฐ„์ดˆ๊ณผ๋ฅผ ์•ผ๊ธฐํ–ˆ๋‹ค.

๋‘ ๋ฒˆ์งธ ์‹œ๋„

์ด๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ๋™์  ๊ณ„ํš๋ฒ•(Dynamic Programming)์„ ์ ์šฉํ•ด๋ณด๊ธฐ๋กœ ํ•˜์˜€๋‹ค.

class Solution {
    
    
    public int solution(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n] % 1234567;
    }
}

dp๋ผ๋Š” ๋ฐฐ์—ด์„ ํ•˜๋‚˜ ๋งŒ๋“ค์–ด, ์•ž์—์„œ๋ถ€ํ„ฐ ๊ณ„์‚ฐํ•œ ๊ฐ’๋“ค์„ ์ €์žฅํ•ด๋‚˜๊ฐ€๋ฉด, ์ค‘๋ณต๋˜๋Š” ๊ณ„์‚ฐ์„ ์ค„์ผ ์ˆ˜๊ฐ€ ์žˆ๋‹ค.
์ด๋ฅผ ๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ์˜ ๊ธฐ๋ฒ• ์ค‘ Memoization์ด๋ผ๊ณ  ํ•œ๋‹ค.

๋™์  ๊ณ„ํš๋ฒ•์„ ์‚ฌ์šฉํ•˜๋‹ˆ ์‹œ๊ฐ„ ์ดˆ๊ณผ๋Š” ํ”ผํ•  ์ˆ˜ ์žˆ์—ˆ์ง€๋งŒ, ๋ช‡ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์—์„œ ์‹คํŒจ๊ฐ€ ๋ฐœ์ƒํ•˜์˜€๋‹ค.

์•Œ๊ณ  ๋ณด๋‹ˆ, n์ด ๋งค์šฐ ํฐ ๊ฒฝ์šฐ n๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๊ฐ€ ์ž๋ฃŒํ˜•์˜ ๋ฒ”์œ„๋ฅผ ๋„˜์–ด๊ฐˆ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์˜ค๋ฒ„ํ”Œ๋กœ์šฐ๊ฐ€ ๋ฐœ์ƒํ•œ ๊ฒƒ์ด๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, 47๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๋Š” 2,971,215,073์ด๊ณ , ์ด ์ˆ˜๋Š” 32๋น„ํŠธ ์ •์ˆ˜(ex. int) ๋ฒ”์œ„๋ฅผ ๋„˜์–ด ์˜ค๋ฒ„ํ”Œ๋กœ์šฐ๊ฐ€ ๋ฐœ์ƒํ•˜๊ฒŒ ๋œ๋‹ค.

๐Ÿ‘พ์ตœ์ข… ์ฝ”๋“œ

๋ฌธ์ œ ์กฐ๊ฑด์€ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๋ฅผ 1234567๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ๊ฒƒ์ธ๋ฐ, ์ตœ์ข… return๋ฌธ์—์„œ 1234567๋กœ ๋‚˜๋ˆ ์ฃผ๋Š” ๋Œ€์‹ , ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜๊ณ  dp๋ฐฐ์—ด์— ์ €์žฅํ•  ๋•Œ ๋งค๋ฒˆ 1234567๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ €์žฅํ•˜๋„๋ก ์ˆ˜์ •ํ•ด์คŒ์œผ๋กœ์จ, ์ด๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค!

class Solution {
    
    
    public int solution(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
        }
        
        return dp[n];
    }
}


๐Ÿ”—๋ฌธ์ œ ๋งํฌ
๐Ÿ’ปRepository

profile
ํ›ˆ์‹น์˜ ๊ฐœ๋ฐœ์—ฌํ–‰

2๊ฐœ์˜ ๋Œ“๊ธ€

comment-user-thumbnail
2024๋…„ 8์›” 11์ผ

์ฐจ๊ทผ์ฐจ๊ทผ ๋ฌธ์ œ ํ•ด๊ฒฐ...! ๋ฉ‹์žˆ์–ด์š”

1๊ฐœ์˜ ๋‹ต๊ธ€