동적계획법
-
백준 1890번 점프 :: 마이구미알고리즘 풀이/동적계획법 2017. 8. 15. 17:41
이번 글은 백준 알고리즘 문제 1890번 "점프" 를 다뤄본다.본인의 실력으로는 BFS, DFS 둘 다 시도해봤지만 도저히 맞을 수가 없었다.그리하여 동적계획법으로 문제를 접근했다. N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다.가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오. 각 칸을 기준으로 거리를 통해 갈 수 있는 지점에 경로의 개..
-
백준 14585번 사수빈탕 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 5. 30. 23:38
이번 글은 백준 알고리즘 문제 14585번 "사수빈탕" 을 다뤄본다.문제는 2017 고려대학교 프로그래밍 대회에서 출제된 문제이다.문제 풀이는 동적계획법으로 접근할 수 있다. 수빈이는 좌표평면 위에 앉아있다. "나는 좌표평면이 너무 좋아!!" 라고 수빈이가 말했다. 좌표평면에는 N개의 사탕바구니가 있고, 각 사탕 바구니에는 M개의 사탕이 있다. 각 사탕 바구니는 (x1, y1), (x2, y2), …, (xn, yn)에 있고, 수빈이는 (0, 0)에 있다.오늘은 날씨가 덥다. 따라서 시간이 1만큼 지날 때마다 모든 사탕바구니에서 사탕은 1만큼 줄어든다. 수빈이는 매우 배가 고프기 때문에, 사탕바구니에 있는 사탕을 순식간에 모두 먹을 수 있다. 수빈이가 1만큼 움직일 때, 시간은 1만큼 지나간다. 수빈이는..
-
백준 14501번 퇴사 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 4. 21. 11:14
이 글은 백준 알고리즘 문제 14501번 "퇴사" 를 풀이한다.삼성 SW 역량 테스트의 기출 문제이다.동적계획법을 통해 문제를 해결할 수 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일Ti3511242Pi1020102015402001일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.또한, N+1일 째에는 ..
-
백준 2096번 내려가기 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 4. 4. 20:25
이번 글은 백준 알고리즘 2096번 문제 "내려가기"를 다뤄본다.이 문제는 동적계획법으로 해결할 수 있다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 문제를 이해하기에는 어렵지 않다.문제에서..
-
백준 2240번 자두나무 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 3. 27. 13:28
이번 글은 백준 알고리즘 2240번 "자두나무" 를 다뤄본다.이 문제의 풀이는 동적계획법으로 해결한다. 매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 ..
-
백준 2011번 암호코드 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 3. 19. 15:43
이번 글은 백준 알고리즘 문제 2011번 "암호코드" 를 다뤄본다.동적 계획법으로 접근하는 문제이다.일단 문제를 보자. 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러가지가 있어.상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?선영: 예가 적절하지 않았네 ..
-
백준 2579번 계단 오르기 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 16. 22:58
이번 글은 백준 알고리즘 2579번 "계단 오르기" 문제를 다뤄본다.일단 문제를 보자. 이 문제는 동적계획법으로 접근하는 문제이다.문제에서 친절하게 규칙 3가지를 알려주었다.먼저 3번 규칙을 보면, 마지막 계단은 무조건 밟는다는 것이 규칙이다. 그렇다면, 마지막 계단을 밟았을 경우, 이전의 경우를 2가지로 생각할 수 있다.1. 마지막 계단 전의 계단을 밟은 경우.2. 마지막 계단 전의 계단을 밟지 않은 경우. 1번의 경우에는 마지막 계단 전의 계단을 밟았음으로, 마지막 계단 전전의 계단은 밟지 못한다.2번의 경우에는 마지막 계단 전의 계단을 밟지 않았음으로, 마지막 계단 전전의 계단을 밟고 왔다. 위 경우를 통해 점화식을 도출해보자. 1. dp[n] = dp[n-3] + array[n-1] + array..
-
백준 2156번 포도주 시식 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 16. 21:00
이번 글은 백준 알고리즘 문제 2156번 "포도주 시식" 을 다뤄본다.일단 문제를 보자. 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 6, 10, 13, 9, 8, 1 주어졌을 때, 6, 10, 9, 8 을 고르면 최대의 양 33이 정답이 된다. 이 문제..