동적 계획법

[백준 2616] 소형기관차 (C++)

2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 현재 칸을 선택할 때, 선택하지 않을 때를 정해서 재귀를 수행하면 되는 문제이다. 현재 칸을 선택하지 않는다면 현재 칸의 번호를 +1 한 채로 다음 칸으로 넘어간다. 현재 칸을 선택한다면? 현재 칸부터 소형 기관차의 크기만큼 연속된 칸에 타있는 손님의 수를 누적합 배열 parr을 통해서 구해준다. 그리고 현재 칸의 번호를 +소형기관차의크기 한 채로 다음 칸으로 넘어간다. 기저 조건은 소형 기관차를 선택한 횟수가 4가 되거나 현재 칸을 선택해도 소형 기관차의..

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

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