코린이의 소소한 공부노트

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..

1. 전략: top-down approach 1) 문제를 둘 이상의 작은 문제들로 쪼갠다. 2) 쪼갠 문제들을 각각 해결한다. - 쪼갠 문제가 충분히 작지 않다면 다시 쪼갠다. 3) 쪼갠 문제들이 해결되면 그 해답을 합친다. 2. 예시 - binary search - merge sort - quick sort - strassen's matrix multiplication - arithmetic with large numbers; representation, multiplication