우주의 IT 소행성

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

- 메모리 공간을 더 사용하여 연산속도를 비약적으로 증가시키는 방법

- 동적 계획법이라고도 함

- 탑다운과 보텀업 방식으로 나뉨

다이나믹 프로그래밍의 조건

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

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

메모이제이션 (캐싱)

- DP구현 방법중 하나, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식이 호출될 때 메모한 결과만을 그대로 가져오는 기법

탑다운 (Top-Down, 하향식)

- 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법

- 큰 문제를 해결 하기 위해 작은 문제를 호출한다고 해서 Top-Down 방식이라 함

- 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

보텀업 (Bottom-Up, 상향식)

- 반복문을 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법

- 작은 문제부터 차근차근 답을 도출한다고 해서 보텀업 방식이라 한다.

- 다이나믹 프로그래밍의 전형적인 형태

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

다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전 계산 결과를 일시적으로 기록해 놓은 것이므로 다이나믹 프로그래밍과는 별도의 개념이다.