DP
-
백준 2602번 돌다리 건너기 :: 마이구미알고리즘 풀이/동적계획법 2019. 11. 10. 23:18
이 글은 백준 알고리즘 문제 2063번 "돌다리 건너기" 를 풀이한다. 정올 고등부 문제이자, 동적계획법(DP) 문제이다. 문제 링크 - https://www.acmicpc.net/problem/2602 절대반지를 얻기 위하여 반지원정대가 출발한다. 원정대가 지나가야할 다리는 두 개의 인접한 돌다리로 구성되어 있다. 하나는 이고 다른 하나는 이다. 아래 그림 1은 길이가 6인 다리의 한 가지 모습을 보여준다. 그림에서 위의 가로줄은 를 표시하는 것이고, 아래의 가로줄은 를 표시한다. 두 돌다리의 길이는 항상 동일하며, 각 칸의 문자는 해당 돌에 새겨진 문자를 나타낸다. 두 다리에 새겨진 각 문자는 {R, I, N, G, S} 중 하나이다. 출발 R I N G S R 도착 G R G G N S 반지원정대가..
-
백준 2591번 숫자카드 :: 마이구미알고리즘 풀이/동적계획법 2018. 1. 31. 20:50
이 글은 백준 알고리즘 문제 2591번 "숫자카드" 를 풀이한다.정올 출제 문제로써, 풀이 방법은 동적계획법을 통해 해결한다.문제 링크 - https://www.acmicpc.net/problem/2591 1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다.나중에, 적어 놓은 것에 맞게 다시 카드를 늘어놓으려고 보니, 방법이 여러 가지일 수 있다는 것을 알았다. 예를 들어 27123의 경우 아래와 같이 여섯 가지 다른 방법이 있다.카드의 숫자를 차례로 적어 놓은 것이 주어질 때, 위와 같이 그것을 가지고 거꾸로 카드의 배열을 찾으려고 한다. 가능한 카드의 배열이..
-
백준 1520번 내리막 길 :: 마이구미알고리즘 풀이/동적계획법 2017. 10. 12. 09:35
이 글은 백준 알고리즘 문제 1520번 "내리막 길" 을 풀이한다.풀이 방법은 DFS + DP(동적계획법) 을 통해 해결한다.DFS - http://mygumi.tistory.com/1021520번 - https://www.acmicpc.net/problem/1520 단순히 모든 경로를 탐색한다면, 시간 초과를 경험하게 된다.시간을 줄일 수 있는 방법은 다음과 같다.20 지점에 오면 더이상 탐색할 필요가 없이 경로가 존재한다는 것을 찾을 수 있다.존재하는 경로를 활용하는 방법으로써, 동적계획법을 이용할 수 있다. dp[y][x] = (y, x) 지점일 때 존재하는 경로의 갯수 DFS를 완벽히 이해하고 있다면, 쉽게 코드를 이해할 수 있다.* dp배열을 -1로 초기화한 이유는 방문여부를 위함이다. 1234..
-
백준 1890번 점프 :: 마이구미알고리즘 풀이/동적계획법 2017. 8. 15. 17:41
이번 글은 백준 알고리즘 문제 1890번 "점프" 를 다뤄본다.본인의 실력으로는 BFS, DFS 둘 다 시도해봤지만 도저히 맞을 수가 없었다.그리하여 동적계획법으로 문제를 접근했다. N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다.가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오. 각 칸을 기준으로 거리를 통해 갈 수 있는 지점에 경로의 개..
-
백준 10942번 팰린드롬? :: 마이구미알고리즘 풀이/동적계획법 2017. 6. 30. 19:55
이번 글은 백준 알고리즘 문제 10942번 팰린드롬? 을 다뤄본다.로켓처럼 빠른 회사인 쿠* 개발자 코딩 테스트에서 출제된 문제이기도 하다.문제 풀이의 최적의 접근법은 동적계획법이다.여기서는 동적계획법과 순수한 다른 방법을 다룬다. 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.각 질문은 두 정수 S와 E로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우..
-
백준 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 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉..