알고리즘의 고비, DP
학부생 때 알고리즘 수업을 들을 때 DP는 너무 쉬운 과목이었습니다. 메모이제이션으로 계산양을 줄인다는 이야기 외에는 이해를 못했기 때문입니다. 석사과정에서 알고리즘은 한학기 내내 DP 문제만 다루는 내용이었습니다. 그 때서야 저는 점화식이 눈에 들어왔고, substruct를 정의해내야 한다는 사실을 알았으며, 2차 배열이 많이 활용된다는 정도 이해하였습니다.
알고리즘에서 DP는 어려운 단원에 속하고, 그렇기 때문에 몇 년 전에는 풀었던 문제도 다시 풀면 못풀고 잊어버리는 듯 합니다. 지금 코딩테스트를 공부하면서, 얼핏 이해했다고 생각한 DP를 활용하지 못하는 제 자신을 보면서 확실한 이해가 필요하다고 생각했습니다.
BOJ 2616 소형기관차
제가 간과했던 사실 중 하나는 점화식의 정의입니다. 석사과정에서 보았던 수많은 DP 문제들의 대부분이 2차배열을 이용하여 풀렸고, 이 행렬의 값은 이전에 계산한 값을 이용하여 작성되는 substruct를 가지고 있었습니다. 저는 그 수업에서 2차 배열에 그려지는 그림을 보면서, substruct를 정의해내는 것이 DP를 푸는 key라고 생각했습니다. 하지만 어떻게 풀어야하는지에 대해서는 감을 잡지 못했습니다.
https://www.acmicpc.net/problem/2616
2616번: 소형기관차
첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있
www.acmicpc.net
오늘 백준의 소형기관차라는 누적합 문제를 풀면서, 최악의 경우 50_000 ** 3인 완전 탐색으로 절대 될 수 없음을 알고 더 이상 문제 접근을 하지 못하며 답답해하고 있었습니다. 그리고 아래 블로그에서 이 문제에 대해 자세히 설명해주신 내용을 읽게 되었습니다.
https://comyoung.tistory.com/184
[백준] 2616번 소형기관차
2616 소형기관차 문제 기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 간다. 기관차가 고장나면 기차를 운행할 수 없게 되므로 최근 철도청은 기관차 고장에 대비하여 몇몇 역
comyoung.tistory.com
제가 수업시간에 봤던 2차 배열에 정성스럽게 설명해주신 것을 보고 "어떻게 이렇게 접근할 수 있었을까?"를 생각하며, 어디서부터 다시 시작해야할지 고민하고 있었습니다.
점화식이란
저는 위 블로그에서 점화식으로 접근하시는 것을 보았습니다. 그런데 점화식의 정의가 기억이 나지 않아 검색을 해보게 됩니다.
https://ko.wikipedia.org/wiki/%EC%A0%90%ED%99%94%EC%8B%9D
점화식 - 위키백과, 우리 모두의 백과사전
수학에서 점화식(漸化式) 또는 재귀식(再歸式, 영어: recurrence relation)이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식이다. 즉, 수열 { a n } {\displaystyle \{a_{n}\}} 의 각 항 a
ko.wikipedia.org
수학에서 점화식 또는 재귀식이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식이다.
예전에 저는 단순히 substruct를 정의하는 것이라고 생각했던 점화식에서 중요했던 사실은 수열의 두 항 사이 관계를 정의한다는 것이었습니다. 제가 수업에서 보았던 2차배열은 메모이제이션이고, substruct였으며, 작성된 두 항의 관계였습니다.
이런 간단한 사실로 DP를 모두 이해했다고 볼 순 없지만, 이제 제가 DP 문제를 접근할 때 염두할 수 있는 사항이 하나 더 늘어났습니다.
1. 반복되는 계산을 메모이제이션으로 줄이기
2. 반복되는 계산이 있는지 substruct 파악하기
3. substruct를 파악할 때, 두 항의 관계를 파악하기