[알고리즘] 동적 프로그래밍 (JS)

📌 참고 사이트

동적 계획법 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

동적 계획법 - 위키백과, 우리 모두의 백과사전

 

 

 

📋 동적 프로그래밍 (Dynamic Programming)

📍 동적 프로그래밍 문제의 특징

➡️ 주어진 문제를 풀기 위해 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다.

 

➡️ 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있게 하여 계산 횟수를 줄일 수 있는 방법이다. 따라서 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

 

➡️ 동적 프로그래밍을 이용한 대표적인 알고리즘으로는 주어진 시작점과 다른 점들 사이의 가장 짧은 경로를 찾아내는 알고리즘인 데이크스트라 알고리즘과 배낭에 담을 수 있는 무게의 최댓값이 정해져 있을 때 그 배낭에 담을 수 있는 짐의 무게가 최대가 되도록 하는 방법을 찾는 배낭 문제 등이 있다.

 

 

❓ 동적 프로그래밍과 그리디 알고리즘

동적 프로그래밍 바식은 가능한 모든 방법을 고려해야 한다는 단점이 있다. 그것을 극복하기 위해 그리디 알고리즘이 등장했다. 

그리디 알고리즘은 항상 최적해를 구해주지는 않지만 최소 신장 트리 문제 등에서는 항상 최적해를 구하는 것이 가능하다.

 

A라는 지점에서 B라는 지점까지 가능한 빨리 이동하는 경로를 찾고 싶다고 할 때, 동적 계획법과 그리디 알고리즘을 사용하면 각각 아래와 같이 된다.

➡️ 동적 계획법 : 갈 수 있는 모든 상황과 교통 정체를 전부 감안해 최적의 경로를 찾아냄.

➡️ 그리디 알고리즘 : 전체적인 상황을 고려하지 않고, 순간순간 교차로가 보일 때마다 가장 빠른 경로를 검색하여 찾아줌.

 

위와 같은 경우 동적 계획법으로 경로를 검색하면 시간이 좀 걸리지만 우리가 갈 수 있는 가장 빠른 길이 된다고 장담이 가능하다.

but 그리디 알고리즘은 즉각즉각 빠른 경로를 찾아주므로 시간적으로 효율이 있을 수도 있겠지만 그것이 항상 전체적인 최적의 경로라고 장담할 수는 없다.  

 

 

💻 동적 계획법 적용해 보기

피보나치 수열에서 동적 프로그래밍 방법을 적용하면 O(n)의 시간 복잡도를 가지게 할 수 있다.

 

보통의 재귀를 이용한 피보나치 수열 코드는 다음과 같이 된다.

 

function fib(n) {
 if (n === 0) return 0
 else if (n === 1) return 1
 else return fib(n-1) + fib(n-2) 
}

 

동적 계획법을 이용한 코드는 다음과 같이 작은 수에서의 피보나치 수열 하나를 구할 때마다 객체에 기록하여 후에 큰 수의 피보나치 수열을 구할 때 사용하는 것이다.

 

const record = { 0: 0, 1: 1 };

function fibo(n) {
  if (Object.keys(record).includes(n.toString())) {
    return record[n];
  } else {
    record[n] = fibo(n - 1) + fibo(n - 2);
    return record[n];
  }
}

console.log(fibo(num));     // 5
console.log(record);     // { '0': 0, '1': 1, '2': 1, '3': 2, '4': 3, '5': 5 }

 

아래 글에서 피보나치 문제 참고하기!

 

[알고리즘] 재귀 (JS) (tistory.com)

[알고리즘] 재귀 (JS)