수리 공작소

동적 계획법(Dynamic Programming, DP)이란? 동적 계획(Dynamic Programming, DP)이란 주어진 문제를 작은 부분으로 쪼개어 해결해나가는 방법이다. 이러한 부분에서 분할정복(Divide and Conquer, DC) 비슷하지만 두 가지 대표적인 차이점이 있다. 1. 문제 접근 방식의 차이 DC는 top-down approach이고, DP는 bottom-up approach라는 차이점이 있다. (물론 DP도 top-down으로 사용될 수 있지만 대체적으로 그렇다고 한다.) 2. DP의 추가적인 메모리 저장 DP는 DC와는 다르게 이전에 계산한 값을 배열(혹은 다른)에 저장을 하여 재활용한다. 이와 같은 방법을 Memoization이라고 한다. 덕분에 이후에 중복 계산을 피하..

문제 요약 : 전체 버스 N개가 있고, 그 중 창영이가 이용할 버스가 M개 입력으로 주어진다. 이 버스를 순서대로 탈 때, 들어가는 총 환승 비용으로 계산하는 문제이다. (전체 버스 간의 환승비용은 이차원 배열로 입력받는다.) #include using namespace std; int main() { int allBus = 0, useBus = 0, fee = 0;; // 모든 버스의 수, 창영이가 사용할 버스의 수, 총 환승 요금 cin >> allBus >> useBus; if (allBus 100 || useBus > allBus || useBus < 1) return 0; //조건 필터링 int* listUseBus = new int[useBus]; // 창영이가 사..

영어로 된 문제를 처음 풀어본다...! 영어로 쓰여져 있으면 괜히 더 어려워보인다. 사실은 복잡하지 않은 문제였다! 어쨋든 시작, 문제를 요약하자면 다음과 같이 벽돌은 몇개의 스택으로 나누어 쌓는다고 가정한다. 스택의 길이를 일정하게 유지하지 않고 쌓은 뒤, 최소한의 움직임으로 전체 스택의 길이를 맞추어주는 문제이다. 이때 개인적으로 생각했을 때 잊어버리지 말아야할 조건은 1. 위와 같은 형태를 한 세트라고 두었을 때, 입력은 여러 세트가 가능하다. 2. 0이 입력되었을 때 입력이 끝났음을 알 수 있다. (0에 대해선 계산을 돌지 않는다.) 3. 벽돌의 전체 수는 스택의 개수로 나누어 떨어진다. 즉, 남는 벽돌이 없다는 뜻이다. 다음은 코드이다. 먼저 각 세트의 최소 이동 벽돌 수를 구해주는 함수를 작성..