메모이제이션 패턴

동적 계획법 메모이제이션 패턴 (C++)

동적 계획법.. 다이나믹 프로그래밍과 같은 말이다. 동적 계획법은 개념 자체는 쉬워서 알고리즘의 기본 난이도는 낮은 편이다. 하지만 메모이제이션을 몸에 익히고 문제를 보고 동적계획법을 떠올리며 어떤 정보를 메모이제이션할지 바로 찾아내는 내공을 가지려면 엄청난 노력이 필요하다고 생각한다. 다른 알고리즘과는 비교가 안될정도로 많이. 이 책에는 약 25개 정도의 큼직한 알고리즘 파트가 1000페이지 조금 넘게 기술되어있다. 그 중에서 동적계획법은 160페이지 가량 되는데 비중이 정말 크다고 볼 수 있다. 쉬우면 너무 쉽지만 어려우면 말이 안나올정도로 어려운 동적계획법의 가장 기본이 되는 탑다운 메모이제이션 패턴을 알아보자. 패턴 코드 // 전부 -1로 초기화 int cache[2500][2500]; int F..