알고리즘 기법 [메모이제이션]

기법

메모이제이션

 

체감 난이도

골드 3

 

설명

HashMap에 있으면 꺼내서 계산식에 사용
없다면, 계산해서 저장 

 

장점

메모이제이션
한번 계산한건 저장해두고 필요할 때 꺼내쓸 수 있는 것
여러번 계산이 필요할 때, 시간을 단축시킬 수 있다. 

 

코드

import java.util.HashMap;

public class MemoizationExample {
    static HashMap<Integer, Integer> memo = new HashMap<>();

    public static int fibonacci(int n) {
        // 1. 메모에 값이 있으면 반환
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        // 2. 기본 케이스
        if (n == 0) return 0;
        if (n == 1) return 1;

        // 3. 값이 없으면 계산 후 저장
        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);

        return result;
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10)); // 55
    }
}

 

알고리즘 기법을 이용한 문제 풀이 

https://www.acmicpc.net/problem/1351