[c++] 알고리즘 설계 기법 | DP(다이나믹 프로그래밍)

[DP(다이나믹 프로그래밍, 동적 계획법)]

 

• 큰 문제에 대한 답을 얻기 위해 동일한 문제지만, 크기가 작은 문제들을 먼저 해결하는 방법이다.

 

 

 

 

 

 

 

• 항상 점화식을 사용한다.
  • 점화식 : 수열의 일반항을 한 개 이상의 앞선 항들을 이용하여 나타낸 식 즉 전에 구했던 것들을 통해서 현재 값을 구하는 방법이다.
• Memoization(메모이제이션) 기법
  • 중간 계산 결과들을 따로 저장해 두어서 중복 연산을 피하는 기법이다.
  • 피보나치 수열은 점화식이기 때문에 전에 구했던 값을 통해 현재 값을 구한다. 즉 메모이제이션 기법을 활용하여 점화식을 풀면 구했던 값을 또 구하는 것이 아닌 전에 구했던 값을 가져오면 되기 때문에 불필요한 연산을 줄일 수 있다!

F[n]에 해당하는 값을 저장한 배열

 

 

• Memoization(메모이제이션) 기법을 사용해서 구현한 피보나치 수열

#include <iostream>
using namespace std;

int fibo[46] = { 0,1,1 }; // 구해진 피보나치 수들을 저장하는 배열
int f(int n)
{
    // n이 2보다 작거나 배열 값이 0이 아니라면 이미 구해진 수 이기 때문에 구해진 수를 반환
    if (n <= 2 || fibo[n] != 0) return fibo[n];
    fibo[n] = f(n - 1) + f(n - 2);
    return fibo[n];
}

int main(void)
{
    int n;
    cin >> n;
    cout << f(n);

    return 0;
}

 

 

[최장 증가 부분 수열(LIS)]

• 부분 수열
  • 주어진 수열 중 일부를 뽑아 새로 만든 수열이다.
  • 이때 각각의 원소의 전후 관계를 유지 해야한다.
• 최장 증가 부분 수열
  • 부분 수열의 원소가 오름차순을 유지하면서도 길이가 가장 긴 수열이다.

 

[최장 공통 부분 수열(LCS)]

• 양쪽에서 공통으로 발견할 수 있는 가장 긴 부분 수열이다.