SunFly의 코딩 및 정보 블로그

DP. 즉 Dynamic Programming은 여러가지 알고리즘 문제들을 풀다보면 간간히 사용하는 경우가 많다. 핵심 내용은 이전에 계산한 값을 다음 실행에 써먹을 수 있고 이러한 계산들이 쌓여서 결과를 도출한다는 것이다. 한마디로 입력값이 이전 계산값이고 출력값이 현재 구하려는 값이다. 백준의 14501번 : 퇴사 문제를 예시로 들어서 보자. 이 문제는 삼성 역량 테스트 문제로도 나온 문제로 대기업 코테에서도 DP 관련 문제가 나올 수 있다는 것을 알아두자. dp 45(35+10) 45 45(35+10) 35(15+20) 15 0 0 0 ♦ 아이디어 방향 1. 그 전에 해당된 날짜의 이익, 상담하는 데에 걸리는 일수를 알고 있어야 다음을 진행할 수 있다. 2. 그 전 값을 기억하는 알고리즘 DP 알고..

문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일Ti Pi 3 5 1 1 2 4 2 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다. 상담을..