WOONY's 인사이트

1. 점프(#2253) 처음에 떠올렸던 아이디어는 출발지점에서 중간 도착지점을 저장하는 방식으로 DP 테이블을 짜는 방식이었다. 예를 들어 1번 돌에서 10번 돌까지 간다고 하면 1번 (+1)=> 2번 (+2)=> 4번 => 7번 => 10번이니까 D[1][2] = 1, D[2][4] = 2, D[4][7] = 3, D[7][10] = 3 이렇게 해서 최종적으로 D[1][10] = D[1][2] + D[2][4] + D[4][7] + D[7][10] 이런 식으로. 그런데 점화식을 짜려니 뭔가 꼬이기 시작하더라..가장 관건은 속도였는데, 나는 속도를 dp 테이블에 value로 저장했으나 이를 어떻게 점화식으로 풀어내야 할지 감이 잘 오지 않았다. 결국 풀지 못하고 풀이를 검색해서 찾아봤다. 풀이에서는 속도..

오늘은 그리디 알고리즘에 대해 공부한 내용을 빠르게 정리하고 마무리. 앞에서 배웠던 재귀 관련 알고리즘으로는 크게 두 가지가 있었다. 분할 정복(Divide and Conquer)과 동적계획법(Dynamic Programming)이 그것이다. 1. 분할정복은 큰 문제를 중복 없는 작은 문제들로 분할하는 방법이다. 재귀적으로 작은 문제부터 해결한다. 2. 반면, 동적계획법은 작은 문제들로 쪼개되 이 작은 문제들 중 중복되는 애들을 DP 테이블에 저장해두고 같은 값이 나왔을 때 계산 없이 바로 테이블에서 꺼낸다. 그러면 오늘 다룰 그리디 알고리즘은 어떤 친구일까? 이름처럼 말 그대로 Greedy하게 선택하는 알고리즘을 뜻한다. 즉, 현재 상태에서 가장 좋은 선택을 반복해서 해를 구성한다. 예제로 동전 교환 ..