DP
-
동전 교환 관련 문제 접근 :: 마이구미알고리즘 2017. 2. 23. 12:07
이번 글은 "동전 교환" 에 관한 알고리즘을 다뤄볼 것이다.백준 알고리즘 사이트에서 알고리즘 분류에서 "동전 교환"을 볼 수 있다.2293번 동전 1, 2294번 동전 2, 11047번 동전 0 문제를 통해 다룬다.동전 0 - https://www.acmicpc.net/problem/11047동전 1 - https://www.acmicpc.net/problem/2293동전 2 - https://www.acmicpc.net/problem/2294 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.) 생각해볼 수 있는 방법은 각 동전에 대한 경우의 ..
-
백준 1309번 동물원 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 2. 17. 22:38
이번 글은 백준 알고리즘 문제 1309번 "동물원"을 다뤄본다. 이 문제의 접근법은 동적계획법 즉, DP이다. 어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. 문제의 포인트는 가로, 세로로 붙어서 배치할 수 없고, 배열은 2 * N 배열이다. 배치할 수 있는 경우는 가로나 세로가 붙어있지만 않..
-
백준 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자리 수의 개수를 구하는 프로그램을 작성하시오.각 자리 수에 따라 줄어들지 않는 경우의 수를 구하면 된다.간단하게 나타..
-
LIS 최장증가수열 알고리즘 :: 마이구미알고리즘 2016. 12. 10. 11:55
이번 글의 주제는 LIS 알고리즘이다. LIS는 Longest Increasing Subsequence 로써 최장증가부분수열이라는 의미이다.시간복잡도 O(n^2)을 다룰 것이고, O(nlogn)의 경우는 링크를 보자. (관련 글) 백준 알고리즘 11053번 11055번을 가지고 진행할 것이다. 최장증가수열은 무엇인지 백준 알고리즘 사이트 문제만 읽어도 알 수 있다. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 위와 같은 경우가 증가 부분 수열이다. 본인은 이번 글에서 이 문제를 가..