[Algorithm] 동적계획법 타파하기 1탄

DP를 상반기에 꼭 타파하자. ✨

1. Memoization 🎶

• 메모이제이션 : DP를 구현하는 방법 중 하나.
• 한 번 구한 결과를 메모배열에 저장하고, 같은 식을 호출하면 메모했던 결과를 그대로 가져오므로써 (캐싱) 계산횟수를 줄여주고, 메모리공간과 시간/비용을 줄일 수 있다.
  • 구했던 것을 다시 구하지 않는다.
• Top - down : 하향식 문제풀이방법
  • 엄밀히 따지면, DP와는 별도의 개념인 메모이제이션
  • 한 번 계산된 결과를 일시적으로 기록하는 것
• Bottom - Up : 상향식 문제풀이방법
  • 재귀호출을 하지 않기 때문에 시간과 메모리 사용량을 줄인다.
  • 단순 반복문을 이용하여 문제를 해결하는 것.

 

package hijpa;

import java.io.*;
import java.util.*;

public class Main {
    static int[] memo;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        memo = new int[46];
        System.out.println(fibo(n));

    }

    private static int fibo(int n) {
        if(n==0){
            return 0;
        }
        if(n==1 || n==2){
            return 1;
        }
        if(memo[n]!=0){
            return memo[n];
        }else{
            memo[n] = fibo(n-1)+fibo(n-2);
            return memo[n];
        }
    }
}