알고리즘
-
[문제해결을 위한 창의적 알고리즘] 공주 구하기2 (고급, p191)알고리즘 2017. 2. 17. 17:07
앞선 포스트에서 메모이제이션 방법을 이용하여 푸는 방법을 적어보았다. 그러나 역시 동적계획법을 사용해야 성능이 보장된다고 할 수 있으므로, 이번에는 동적계획법 (Dynamic Programming) 방법을 이용해 푸는 방법을 알아보고자 한다. 책에는 오타가 있음을 유의한다. 아래에서 DT[a][b]=가는 다리오가 a의 위치 섬에, 오는 다리오가 b의 위치 섬에 있을 수 있는 모든 경우의 수라고 정의한다. import java.util.Scanner; public class SavePrincessSol197 { public static final int MOD = 1000;public static int n;// 풀이에서는 array size가 501로 선언되어 있으나 n이 3~20까지이므로 20이면 충분..
-
[문제해결을 위한 창의적 알고리즘] 공주 구하기 (고급, p191)알고리즘 2017. 2. 11. 20:58
이 문제도 중급에서 다뤘던 문제이지만, 여기서는 성능을 좀 더 개선해 볼 수 있는 방법으로 메모이제이션 기법을 이용한 풀이를 적어보고자 한다. 두명의 다리오가 있다고 하고 한명은 유시섬에서 후퍼섬으로 가고 한명은 후퍼섬에서 유시섬으로 오는 상황에서 f(a, b, k) = "가는 다리오가 a 위치의 섬에 있고, 오는 다리오가 b 위치의 섬에 있으며, 다음으로 방문할 섬은 k위치의 섬에 대해서 탐색하려고 하는 상태"로 정의한다. import java.util.Scanner; public class SavePrincessSol195 { public static final int MOD = 1000;public static int n;public static int[] D = new int[501];public..
-
[문제해결을 위한 창의적 알고리즘] 선물 (고급, p178)알고리즘 2017. 2. 11. 20:29
이 문제도 이전에 중급에서도 등장했던 문제이다. 그러나 마찬가지로 동적계획법 (Dynamic Programming)으로 풀려고 하면 방법이 잘 생각나지 않는다. 특히 무게의 합을 가지고 다이나믹 테이블을 만든다는 점을 유의해서 풀어야 한다. 아래에서 DT[k][b][c]= 현재 k개의 선물을 받았을 때, 길순이가 부피 b, 길삼이가 부피 c를 받을 수 있으면 1, 그렇지 않으면 0으로 정의한다. import java.util.Scanner; public class PresentSol190 { public static int n, W;public static int[] G = new int[21];public static int A, B, C;public static int ans = 0x7fffffff;..
-
[문제해결을 위한 창의적 알고리즘] 돌다리 건너기 (고급, p178)알고리즘 2017. 2. 11. 20:05
이 문제는 중급편에서도 나왔던 문제인데, 동적계획법 (Dynamic Programming)으로 풀려고 하면 다이내믹 테이블을 생각해 내기 쉽지 않은 문제로 보인다. 다이내믹 테이블이 어떻게 만들어지는지 보면서 풀어보면 좋을 것 같다. 아래에서 'DT[s][r]=s돌다리에서 r번 문자로 끝나는 모든 경우'이다. import java.util.Scanner; public class StoneBridgeSol183 { public static char[] rol = new char[30];public static char[][] dol = new char[2][120];public static int[][] DT = new int[2][30];public static int rc;public static in..
-
[문제해결을 위한 창의적 알고리즘] 경찰차 2 (고급, p170)알고리즘 2017. 2. 4. 21:33
앞선 포스트에서 가장 쉬운 완전탐색 방법으로 해결하는 코드를 소개한 적이 있다. 이 방법보다 보다 효율적인 방법으로 메모이제이션을 활용한 코드를 소개하고자 한다. import java.util.Scanner; public class PatrolCarSol174 { public static int[][] E = new int[1010][2]; public static int n, m, ans =987654321; public static int[][] DT=new int[1100][1100]; public static int min(int a, int b){ return a > b ? b : a; } public static int abs(int a){ return a > 0? a:-a; } public ..
-
[문제해결을 위한 창의적 알고리즘] 격자길 (고급, p163)알고리즘 2017. 2. 3. 17:54
이 문제는 0,0부터 n,m까지 갈 수 있는 길의 방법을 구하는 문제이다. 이전 포스트의 광석 수집 문제와도 비슷해 보인다. 한가지 신경쓸 점은 0,0부터 n,m까지 잇는 선보다 위쪽에 있는 점은 거쳐갈 수 없다는 점이다. 다이내믹 테이블이 채워지는 과정을 보면 더 이해가 쉬울 것같다. import java.util.Scanner; public class Crossway163 { public static int n, m; public static int[][] dt = new int[101][101]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); ..
-
[문제해결을 위한 창의적 알고리즘] 거스름돈 (고급, p156)알고리즘 2017. 2. 2. 13:30
거스름돈 문제는 중급에서도 다루었던 문제이다. 그러나 여기에서는 더 큰 숫자에 대해서 처리할 수 있도록 동적 계획법 (Dynamic Programming)으로 푸는 방법을 살펴보도록 하겠다. 아이디어는 1부터 주어진 금액까지의 배열을 만들고 각 동전으로 만들 수 있는 금액들을 만들어 보면서 동전이 가장 작은 숫자로 업데이트하는 방식이다. 해설에 설명된 것보다 좀 더 직관적으로 이해할 수 있는 방법으로 구현해 보았다. import java.util.Scanner; public class Change156 { public static int[] money = new int[10001]; public static void main(String[] args){ int m; int n; int[] coins = ..
-
[문제해결을 위한 창의적 알고리즘] 타일 채우기 (고급, p149)알고리즘 2017. 2. 2. 12:22
이 문제는 앞선 포스트에서도 재귀적 방법으로 풀어 본적이 있는 문제이다. 그러나 숫자가 커짐에 따라 기하급수적으로 계산량이 늘어날 수 있으므로, 여기서는 가장 효율적인 방법으로 접근해 보려고 한다. 책에서도 점화식을 n, n-1, n-2 사이의 관계와 n과 n/2사이의 관계를 설명하고 있다. 지금까지 문제 풀이 방법으로 보았을때, 상향식 동적 계획법 (Dynamic Programming)이 가장 빠른 접근 방법이나 책에서는 보여주지 않고 있다. 따라서 이 방법을 풀이해 보고자 한다. 중요한 것은 점화식을 유도해 내는 과정을 잘 이해하는 것이라고 생각된다. 1) n이 짝수이면, 절반씩 나눠 채우는 방법과 1칸씩을 내어논 상태에서 채운 다음 2칸을 채울 수 있는 2가지 방법을 곱한다. 2) n이 홀수이면, ..