동적 계획법 (Dynamic Programming)

1. 정의
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다

2. 원리
일반적으로 주어진 문제를 풀기 위해,
문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것
각 하위 문제를 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단히 해결
->계산 횟수 감소
문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아냄

3. 예시1 : 피보나치 수열

<일반적인 코드>

int fibo(int n){
    if(n<=1)
        return n;
    else
        return fibo(n-2)+fibo(n-1);
}

<동적 계획법이 적용된 코드>
중복되는 계산이 있고, 이것은 전체적인 계산 속도를 떨어뜨린다
위 일반적인 경우의 코드의 시간 복잡도는 지수 함수가 된다
각 함수의 계산값을 배열이나 list에 넣어주면
계산 시간이 절약된다

int cachedfibo(int n){
    if(n<=1)
        return n;
    if(cached[n]!=0)
        return cached[n];
    cached[n]=cachedfibo(n-1)+cachedfibo(n-2);
    return cached[n];
}

위와 같이 반복되는 계산을 막기위해 이전에 계산한 값들을 저장하는 방법이 바로 동적 프로그래밍


앞으로 알고리즘 수업에선 계속 자바를 사용할 것(그게 마음 편할듯 하다)인데,
위의 예시처럼 cached의 배열에서 n값으로 접근을 하며
문제를 푸는게 좋을듯 하다

이번 포스팅은 너무 짧지만, 해결해야하는 알고리즘 수업 과제가 있어
길게 못 적을듯 하다...

흑흑


이번 포스팅 : 동적 계획법에 대한 간단한 원리와 예시
다음 포스팅 : 스트링을 다루는 법이나, 다른 알고리즘에 대해서