다이나믹 프로그래밍과 메모이제이션

'한 번 계산한 문제는 다시 계산하지 않도록 한다.'

 

다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다.

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

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

 

 

# 메모이제이션 :: memoization

- 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면, 메모한 결과를 그대로 가져오는 기법을 의미한다. 

- 메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다. 

 

- 구현: 단순하게, 한 번 구한 정보를 리스트에 저장한다. 

- 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때에는 이미 구한 정답을 그대로 리스트에서 가져온다. 

 

 

# 다이나믹 프로그래밍과 분할 정복의 차이

- 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다. 

- 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결한다. 

    - 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이미 해결이 됐던 것이니까 다시 해결할 필요가 없다고 반환하는 것이다. 

 

 

# 탑다운(Top-Down) 방식과 바텀업(Bottom-up) 방식?

- 탑다운 방식 : 재귀함수를 이용하여 코드 작성하는 방법. 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 ...

- 바텀업 방식 : 단순히 반복문을 이용하는 방법. 작은 문제부터 차근차근 답을 도출한다.

 

 

- 메모이제이션은 탑다운 방식이고, 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다. 

- 바텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부른다. 

 

- 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념이라, 다이나믹 프로그래밍과는 별도의 개념이다. 

- 메모이제이션 사용을 위해, 리스트 이외의 자료형을 사용할 수도 있다. 예를 들어, 사전(dict) 자료형.

 

 

 

# 문제 풀이

- 첫 번째로, 주어진 문제가 다이나믹 프로그래밍 유형임을 파악한다. 

- 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지, 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자. 

 

- 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에, 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어다. 

 

- 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 바텀업 방식으로 구현하는 것을 권장한다. 

- 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다.