다이나믹 프로그래밍(DP), 메모이제이션

📌 아래와 같은 순서로 작성되었습니다.
    - 다이나믹 프로그래밍 개요
        - 다이나믹 프로그래밍(DP)이란?
        - 다이나믹 프로그래밍 사용 조건
    - 피보나치 수열
        - 피보나치 수열
        - 피보나치 수열 시간복잡도
    - 메모이제이션(Memoization)
        - 메모이제이션(Memoization)
        - 탑다운 vs 보텀업
        - 메모이제이션을 활용해 피보나치 수열을 해결해보면?
    - 다이나믹 프로그래밍 vs 분할 정복

---

다이나믹 프로그래밍(DP)이란?

• 메모리를 적절히 사용해 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과는 별도의 메모리 영역에 저장해 다시 계산하지 않도록 함
• 일반적으로 두 가지 방식(탑다운, 보텀업)으로 구성
• 동적계획법이라고도 부름

다이나믹 프로그래밍 사용 조건

1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있음
2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결

   * 피보나치 수열은 DP사용 조건을 만족한다.

---

피보나치 수열

단순재귀함수로 피보나치 수열을 해결하는 경우

• 단순재귀함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 됨
• 위 그림과 같이 f(2)가 여러번 호출 됨(중복되는 부분 문제)

피보나치 수열 시간복잡도

=> 빅오 표기법을 기준으로 f(30)계산을 위해 약 10억가량의 연산 수행해야 함

 

---

메모이제이션(Memoization)

• 한번 계산한 결과를 메모리 공간에 메모하는 기법
  •   같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
  •  값을 기록해놓는다는 점에서 캐싱(Caching)이라고도 함

탑다운 vs 보텀업

• 탑다운(메모이제이션) 방식을 하향식이라고도 하며 보텀업 방식은 상향식이라고도 함
  •  DP 전형적인 형태는 보텀업 방식
  •  결과 저장용 리스트는 DP테이블이라고 부름
• 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미
  •   따라서 메모이제이션이 DP에 국한된 개념은 아님
  •   한 번 계산된 결과를 담아 놓기만 하고 DP를 위해 활용하지 않을 수도 있음

메모이제이션을 활용해 피보나치 수열을 해결해보면?

 

 

 

 

=> 이미 계산된 결과를 메모리에 저장하면

왼쪽 그림과 같이 색칠된 노드만 처리할 것을 기대할 수 있음

 

 

 

 

 

 

 

 

=> 실제 호출되는 함수에 대해서만 확인해보면

왼쪽 그림과 같이 방문

 

 

 

 

 

 

메모이제이션을 이용하는 경우, 피보나치 수열 함수의 시간복잡도는 0(N)이다.
      => 지수 시간복잡도를 가지던 문제를 DP를 적용하면 선형시간까지 시간 복잡도 줄일 수 있음

---

다이나믹 프로그래밍 vs 분할 정복

• 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용가능
  •   큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
• 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다.
  •   다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
  •   분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음

분할정복 대표 예시 퀵 정렬을 보면, 한 번 기준 피벗이 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않음

분할 이후에 해당 피벗을 다시 처리하는 부분 문제는 호출하지 않는다.

 

 

🔎 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하다

1. 먼저, 그리디, 구현, 완전 탐색 등의 아이디어로 문제 해결할 수 있는지 검토
2. 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍 고려해보기
3. 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤(탑다운)
   작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있음

* 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음

 

 

 

reference

'(이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍' 강의영상을 참고해 작성하였습니다.
https://www.youtube.com/watch?v=5Lu34WIx2Us&t=182s