📢이전에 파이썬 버전으로 정리한 것이 있으므로, 자세한 내용은 코딩테스트-올인원[파이썬 버전]을 참고하시기 바랍니다.

🤩기존의 피보나치 top-down, bottom-up을 자바 버전으로 구현해보았다👇

💻피보나치 Top-down 코드 구현

public class Fibonacci {
    public int fib(int n) {
        HashMap<Integer, Integer> memo = new HashMap<>();
        return dp(n, memo);
    }

    private static int dp(int n, HashMap<Integer, Integer> memo) {
        // base condition
        if (n <= 1) {
            return n;
        }
        // n이 메모리에 없으면 재귀 함수를 호출
        if (!memo.containsKey(n)) {
            memo.put(n, dp(n - 1, memo) + dp(n - 2, memo));
        }
        // n이 메모리에 있으면 메모리에 있는 value를 리턴
        return memo.get(n);
    }

• 대부분 코테 문제에서는 메서드 시그니처가 문제 그대로 주어지기 때문에 dp 재귀 함수를 따로 구현해야 한다.
  • 파이썬에서는 closure 기능이 있어서 부모 메서드의 지역 변수를 그대로 사용할 수 있지만, 자바는 type-strict한 컴파일러 언어라 해시맵을 재귀 함수 파라미터로 전달하였다.
    • 해시맵으로 초기화한 이유는 n에 따라 value가 달라지기 때문
  • 내부 헬퍼 메서드는 인스턴스 변수에 의존하지 않으므로 static으로 선언하였다.

🔎참고로, dp를 int[] dp = new int[n + 1];과 같이 배열로 선언할 수도 있지만, value가 음수값으로 주어질 수도 있으므로 해시맵으로 초기화하는 것이 더 효율적이라고 한다.

💻피보나치 Bottom-Up 코드 구현

public class Fibonacci {
    public int fib(int n) {
        int[] table = new int[n + 1]; // 배열은 0부터 시작하므로 1을 더해줘야함
        return bottomUp(n, table);
    }

    private static int bottomUp(int n, int[] table) {
        // base condition
        table[0] = 0;
        table[1] = 1;

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

        return table[n];
    }

• 배열은 0부터 시작하기 때문에 테이블을 n+1의 크기로 할당하였다.
• $F(n) = F(n-1) + F(n-2) (n >= 2)$의 점화식을 따르므로, 시작은 2부터 하였다.
• for문에서 조건식을 n + 1로 한 이유는, 결국에는 테이블을 n까지 채워야 하기 때문이다.

⚙️구현 방법

⚠️개념을 아무리 충실히 이해했다고 해도, 완전탐색부터 DP 문제라고 파악하기까지 오래걸리기 때문에 문제를 많이 풀어보는 수 밖에 없음!

1. 일단 재귀함수로 비효율적인 완전탐색 코드를 작성
2. 중복되는 subproblem의 계산 결과를 저장(memoize)

👎3. Top-down -> Bottom-up으로 코드 전환을 고려
👉입력 크기, 성능, 공간 최적화가 필요할 때만 고려

📝몰론 Bottom-up의 table로 사용되는 base condition을 해시맵으로 구현해도 상관없다.
다만, 개인적인 견해로는 코테용으로 DP를 풀 때 Top-down으로 풀리는 문제를 굳이 최적화를 위해서 Bottom-up으로 코드를 migrate를 할 필요는 없다고 본다.(심지어 하드웨어 성능이 좋기 때문에 공간 복잡도를 고려할 필요도 없다.)
👍가장 중요한 점은, 대부분의 점화식(reccurence relation)은 재귀를 활용한 Top-down으로 구현되기 때문에 직관적인 풀이로 빠르게 문제를 풀고 싶다면 Top-down을 고수해도 문제없다!

🍯문제에서 dp로 풀라는 힌트들

• 최대 최소, 방법의 개수 등을 구할 때
  • 예) ~의 최소 비용은?, ~의 최대 이익은?, ~를 하는 방법의 개수는?, What is the longest possible..?, 특정 지점에 도달할 수 있는지?