[알고리즘] 🤷‍♂️ 동적 계획법 / dynamic programming

👉 동적계획법

DP(동적 계획법)이 뭔가요?

DP는 알고리즘 문제로 자주 나오는 디자인 패러다임 중 하나입니다. Dynamic Programming이라는 말은 고안자인 벨만이 dynamic이라는 단어가 멋있어서(…) 선택한 단어라고 합니다. 따라서 이 방법은 전산학 전반에서의 동적(dynamic) 혹은 프로그래밍(programming)이라는 단어와는 관련이 없습니다. DP의 한글 번역도 동적 프로그래밍보다는 동적 계획법으로 번역됩니다.

👉 특징

부분 문제(overlapping subproblems)

동적 계획법의 접근 방식은 분할 정복과 같습니다. 주어진 문제를 더 작은 문제로 나눈 뒤 이 문제의 답을 계산하고, 이 답을 토대로 원래 문제의 답을 도출해가기 때문입니다. 하지만 분할 정복과 문제를 나누는 부분에서 차이가 납니다. 동적 계획법에서 어떤 부분 문제가 두 개 이상의 문제를 푸는 데 사용되는 데 이를 중복되는 부분 문제(overlapping subproblems)라고 부릅니다.

메모이제이션(memoization)

동적 계획법에서는 이 중복되는 부분을 저장하여 재활용함으로써 속도를 향상시킬 수 있습니다. 이미 계산한 값을 저장해 둔 메모리의 장소를 캐시(cache)라 부르고 이를 활용하는 최적화 기법을 메모이제이션(memoization)이라 부릅니다.

👉 구현

일반적인 동적 계획법 알고리즘 구현 방법

1. 주어진 문제를 완전 탐색(exhaustive search)로 해결합니다.
2. 중복된 문제(overlapping subproblems)를 한 번만 계산하기위해 메모이제이션(memoization)을 이용합니다.

🙋‍♂️ 추천 문제

• Lv 1    N으로 표현

• Lv 3    타일 장식물, 정수 삼각형, 등굣길

• Lv 4    카드 게임, 도둑질, 서울에서 경산까지

Written with StackEdit.