25.md

멀리 뛰기

동적프로그래밍과 메모이제이션

• 동적프로그래밍 정의

  사실 위에서 말하는 동적프로그래밍에 대해서 깊이있게 알지는 못한다. 그래서 잠시 동적프로그래밍이 무엇을 말하는지 알아보자.

  동적프로그래밍(Dynamic Programming)이란 하나의 문제를 작은 문제로 나누어서 그 결과를 저장한 뒤 다시 큰 문제를 해결할 때 이를 사용하는 아이디어(패러다임 혹은 알고리즘)이라고 말한다. 동적프로그래밍을 사용하는 경우, 즉 언제 동적프로그래밍을 사용하면 좋을까?

• 겹치는 부분 문제

  겹치는 부분 문제는 어떤 문제가 여러 개의 부분 문제들로 나눠질 수 있다는 것을 의미한다. 이러한 예시가 피보나치 수열이다. 피보나치 수열은 앞의 두 수를 더해서 다음 수가 되도록하는 수열이다.

  f(0) = 0, f(1) = 1
  f(n) = f(n-1) + f(n-2) (n >= 2)
  

  피보나치 수열

  모든 문제가 부분 문제로 쪼개질 수 있고, 작은 문제의 답을 구하는 방법으로 큰 문제의 답을 구할 수 있다. 이처럼 반복되는 부분에 대한 문제를 해결하기 위해서 재귀적 용법이 사용된다. 이러한 재귀적 용법에서의 비효율을 해결하기 위해서 부분 문제의 결과를 저장하여 재사용하는 방식(메모이제이션)으로 접근한다.

• 최적 부분 문제

  최적의 문제는 어떤 문제의 최적의 해결책이 부분 문제의 최적의 해결책으로 만들어질 수 있는 것을 말한다. 그래서 특정 문제의 정답이 부분 문제의 정답과 일치하게 된다. → 솔직히 이 최적 부분 문제라는 것이 어떤 문제인지 명료하게 와닿지 않는다. (어디선가 풀어봤을지 모르지만,) 이러한 예시가 있다면 한번 체크해봐야겠다.

• 동적프로그래밍 접근 방법

  1. 풀어야할 문제가 반복되는 작은 문제들로 구성되어 있는지 여부 파악
  2. 문제에서 사용되는 변수들 간의 관계를 나타내는 식(관계식/점화식)으로 표현해보기
  3. 반복되서 사용되는 값들을 저장할 수 있도록! 메모이제이션 구현

Try1

function solution(n) {
  let count = 0;

  const recursive = (k) => {
    if (k > n) return;
    if (k === n) {
      count++;
      return;
    }
    recursive(k + 2);
    recursive(k + 1);
  };

  recursive(2);
  recursive(1);

  return count % 1234567;
}

위 구현은 재귀적인 방식으로 접근한 방식이다. 제출 후에 시간초과가 발생한다. 부분 문제에 대한 반복적인 계산으로 인한 비효율이 발생했기때문으로 보인다. 그래서 위 코드에서 메모이제이션을 활용하기 위해서 생각해봤다. 하지만 위 코드에서는 메모이제이션을 어떤 식으로 해야할지 감이 오지 않았다. 우선 이 코드에서는 n의 변경에 따라서 값을 반환하도록 만들지 않고, 전역 변수 count를 통해서 하나로 카운팅하도록 설계되었기 때문으로 보인다.

Try2

function solution(n) {
  const memo = [1, 2];

  for (let i = 2; i < n; i++) {
    memo[i] = (memo[i - 1] + memo[i - 2]) % 1234567;
  }

  return memo[n - 1];
}

사실 이 코드는 여러 참고 글을 통해서 구현한 부분이다.

위에서 언급한 동적프로그래밍 접근 방법처럼 각 문제들에 대한 관계식을 만들어야한다.

f(n)에 대한 정의

n = 1 일 때, 1칸을 가는 방법, n = 2 일 때, 2칸을 가는 방법,.... n일 때, n칸을 가는 방법

→ 1 2 3 5 8 .... 이런 식의 나열이 된다. 자세히보면 익숙한 식이다. 바로 피보나치이다. 그렇다면 관계식은 f(n) = f(n - 1) + f(n - 2) (n >= 2) 이렇게 된다. 그래서 이제 이 식을 이용해서 부분의 문제를 메모이제이션한다. 여기서는 각 배열에 값을 저장해서 사용하게 된다.

여기서 왜 % 1234567는 최종값이 아닌 부분 문제를 계산할 때 하는걸까? 최종에서만 나머지 연산을 하도록 구현하면 에러가 나게 된다. 그 이유는 연산을 통해서 나온 값이 너무 커서 변수(memo배열)에 저장할 수 없기 때문이다. 그래서 나머지 연산까지 한 값을 메모이제이션하는 것이다.

결론

이 문제는 문제를 풀었다기보다, 실수, 오류를 통해서 동적프로그래밍을 다시 한번 살펴보는데 의의가 있는 문제였다. 사실 문제를 풀 때, 어떤 알고리즘을 써서 풀어야겠다 라기보다는 그냥 문제를 읽고 조건과 상태에 맞춰서 구현하는 것이 일반적으로 내가 코테를 푸는 스타일이다. 이런 방식이 문제 자체를 이해하고 고민하는데 도움이 될 수는 있겠지만 당장 코테를 보기 위한 방법과는 맞지 않을 수 있다는 생각은 든다. 그렇기 때문에 앞서 서술한 것처럼 코테를 유형별로 분리하고, 해당 유형에 대한 배경지식을 갖추는 작업(ex. 동적프로그램밍에 대해서 정리해보는 것)이 필요하다는 생각이 든다. 이런 작업을 위한 시간을 갖기보다는 문제를 풀면서 점차적으로 내가 능동적으로 해야하는 작업일 것이다. 화이팅 👊🏻