알고리즘 풀이/동적계획법
-
백준 2631번 줄세우기 [LIS] :: 마이구미알고리즘 풀이/동적계획법 2017. 4. 2. 00:33
이번 글은 백준 알고리즘 2631번 "줄세우기" 를 다뤄본다.이 문제는 LIS 알고리즘을 활용하여 해결할 수 있다. LIS 알고리즘, 최장증가수열은 본인이 다른 글에서 이미 다뤘었다.모른다면, 참고하고 읽으면 도움이 될 것이다. (LIS 알고리즘 관련글) 왜 LIS 알고리즘을 활용할 수 있는 지 문제를 보며 설명하겠다. KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리..
-
백준 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이 맞는 단어라는건 쉽게 알수 있잖아?선영: 예가 적절하지 않았네 ..
-
백준 2225번 합분해 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 3. 9. 20:11
이번 글은 백준 알고리즘 문제 2225번 "합분해" 를 다뤄본다.동적계획법으로 접근하는 문제이다.일단 문제를 보자. 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 문제는 간단하다.하지만 점화식을 생각하기에는 어렵다.간단하게 먼저 2차원 배열로 생각해보자.DP[K][N] = K개를 더해서 합이 N일 경우를 생각할 수 있다.이어서 그림을 통해 알아보자. 그림을 설명해보자면, 합 N을 만들기 위해서는 0~N까지 정수가 다양하게 존재한다.그 중 마지막 수를 L라고 가정하자.L 이전의 수들의 합은 N-L 이라는 것을 알 수 있다.또한 K개..
-
백준 10164번 격자상의 경로 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 3. 5. 23:59
이번 글은 백준 알고리즘 문제 10164번 "격자상의 경로" 를 다뤄본다.동적계획법으로 접근하는 문제이다.일단 문제를 보자. 격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다. 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다. 동그라미 표시된 칸을 무조건 지나가는 경로의 수를 찾는 문제이다.점화식을 만드는 방법은 문제에서 알려준 조건을 보면 쉽게 파악할 수 있다. 조건 1을 보면, 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다고 한다.기준이 되는 칸으로 올 수 있는 경우..
-
백준 2302번 극장 좌석 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 2. 25. 22:59
이번 글은 백준 알고리즘 2302번 "극장 좌석" 문제를 다뤄본다.이 문제의 키워드는 동적계획법(DP), 피보나치, 곱의 법칙이다.문제를 보자. 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 써 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다. 그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉..
-
백준 1309번 동물원 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 2. 17. 22:38
이번 글은 백준 알고리즘 문제 1309번 "동물원"을 다뤄본다. 이 문제의 접근법은 동적계획법 즉, DP이다. 어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. 문제의 포인트는 가로, 세로로 붙어서 배치할 수 없고, 배열은 2 * N 배열이다. 배치할 수 있는 경우는 가로나 세로가 붙어있지만 않..
-
백준 3745번 오름세 [LIS] :: 마이구미알고리즘 풀이/동적계획법 2017. 2. 17. 16:00
이번 글은 백준 알고리즘 문제 3745번 "오름세"를 다뤄본다.문제의 접근은 LIS(최장 증가 부분 수열) 알고리즘 문제이다.LIS O(nlogn) - http://mygumi.tistory.com/303 본인은 LIS 알고리즘을 다룬 글이 있다. (관련 글)관련 글은 시간 복잡도 O(n^2)으로 문제를 해결했다. 오름세 문제는 O(n^2)으로는 문제를 해결할 수 없다.시간초과를 초래하니 LIS의 또 다른 접근 방식으로 문제를 해결한다. 이번에 다룰 LIS의 시간복잡도는 O(nlogn)을 가진다.이분 탐색 또는 이진 탐색이라고 불리는 알고리즘을 이용하는 방식이다. (관련 글) 전체적인 의사코드로 표현하면 아래와 같다. // nums - 주어진 수열for each num in nums if(list.siz..