알고리즘의 고비, DP 학부생 때 알고리즘 수업을 들을 때 DP는 너무 쉬운 과목이었습니다. 메모이제이션으로 계산양을 줄인다는 이야기 외에는 이해를 못했기 때문입니다. 석사과정에서 알고리즘은 한학기 내내 DP 문제만 다루는 내용이었습니다. 그 때서야 저는 점화식이 눈에 들어왔고, substruct를 정의해내야 한다는 사실을 알았으며, 2차 배열이 많이 활용된다는 정도 이해하였습니다. 알고리즘에서 DP는 어려운 단원에 속하고, 그렇기 때문에 몇 년 전에는 풀었던 문제도 다시 풀면 못풀고 잊어버리는 듯 합니다. 지금 코딩테스트를 공부하면서, 얼핏 이해했다고 생각한 DP를 활용하지 못하는 제 자신을 보면서 확실한 이해가 필요하다고 생각했습니다. BOJ 2616 소형기관차 제가 간과했던 사실 중 하나는 점화식의..