✅ 동적 프로그래밍

자몽·2021년 8월 1일
1

알고리즘

목록 보기
8/31

서론

동적 프로그래밍. 영어로는 Dynamic Programming 이라고 부른다.
실제로 제작자는 멋있어서 이렇게 이름을 지었다고
근데 이해가 가는게 동적 프로그래밍은 가히 획기적으로 할 수 있을 만큼 연산을 줄여주는 알고리즘이다.

동적 프로그래밍이 어떻게 동작하길래 연산을 줄여주는지 지금부터 알아보도록 하자.

재귀 함수 vs 동적 프로그래밍

피보나치는 대표적인 재귀 함수를 사용해 풀 수 있는 문제이다.
코드는 다음과 같다.

const fibo=(n)=>{
  if(n<=2) return 1;
  return fibo(n-2) + fibo(n-1);
}
fibo(5)

코드를 이렇게 짠다면, fibo(5)에서부터 fibo(0)에 이르기까지 나무를 그려 연산 과정을 거친다.

하지만 이렇게 간단해 보이는 재귀적 용법에도 한가지 문제가 존재했다.
바로, 연산을 너무 많이 해야 한다는 문제였다.
위의 사진을 보면, fibo(3)아래의 트리는 구성, 생김새가 모두 동일하다.

이러한 반복을 피하기 위해 만들어진 알고리즘이 바로
동적 프로그래밍이다.

동적 프로그래밍

  • 동적 프로그래밍은 아래의 그림처럼 중복되는 부분을 미리 저장시켜두고 사용하는 알고리즘 기법이다.
    • 팁: 우선 Tree 구조를 그린다. Tree 구조에 맞춰서 재귀적 용법으로 코드를 짠 후, 동적 프로그래밍으로 최종적으로 코드를 바꾼다.

피보나치


우선 같은 피보나치 함수 코드가 어떻게 바뀌었는지 먼저 보겠다.

const fibo=(n,memo={})=>{
  if(n in memo) return memo[n];
  if(n<=2) return 1;
  memo[n] = fibo(n-1,memo) + fibo(n-2,memo);
  return memo[n];
};
fibo(5)

기존에는 Top(fibo(5)) -> Down(fibo(0))으로 연산을 진행했다면,

동적 프로그래밍은 반대로 Down -> Top으로 작은 것부터 연산을 진행한다.

따라서 Down에서 이미 연산한 부분들을 그대로 써야 할 필요가 있는데,
이는 memo={}에 저장함으로써 문제를 해결한다.

중복되는 부분을 미리 연산해두면 연산 과정은 이렇게나 짧아진다.

길 찾기

문제: m x n의 길이를 가지고 있는 사각형이 있다.
좌측 상단에서 우측 하단까지 갈 수 있는 경우의 수를 구하시오.

  • 트리 구조 그리기
    m=3, n=2라고 했을 때,

    다음과 같이 트리 구조를 짤 수 있다.

  • 재귀 함수로 표현하기

const route = (m, n)=>{
  if(m===1 && n===1) return 1;
  if(m===0 || n===0) return 0;
  return route(m-1, n) + route(m, n-1);
}
route(3,2);
  • 동적 프로그래밍 사용하기
    A(2,1)아래가 모두 반복되므로 이번에도 memo를 사용해 저장한다.
const route = (m, n, memo={})=>{
  const key = m + ',' + n;

  if(key in memo) return [key];
  if(m===1 && n===1) return 1;
  if(m===0 || n===0) return 0;

  memo[key] = route(m-1, n) + route(m, n-1);
  return memo[key];
}
route(3,2);

key를 m과 n으로 하여 사용하고, /ex) "3,2"
이렇게 만들어진 key가 memo에 저장되어 있다면,
그대로 사용한다.

합이 되는지 구하기

어떤 수(targetNum)이 주어지면 numbers 배열의 요소들중 합해서 targetNum이 되는 경우들을 구하시오.
ex) 7, [5,3,4,7] => 3+4=7, 7=7 이므로 [3,4], [7]을 return 한다.

  • 트리 그리기

  • 재귀 함수로 표현하기

const howSum = (targetSum, numbers)=>{
  if(targetSum === 0) return [];
  if(targetSum < 0) return null;

  for(let num of numbers){
    const remind = targetSum - num;
    const remindResult = howSum(remind, numbers);
    if(remindResult !== null){
      return [...remindResult, num];
    }
  }
  return null;
}
howSum(7,[5,3,4,7])
  • 동적 프로그래밍 사용하기
const howSum = (targetSum, numbers,memo={})=>{
  if(targetSum in memo) return memo[targetSum];
  if(targetSum === 0) return [];
  if(targetSum < 0) return null;

  for(let num of numbers){
    const remind = targetSum - num;
    const remindResult = howSum(remind, numbers,memo);
    if(remindResult !== null){
      memo[targetSum] = [...remindResult, num];
      return memo[targetSum];
    }
  }
  return null;
}
howSum(7,[5,3,4,7])

참고 자료:

profile
꾸준하게 공부하기

0개의 댓글