memoization
-
[문제해결을 위한 창의적 알고리즘] 공주 구하기 (고급, 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..
-
[문제해결을 위한 창의적 알고리즘] 경찰차 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 ..