1) dynamic programming과 memoization은 서로 완전히 다른겅미 'ㅅ')
2) 모든 recursive 함수가 dynamic programming으로 변환 가능한것은 아님. (너무 당연한가)
3) DP는 기억하는게 아니라 점화식(수열)을 컴퓨터로 계산하는 것.
4) memoization은 알고리즘이라기 보다는 최적화 기술에 속함.
주의해야할건 Memo"ri"zation아니라는 Memo"i"zation임.
2) 모든 recursive 함수가 dynamic programming으로 변환 가능한것은 아님. (너무 당연한가)
3) DP는 기억하는게 아니라 점화식(수열)을 컴퓨터로 계산하는 것.
4) memoization은 알고리즘이라기 보다는 최적화 기술에 속함.
주의해야할건 Memo"ri"zation아니라는 Memo"i"zation임.
아 스펠링 틀렷다
횽이 정곡을 찔렀네.ㅋㅋ
DP는 점화식으로 표현될 수 있는 데이터들을 점화식을 계산해가는데 필요한 최소의 변수만 써서 계산했던가, 그렇게 기억하는데 맞어?
메모이제이션은 값이 여러번 호출될 때, 재계산 대신 최초 계산 결과를 배열로 저장해 둔 뒤 다시 요청올 때 반환해서 계산 속도 높이는 기법이고
http://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98
http://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
그런데 앞에 장기문제 말야, DP로 최단횟수 구하고, 경로는 메모이제이션으로 구한 문제 아니였어? 그래서 둘 다 쓰였다고 표현한거 같은데
그건 그냥 단순 재귀지 'ㅅ') 경로를 찾으면서 스스로 연산하는건 아니잖아.
http://en.wikipedia.org/wiki/Dynamic_programming
지금 횽은 bottom-up approach 말하는듯
내가 말하는건 top-down이고
그런데 top-down에 메모이제이션 포함됨...
좁게 보면 횽이 말한 bottom-up이 DP인데, 넓게보면 top-down도 포함됨.
솔까 복합문제에서 알고리즘 분류 운운하는것도 삽질인듯.ㅎㅎ
사실 bottom-up/top-down 구분 자체가 formal한게 아니고, 구분하더라도 Memoization이 top-down DP의 superset임.