이번 주차에는 Dynamic Programming과 Greedy Algorithm을 공부했다.
동적계획법은 큰 문제를 작은 문제로 분할, 작은 문제의 점화식으로 큰 문제를 나타내는 방법으로 분할정복과 비슷한 느낌이었다.
그리디 알고리즘은 그럴듯한 최선의 솔루션을 찾는 방법을 생각해내고, 수학적으로 증명(귀류법을 주로 사용하는 것 같다.)하는 방법이었다.
그리디 알고리즘은 한번에 최적의 솔루션을 찾아내면 좋겠지만, 잘못된 솔루션을 생각하면 답이 나오지 않을 때, 구현의 문제인지 솔루션 자체의 문제인지 알아내고 솔루션이 문제일 경우에는 스스로 내 생각을 반증해야 한다는 점이 굉장히 어려운 부분이라고 느껴졌다.
