DP - Dynamic Programming

기술면접을 위해 기초 CS에 대한 복습중이다.
공부한 내용 중 요점이나 나중에 기억해야할 부분을 정리해보려고 한다.
내가 아는 부분은 생략되어 있을 수 있고, 혹여나 틀린 부분이 있을 수도 있으니 이 글을 보고 '다른 사람'이 공부하기에는 도움이 되지 않을 수 있으니 주의!

다이나믹 프로그래밍

• 피보나치 수열처럼 점화식 풀 때 사용한다.
• 이미 계산한 것은 다시 계산을 하지 않게끔 하는 것이 목적이다.
• 탑다운과 보텀업 방식이 있다.
• 보텀업: DP 테이블을 만들어서 하는 방식.

    // 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
    d[1] = 1;
    d[2] = 1;
    int n = 50; // 50번째 피보나치 수를 계산
    // 피보나치 함수(Fibonacci Function) 반복문으로 구현
    for (int i = 3; i <= n; i++) {
        d[i] = d[i - 1] + d[i - 2];
    }
    cout << d[n] << '\n';

• 탑다운: 한 번 계산된 결과는 메모이제이션(Memoization)하는 방식.

    long long fibo(int x) {
        // 종료 조건(1 혹은 2일 때 1을 반환)
        if (x == 1 || x == 2) {
            return 1;
        }
        // 이미 계산한 적 있는 문제라면 그대로 반환
        if (d[x] != 0) {
            return d[x];
        }
        // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
        d[x] = fibo(x - 1) + fibo(x - 2);
        return d[x];
    }

다이나믹 프로그래밍 VS 분할 정복

• 공통점: 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제를 모아 큰 문제를 풀 수 있다.
• 차이점: DP는 부분 문제가 중복되지만, 분할 정복은 동일 문제가 반복되지 않는다.

DP 문제에 접근하는 방법

• 문제를 풀 때 가장 먼저 그리디, 구현, 완전 탐색 등으로 생각해보고, 너무 많은 시간 복잡도가 소요된다고 생각이 들면 다이나믹을 고려해본다.
• 부분 문제가 반복적이고, 작은 문제에서 구한 답이 큰 문제에 그대로 사용될 수 있다면 DP일 가능성이 높다.
• DP의 2가지 조건: 최적 부분 구조, 중복되는 부분 문제
• DP 테이블에는 구하고자 하는 값을 인덱스마다 차례로 넣는다.
• 점화식 만들기: $x-1$이나 $x-k$ 이런 식으로 어떤 특정 위치에서 직전 계산을 이용할 수 있도록 구현해야 한다.

LIS (Longest Increasing Subsequence)

• 특정 위치 v[i]를 마지막 값으로 하는 부분 수열에 대해서 LIS를 구한다.

  // 오름차순 조건을 만족한다면
  if(v[j] < v[i])
    // 현재까지의 LIS 값과 v[j] 위치에서의 LIS에 v[i]까지 더한 값,
    // 즉, d[j] + 1과 비교한다.
    d[i] = max(d[i],d[j] +1)

※ Vector 문법

// 크기는 3, 모든 값은 10000으로 초기화
vector<int> v(3, 10000);

// 거꾸로 뒤집기
reverse(v.begin(), v.end());

---

참고한 사이트

• 나동빈님 유튜브: 이코테 2021 강의
• 나동빈님 Github: 이코테 소스코드 저장소