99클럽 코테 스터디 19일차 TIL + 재귀호출, 메모이제이션, [leetcode] Fibonacci Number

✨ 문제 

Fibonacci Number

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

https://leetcode.com/problems/fibonacci-number/description/

 

 

 

✨ 개념

재귀호출 recursion

- 문제를 더 작은 문제로 나누어 함수가 자기 자신을 호출하는 프로그래밍 기법.

- 중복 계산이 많아 비효율적일 수 있음.

 

메모이제이션 memoization

- 이미 계산한 결과를 저장하여 동일한 계산을 반복하지 않도록 하는 기법.

- 메모이제이션을 통해 재귀 호출의 단점을 보완할 수 있음.

- 메모이제이션 사용 시 각 하위 문제를 한번만 계산하고, 이후에는 저장된 값을 재사용함.

 

동적 프로그래밍에서 재귀호출과 메모이제이션을 사용하면 문제를 효율적으로 해결할 수 있음.

 

 

✨ 최종코드

class Solution {
    private Map<Integer, Integer> memo = new HashMap<>();

    public int fib(int n) {
        if (n <= 1)
            return n;

        if (memo.containsKey(n))
            return memo.get(n);

        int result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);

        return result;
    }
}