칸비

개발 찍어먹기

[알고리즘]-동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)

개념

복잡한 큰 문제를 여러 개의 작은 문제로 나누어 큰 문제를 푸는 방법이다.

피보나치 수열이 그런 문제이다.

메모제이션

동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장해서 동일한 계산의 반복을 제거하며 실행속도를 빠르게 하는 기술이다. 동적계획법의 핵심 기술이다.

기본적인 피보나치 코드

int fibonacci(int x){
    if(x <= 2) return 1;

    return fibonacci(x-1) + fibonacci(x-2);
}

여기서 x값이 커지면 오버헤드가 커지게된다. 그래서 피보나치 수를 구하면 값을 따로 저장한다.(메모제이션) 메모제이션 안쓴 시간복잡도 O(2^N) 이다. 메모제이션 쓰면 시간복잡도 O(N)으로 엄청 줄게 된다.

메모제이션 쓴 피보나치 코드

int[] data = new int[100];

int fibonacci(int x){

    if(x <= 2) return 1;

    if(data[x] != 0) return data[x];

    else{
        data[x] = fibonacci(x-1) + fibonacci(x-2);
        return data[x];
    }
}

피보나치 수를 구한 값을 data배열에 넣어줘서 똑같은 파라미터(x값)를 불러올 때 data배열만 참고하면 된다.

요약

  • DP에서 메모제이션이 중요하다.
  • 다익스트라 알고리즘을 알아보려고 이걸 포스팅했다.

참고