Olympiad Informatics
-
[문제해결을 위한 창의적 알고리즘] 두부 자르기2 (고급, p207)알고리즘 2017. 2. 24. 18:14
앞선 포스트에서는 완전 탐색으로 두부 자르기 문제를 푸는 방법에 대해 적어 보았다. 이번에는 동적 계획법으로 푸는 방법을 소개하고자 한다. 문제 해결을 위한 창의적 알고리즘 고급편의 가장 마지막에 있는 동적 계획법 문제이므로 난이도가 가장 높은 동적 계획법 문제로 보인다. import java.util.Scanner; public class TofuCutSol213 { public static int cu(){ return 1
-
[문제해결을 위한 창의적 알고리즘] 두부 자르기 (고급, p207)알고리즘 2017. 2. 19. 19:14
이 문제는 한국정보올림피아드에 출제되었던 문제인데, 굉장히 어렵다고 알려져 있다. 실제로 어떻게 동적계획법을 세워야할지 감이 잘 오지 않는다. 따라서 먼저, 완전 탐색을 이용한 방법으로 푸는 방법을 알아보고자 한다. import java.util.Scanner; public class TofuCutSol209 { // 두부가 선택되었는지 확인하기 위한 배열public static int[][] chk = new int[20][20];// 가격 배열, 풀이에서는 26x26배열이지만 이미 F가 마지막 배열이므로 26까지 필요 없다. 아래에서 A~F까지 알파벳에서 A를 빼서 배열 위치를// 확인하고 있으므로 6x6을 지정해야 한다. 자바에서 배열 초기화 방법이 C와 다르므로 아래와 같이 초기화했다.public..
-
[문제해결을 위한 창의적 알고리즘] 공주 구하기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..
-
[문제해결을 위한 창의적 알고리즘] 색상환 2 (고급, p131)알고리즘 2017. 2. 1. 09:56
이전 포스트에서는 가장 기초적(?)인 방법을 소개했는데 이번에는 책에서 설명하는 방법 중 가장 효율적인 방법을 적어보고자 한다. 사실 점화식을 유도해 내는 과정이 좀 어렵게 느껴져서 그렇지 이전의 방법으로 문제를 풀 수 있었다면, 동적 계획법 (dynamic programming)으로 바꿔서 푸는 것은 그렇게 어려워 보이지 않는다. n개 색상중 k개를 뽑는 방법은 k가 1이면 n이라는 것과 k가 n/2를 넘으면 0이라는 것, 그외의 경우에는 n-2에서 k-1개를 선택하는 것과 n-1개에서 k개를 선택하는 것을 더하면 된다는 것을 유도해 내는 것이 중요하다. import java.util.Scanner; public class ColorCircleSol138 { public static final int ..