8. 다이나믹 프로그래밍

Intro

다이나믹 프로그래밍이라 함은 메모리를 적절히 사용해 수행 시간 효율성을 비약적으로 향상시키는 방법이다 

그렇다면 어케 적절히 사용하는가

바로 이미 계산된 결과(작은 문제)를 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하는 것이다.

한 번 해결한 문제는 다시 해결하지 않도록 하자! 라는 목표로, 다음의 조건을 만족할 때 사용할 수 있다.

 

1. 최적 부분 구조 (Optimal Substructure)
   : 큰 문제를 작은 문제로 나눌 수 있고, 그 작은 문제들의 답을 모아 큰 문제를 해결할 수 있는 구조
2. 중복되는 부분 문제 (Overlapping Subproblem)
   : 동일한 작은 문제를 반복적으로 해결해야 하는 구조

 

Meaning

Dynamic Programming ➡️ 동적 계획법 

자료구조에서 동적 할당(Dynamic Allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 말하지만, dp 알고리즘에서의 다이나믹(Dynamic)은 그 뜻이 아니고, 별 의미 없이 사용된 단어임 (Richard Bellman 아저씨가 dynamic이라는 단어가 간지나서 선택했다고 한다 ㅋ)

 

 

Fibonacci Nums

피보나치 문제를 생각해보자

단순 재귀함수로 피보나치 수열을 해결하고자 하면 같은 값이 여러번 호출된다는 것을 확인할 수 있다.

이 경우 "중복되는 부분 문제"가 발생하는 것!

이러케 한번 해결한 문제에 대한 답을 바로 알 수 있도록 별도의 메모리 공간에 기록하자~!는 아이디어

당연히 피보나치 수는 큰 문제의 답이 작은 문제들로 구해지는 "최적 부분 구조"에 해당하고, 우리는 다이나믹 프로그래밍을 통해 시간복잡도를 개선시킬 필요가 있다^o^

 

 

Top-Down

그렇다면 디피를 어떻게 구현하는가 !

두 가지 방법이 있는데여 바로 상향식과 하향식입니당

먼저 하향식, 즉 Top-down 방식에서 사용되는 메모이제이션(memoization) 방식에 대해 알아보도록 하게씀

이거슨 위에서 살짝 말했듯이 한 번 계산한 결과를 메모리 공간에 memo하는 기법 ^%

당요니 이러케 기록해놓은 값은 같은 문제를 해결해야 할 때 사용할거고, 배열 등에 값을 기록해놓는다는 점에서 캐싱(caching)이라고도 함 (그래서 배열명을 보통 cache, table, dp, d.. 등으로 설정함니다^~^)

탑다운 방식은 구현과정에서 재귀함수!!를 이용한다

큰 문제를 해결하기 위해서 작은 문제를 재귀적으로 호출하여 작은 문제가 모두 해결되었을 때 실제로 큰 문제에 대한 답까지 자연스럽게~ 얻을 수 있도록 코드를 작성하고, 그 과정에서 한 번 계산된 값을 기록하기 위해 메모이제이션 기법을 이용하는 것 !

** 메모이제이션은 특별한 것도 아니고, dp에 국한된 개념도 아님. 그저 한 번 구해진 결과를 별도의 공간에 담기만 한다면 캐시를 사용했다, 메모이제이션 기법을 사용했다 등등 이러케 표현하게 되는거임 

 

Bottom-Up

보텀업 방식은 말 그대로 아래쪽에서부터 작은 문제를 하나씩 해결해나가는데, 먼저 계산했던 값들을 활용해서 그 다음의 문제까지 차례로 해결하는 것이당~ 그래서 이것의 구현은 반복문 형태가 될 것임

* 그리고 디피의 전형적인 형태는 이 보텀업 방식이라고 함. 그리고 결과 저장 목적의 배열 및 리스트를 dp table이라고 부름

 

 

❔❔의문점❔❔❔❔❔

한 번 계산된 결과를 메모이제이션하고 한 번이라도 계산된 적이 있는 문제인지 체크해서 그 값을 그대로 반환하는 탑다운과 앞서 계산된 결과를 저장하기 위한 dp 테이블을 만들고 채워나가는 보텀업 --> 그냥 방향만 다르고 기록하는건 똑같은거 같은데 왜 개념이랑 용어...?를 구분하는지 이해가 안됨 (보텀업 방식에서 dp 테이블에 기록하는건 메모이제이션이 아닌가?? >>??)

 

 

❕❕❕❕분할 정복과의 차이❕❕

디피랑 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있으나, 차이점은 부분 문제의 중복!

디피 문제에서는 각 부분 문제들이 서로 영향을 미치고 중복됨. 예를 들어 피보나치에서는 특정 부분 문제가 반복적으로 호출되었음

반면 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음 (ex 퀵 정렬에서 기준 원소(pivot)이 자리를 잡으면, 즉 한 번 분할이 이루어지면 해당 피벗을 다시 처리하는 부분 문제는 호출되지 않음 ~)

 

 

결론: 디피문제를 마주했을 때 떠올려야 할 디피는... 규칙을 찾고... ☆점화식을 세우는 것☆ 그걸 코드로 구현하는 것...!이 아닐까?