[코딩테스트]다이나믹 프로그래밍

📖다이나믹 프로그래밍(동적계획법)

▪ 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법.
▪ 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법.


▪ 재귀 함수 대신 반복문을 사용한 다이나믹 프로그래밍이 더 성능이 좋음.
▪ 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있으므로 탑다운 방식보다는 보텀업 방식으로 구현.

📌다이나믹 프로그래밍을 만족하는 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

📌다이나믹 프로그래밍을 구현하는 방법

탑다운 방식
▪ 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법.
▪ 큰 문제를 해결하기 위해 작은 문제를 호출.
▪ 하향식

메모이제이션 기법(캐싱)
▪ 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법.
▪ 탑다운 방식에 국한되어 사용되는표현.

보텀업 방식
▪ 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출.
▪ 큰 문제를 해결하기 위해 작은 문제를 호출.
▪ 상향식

DP 테이블: 보텀업 방식에서 사용되는 결과 저장용 리스트

📒이것이 취업을 위한 코딩테스트다 with 파이썬 책을 참고하여 작성하였습니다.
https://www.hanbit.co.kr/store/books/look.php?p_code=B8945183661