99클럽 코테 스터디 24일차 TIL DP 예제

DP; Dynamic Programming 동적 계획법 예제

• 피보나치 수를 구하는 함수에 DP 알고리즘 적용하기
• 피보나치수열 알고리즘은 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있는 최적 부분 구조로 이루어져 있음
• DP 알고리즘을 적용하기 좋은 예제 중 하나임

 

• 1. recursive 방식
  • 함수의 호출을 이용한 재귀적 방법
  • 재귀적 구조는 엄청난 중복 호출이 발생할 수 있으므로 내부에 시스템 호출 스택을 사용하는 overhead가 발생할 수 있음

•  

public int fib_recursive(int n) {
    if (n <= 1) {
        return n;
    }
    return fib_recursive(n - 1) + fib_recursive(n - 2);
}

 

• 2. iterative 방식 (memoization 개념 활용)
  • 반복문을 이용한 반복적 방법
  • Memoization을 반복적 구조에 사용하여 DP 알고리즘을 구현하는 것이 위의 재귀적 구조에 비해 실행 속도와 성능 면에서 보다 효율적
  • 이전에 계산해 놓은 피보나치 수를 배열에 저장해 놓으면, 인덱스로 바로 접근할 수 있다.

public static int fib_memoization(int n) {
    int[] fibo = new int[n + 1];

    if (n <= 1) {
        return n;
    }

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

    return fibo[n];
}

 

728x90

느낀 점

• 재귀는 depth 가 한없이 깊어질 수 있으므로 주의해서 사용해야 한다.
• memoization을 활용하여 효율이 좋은 코드를 짜도록 해야겠다.

다음에 학습할 것

• 메모이제이션에 대하여

반응형

---

DP 동적계획법의 예제를 풀어보았다. 중요한 개념이므로 확실히 알고 넘어가자.