Dynamic programing

• DP를 사용 할 수 있는 조건

  1. 큰 문제를 작은 문제로 나눌 수 있다.

  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

     ex) 피보나치 수열

     메모이제이션 (캐싱) : 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 결과를 그대로 가져오는 방법

     1. 한번 구한 정보를 리스트에 저장
     2. 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정보를 리스트에서 가져오기만 한다.

• DP의 두가지 방식

  1. 탑다운(Top-Down) : 재귀 함수를 이용하여 프로그래밍 소스코드를 작성하는 방법

     1. 하향식

     2. 메모이제이션

        이전에 계산된 결과를 일시적으로 기록

        → 배열, 리스트, 사전

     3. 큰 문제를 해결하기 위해 작은 문제를 호출

  2. 보텀업(Bottom-Up) : 반복문을 이용하여 프로그래밍 소스코드를 작성하는 방법

     1. 상향식

     2. DP 테이블

        결과 저장용 리스트

     3. 작은 문제부터 차근차근 답을 도출

     4. 탑다운보다 권장됨

        시스템상 재귀 함수의 스택 크기가 한정되어 있으면 recursion depth관련 오류가 발생할 수 있다.

        → setrecursionlinit()함수를 호출하여 재귀 제한을 완화

• 다이나믹 프로그래밍 요약

  • 한 번 해결된 부분 문제의 정답을 메모리에 기록하여 한 번 계산한 답은 다시 계산하지 않는다.

  • 점화식을 그대로 코드로 옮겨서 구현할 수 있다.

    점화식 : 인접한 항들 사이의 관계식

1. 1로 만들기

   $$ a_i = min(a_{i-1}, a_{i/2}, a_{i/3}, a_{i/5}) +1 $$

   • 지원코드 → DP맞는 것 같음

     조건을 많이 나눠놔서 계산이 복잡해보이는데 알고보면 이전 계산 결과 그대로 들고오는 건 수빈이랑 똑같

2. 개미 전사

   $$ a_i = max(a_{i-1},a_{i-2}+k) $$

   

3. 효율적인 화폐 구성

   • 화폐의 큰 단위가 작은 단위의 배수이기 때문에 그리디로는 풀 수 없다.

   1. 전체 배열의 크기를 M으로 설정

   2. 배열의 모든 값을 10001로 설정

   3. 2의 배수인 인덱스의 값들을 변경

   4. 3의 인덱스의 값들을 변경 (이전 값과 비교해 더 작은 걸로 업데이트)

      1. i : 금액
      2. k : 화폐의 단위

      $$ a_i = min(a_i,a_{i-k}+1) $$

   5. 위와 같이 5의 인덱스의 값들을 변경

1. 돌게임

   

2. 정수 삼각형

1. 카드