알고리즘 풀이/동적계획법
-
백준 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이 정답이 된다. 이 문제..
-
백준 1912번 연속합 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 15. 23:50
이번 글은 백준 알고리즘 1912번 문제 "연속합" 을 다뤄본다.일단 문제를 보자.n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.문제는 쉽게 이해할 수 있다.연속되는 수들을 골라 최대의 합이 되는 수를 고르면 된다. 사이트에서 알고리즘 분류를 보면 알다시피 동적계획법으로 풀기를 권장하는 문제이다. 어떻게 점화식을 만들 수 있을까?점화식에 앞서 함정만 파악하면 쉽게 문제를 풀 수 있다. 임의의 수열 7 8 -9 10..
-
백준 1932번 숫자삼각형 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 3. 23:26
이번 글은 백준 알고리즘 문제 1932번 "숫자삼각형" 을 다뤄본다.이 문제의 풀이 방식은 DP(동적계획법)이다.문제를 한번 보자. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5위 그림은 크기가 5인 숫자 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.맨 위층을 0층으로 가정하겠다.1 층 : 7 -> 3 || 7 -> 82 층 : 7 -> 3 -> 8 || 7 -> 3 -> 1 || 7 -> 8 -> 1 || 7 -> 8 -> 0................
-
백준 2688번 줄어들지 않아 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 2. 20:47
이번 글은 백준 알고리즘 2688번 "줄어들지 않아" 문제를 다뤄본다.핵심은 DP라고 불리는 동적계획법이다.일단 문제를 보자. 어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.각 자리 수에 따라 줄어들지 않는 경우의 수를 구하면 된다.간단하게 나타..