다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming)

큰 문제를 작은 문제로 쪼개어 해결하는 알고리즘 기법입니다. 이 기법은 작은 문제의 결과를 저장하고, 이를 이용해 큰 문제를 해결합니다. 이를 메모이제이션(Memoization)이라고도 부르며, 일반적으로 재귀적인 방법으로 구현됩니다.

 

다이나믹 프로그래밍은 최적화 문제를 해결하는데 효과적입니다.

예를 들어, 주어진 자원을 최대한으로 활용하여 최대 이익을 얻는 문제, 두 문자열 사이의 최장 공통 부분 문자열을 찾는 문제, 최소 비용으로 목표 지점에 도달하는 경로를 찾는 문제 등에 이용됩니다.

대표적인 다이나믹 프로그래밍 알고리즘

• 피보나치 수열 계산
• LCS(Longest Common Subsequence) 문제

다이나믹 프로그래밍으로 풀 수 있는 문제의 속성

1. 겹치는 부분 문제가 있는 경우 (Overlapping Subproblem)

• 큰 문제를 작은 문제로 쪼갤 수 있는 경우(피보나치 수열)

2. 최적화 부분 구조 (Optimal Substructure)

• 작은 문제를 풀어나감으로써 큰 문제의 정답을 구할 수 있는 경우

다이나믹 프로그래밍을 이용해 피보나치 수 구현해보기

메모이제이션이 없는 함수와 메모이제이션이 있는 함수로 구현할 수 있습니다.

 

메모이제이션이 없는 함수

let Fibonacci = (n) => {
  n > 2 ? Fibonacci(n - 2) + Fibonacci(n - 1) : 1;
};

메모이제이션이 있는 함수(top-down방식)

let fiboArr = [];
let fiboMemoization = (n) => {
  if (n <= 2) {
    fiboArr[n] = 1;
  }
  if (!fiboArr[n]) {
    fiboArr[n] = fiboMemoization(n - 2) + fiboMemoization(n - 1);
  }
  return fiboArr[n];
};

결과의 차이를 n=10으로 했을 때 느껴보자. (원래 10으로 했다가 너무 길어져서 줄였다...)

메모이제이션 미사용
7
5
3
1
2
4
2
3
1
2
6
4
2
3
1
2
5
3
1
2
4
2
3
1
2
======================================
메모이제이션 사용
7
5
3
1
2
4
2
3
6
4
5

이렇게 극명한 차이가 보인다. 

 

메모제이션이 있는 방식2 (bottom-up)

let fiboArr = [];
let fiboBottomUp = (n) => {
  fiboArr[0] = 0;
  fiboArr[1] = 1;
  for (let i = 2; i <= n; i++) {
    fiboArr[i] = fiboArr[i - 1] + fiboArr[i - 2];
  }
  return fiboArr[n];
};

for문을 이용하여 처음부터 더해가는 방식입니다.

 

소감

새로운 알고리즘을 알게 되면 항상 생각하는 것이 있습니다. 대체 어디에 사용해야하는 것일까 입니다. 그래서 좀 찾아봤는데요.

배낭문제(제한된 용량에 가치가 다른 물건을 넣을 때, 가치의 합을 최대화하는 문제), 건물 건설 최적화, 최단 경로 문제(다익스트라) 같은 것에 사용이 된다고 합니다.

뭐 언젠가는 사용하겠죠? 뭔가를 배운다는 것을 즐겁네요.

---

출처

https://velog.io/@jakeseo_me/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EB%A1%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC%ED%95%98%EA%B8%B0-9-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D