1. 문제 계란 한 개에 _ _ _ _ _ _ _ _ _ _ _ _ _ 웨브바짐 달러! 계획 경제의 실패로 세계 최고의 인플레이션을 자랑하게 된 공산 국가 웨브바짐에서는 하루 중에도 물가가 계속 오르기 때문에 물건의 가격을 실시간으로 바꿔야 합니다. 웨브바짐에서 가장 큰 무가베 마트에서는 그래서 위와 같이 빈 칸만 쓰여 있는 광고판을 붙여놓고 계란 가격이 오름에 따라 (정확히는 웨브바짐 달러의 가치가 추락함에 따라) 실시간으로 숫자가 크게 적힌 플라스틱 판을 빈 칸에 갈아 끼웁니다. 예를 들어 계란 한 개에 35억 웨브바짐 달러라고 하면, 3이 쓰인 판 한 개, 5가 쓰인 판 한 개, 0이 쓰인 판 여덟 개를 빈칸에 순서대로 끼우는 것이죠. 무가베 마트에서 아르바이트를 하는 종욱이는 어느 날 곤란한 손님..

동적 계획법 중 메모이제이션을 적용하는 문제들이 참 많았는데, 무슨 소리인지 제대로 이해하지 못했다. 그래서 오늘 각잡고 조사해보았다. ^_^ 1. 동적 계획법이란? 동적 계획법 (dynamic programming): 처음 주어진 문제들을 분할하고, 이로부터 본 문제에 관한 답을 도출하는 접근 방법이다. 특히 부분 문제들의 수가 기하급수적으로 증가할 때 유용하다. 동적 계획법은 여러 문제 해결에 사용되는 부분 문제에 대한 결과를 여러번 계산하는 대신, 한 번만 계산하고 이를 재활용하여 속도를 향상시킨다는 점에서 분할 정복법과 차이가 있다. 이를 위하여 각 문제의 답을 메모리에 저장해야 하는데, 이미 계산된 값을 저장해두는 메모리의 장소를 캐시(cache)라고 하며, 두 번 이상 계산되는 부분 문제를 중..