목록DP (1)

코린이의 소소한 공부노트

Dynamic Programming

1. 전략: bottom-up approach 1) 문제의 가장 작은 단위부터 사용할 수 있는 반복문을 작성한다. 2) 가장 작은 문제부터 차례대로 풀어나간다. 3) 저장된 결과를 재사용한다. 3) divide and conquer와의 공통점 - 문제를 작게 쪼개서 해결한다. 4) divide and conquer와의 차이점 - DAC의 경우 top-down 형식이기 때문에 중복 계산이 여러 개 생겨날 수 있다. - DP는 bottom-up 형식이기 때문에 중복 계산이 생기지 않는다. 2. 예시 - binomial coefficient - Floyd's algorithm for shortest paths - traveling salesperson problem - chained matrix multipl..
Back-End/Algorithm 2023. 3. 7. 00:35
이전 Prev 1 Next 다음