Dynamic Programming - 알고리즘
DP란?
DP란 Dynamic Programming의 약자로 한글론 ‘동적 계획법’이라고 한다. 이 이름은 대대로 엄청나게 까여왔고 쉽게 이야기하려는 분들이 가끔 ‘기억하며 풀기’라고 부르기도 한다.
‘기억하며 풀기’라는 이름에서도 알 수 있듯이 기본적인 개념은 ‘부분 문제의 답을 재활용하여 푼다.’라고 볼 수 있다.
DP로 사고하기
DP가 말이 ‘부분 문제의 답을 재활용하여 푼다.’라고 하지. 실제로 구현하려면 꽤 복잡하다.
나같은 경우는 순차적으로 생각하는데 이런식으로 한다.
완전 탐색 알고리즘을 설계한다.
모든 답을 헤아려보는 알고리즘을 만들어본다.
메모이제이션
함수의 반환값을 저장해 둘 캐시를 만들어 놓는다.
최적 해를 구하기 위해 최적화한다.
DP가 쓰이는 경우는 대부분 최댓값, 최솟값에 대한 문제이다. 부분문제의 최적값을 메모이제이션하여 지니고 있는다.
예고
이게 직접 어떻게 쓰이는지 다음 포스트에서 알아보자.
2023년 새해에는 성장하고 함께하고 싶다면?
Pre A 단계 이상의 스타트업 C 레벨들이 모여서 커뮤니티를 만들었습니다. 같이 스터디하고 친해질 일잘러를 찾습니다.