다이나믹프로그래밍(1)

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 

코드 출처: https://github.com/ndb796/python-for-coding-test

---

▶ 다이나믹 프로그래밍이란?

메모리를 적절히 사용하여 수행시간의 효율성을 향상시키는 방법이다. 즉 한번 계산된 결과는 별도 메모리 영역에 저장해 다시 계산하지 않도록한다. 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용한다. 

 

1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있어 작은 문제를 모아 큰 문제를 해결할 수 있을 때

2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결할 때

 

현재 주어진 문제가 다이나믹 프로그래밍 유형인지 아닌지 고민하여 파악한느 것이 중요하다. 문제를 보고 위의 조건들이 만족한다면 다이나믹 프로그래밍 구현을 생각해보자. 

 

 

▷ 예시

피보나치 수열의 점화식을 구현할 때.

- 아래처럼 단순 재귀함수로 해결하면 지수시간 복잡도를 가지게 돼서 엄청난 시간적 비효율성이 발생할 수 있다. 

> 재귀함수 활용

 

피보나치 수열 중 여섯번째 수를 구하기 위해서 재귀함수를 구하게 되면 두번째 수를 반복적으로 구해야하는 상황이 발생한다. 이런 경우 다이나믹 프로그래밍을 이용하여 더욱 효율적으로 코드를 구현할 수 있다. 이에 앞서 피보나치 수열을 다이나믹프로그래밍의 두가지 조건을 만족하는지 체크해야한다. 

1. 피보나치 수열은 최저구분구조를 만족한다- 네번째수열을 해결하기 위해 세번째 수열과 두번째 수열과 같은 작은 문제를 합쳐 해결할 수 있기 때문에다.

2. 중복되는 부분 문제 또한 만족한다- 네번째 수열을 구하기 위해 두번째 수열이 두번 반복해서 계산하여 해결한다. 

 

 

▷메모이제이션 memoization이란?

한번 계산한 결과를 일시적으로 메모리 공간에 메모해놓고 같은 문제가 생겼을 때 호출하여 메모했던 결과를 가져와 사용할 수 있다. 탑다운top-down방법의 경우 메모이제이션을 사용하지만 보텀업bottom-up방법의 경우 메모이제이션을 사용하지 않을 수 있다. 두가지 방법에 대해 다음과 같이 코드 구현을 따라해보았다. 

 

 

 

▷ 예시 - 피보나치 수열

> top-down 

메모이제이션을 활용하여 탑다운 방식을 구현하였다. 메모이제이션을 통해 이전보다는 시간 효율적이지만 이전과 같이 재귀함수를 사용하기 때문에 같은 과정을 반복해서 따라야하므로 오버헤드가 발생할 수 있다. 

 

> bottom- up

 

일반적으론 이렇게 반복문을 사용하여 다이나믹 프로그래밍을 구현할 때 더 성능이 좋다고 한다. 이때의 시간복잡도는 O(N)이다.