Java
-
[문제해결을 위한 창의적 알고리즘] partitioned (고급 p.68)알고리즘 2016. 12. 23. 17:57
이 문제의 해설은 굉장히 직관적이지가 않아 내 나름대로의 방법으로 풀어 보았다. 그림 설명과 결과값 출력이 조금 헛갈리게 설명되어 있으나, 출력 결과 값을 보면 주어진 n을 분할해서 내림차순 형태의 배열을 출력한다고 간단히 이해한 후 문제를 접근하는 편이 훨씬 낫지 않나 싶다. import java.util.Scanner; public class Partitioned { public static int n; //n은 30이하의 자연수라고 제한되어 ㅇ public static int[] arr = new int[30]; // f는 k개의 정사각형 종이를 id번째의 배열에 몇개를 놓을 수 있는지를 계산 public static void f(int k, int id){ // k가 0, 즉 정사각형이 다 떨어졌..
-
[문제해결을 위한 창의적 알고리즘] 경찰차 1 (고급 p.170)알고리즘 2016. 12. 16. 18:14
이 문제는 중급에서도 다뤄진 적이 있는 문제이다. 해설에서 설명하고 있는 내용은 경찰차 두대의 위치를 다른 사건들의 지점과 함께 배열에 저장한 다음, 두개의 포인터를 가지고 두대의 경찰차를 다음 포지션으로 이동시켜가면서 거리의 합을 구한다. 모든 사건이 다 처리되었을 때, 이동거리가 최소가 되도록 하면 된다. 이 포스트에서는 먼저 다이내믹 프로그래밍을 이용하지 않은 경우의 솔루션을 보기로 한다. import java.util.Scanner; public class PatrolCarSol173 { // 사건의 개수가 최대 1000개 이므로 1002까지만 있으면 된다 public static int[][] E = new int[1002][2]; public static int n, m; public stat..
-
[문제해결을 위한 창의적 알고리즘] 이진 암호화 (고급 p.58)알고리즘 2016. 12. 3. 16:43
이 문제는 주어진 길이 내의 문자가 모두 일치하지 않을 때, 길이를 반으로 나눠 다시 해당 길이내의 문자가 모두 같은지를 확인하는 방법을 묻고 있다. 이 아이디어만 잘 이해한다면 쉽게 풀 수 있는 문제로 보인다. 재귀호출을 통해 아래와 같이 구현할 수 있다. 모든 문자가 0 혹은 1인지를 판단하기 위해 각 숫자를 더한 것에 유의하시기 바랍니다. import java.util.Scanner; public class BinaryEncryptionSol61 { // 필요한 문자열 길이를
-
[문제해결을 위한 창의적 알고리즘] 영역 구분 (고급 p.51)알고리즘 2016. 11. 24. 12:57
이 문제는 주어진 영역을 반으로 나누어 가며 그 영역이 하얀색으로 다 채워졌는지 혹은 회색으로 다 채워졌는지 확인하는 문제이다. 해결 방법은 주어진 영역을 반으로 나눠가며, 시작 지점과 끝나는 지점 (혹은 정사각형 영역 크기)가 하나의 색으로 다 채워졌는지 확인하고 그렇지 않다면 다시 4등분하여 다시 하나의 색으로 채워졌는지 확인해 나가는 것이다. 코드에서 유의할 만한 사항은 다음과 같다. 1) 2의 배수의 배열 크기를 지정할 때
-
[문제해결을 위한 창의적 알고리즘] Combination (고급, p29)알고리즘 2016. 9. 16. 16:00
이 문제는 점화식 유도를 연습하기에 매우 좋은 문제라는 생각이 든다. n개 중에서 k를 고를 때, n개 중에서 k-1개를 고르는 것과 어떤 관계가 있을 지를 생각해 보면 쉽게 점화식을 유도할 수 있다. 또한 교재에서 곱하기를 먼저 다하고 나누기를 하는 것 보다는 나누기를 먼저하고 곱하기를 하는 것이 overflow가 발생하지 않도록 한다는 팁도 유용해 보인다. import java.util.Scanner; public class Combination { // n개 중에서 선택 (1
-
[문제해결을 위한 창의적 알고리즘] 별 그리기 (고급, p24)알고리즘 2016. 9. 15. 12:29
이 문제는 비교적 간단한 알고리즘으로 풀이의 설명을 잘 읽어보면 쉽게 이해할 수 있는 문제이다. 다만, 자바의 char array를 출력할 때, 포인터 주소값을 지정하는 것은 어려우므로 array 처음부터 별을 넣도록 코드를 수정하였다. import java.util.Scanner; public class DrawStarSol28 { // 별 문자열 최대값 public static final int MAXN = 10000; // 별 문자 배열 선언 public static char[] star = new char[MAXN]; public static void f(int n) { if (n > 0) { // 재귀적으로 n이 1이 될때까지 호출 f(n-1); // star 배열을 index 0부터 사용하기 ..
-
[문제해결을 위한 창의적 알고리즘] 색상환 (고급, p131)알고리즘 2016. 8. 15. 19:45
이 문제는 점화식을 유추해 내기 그렇게 쉽지는 않은 문제였다. 그래서 해설에서도 점화식을 유도하는 데 상당한 분량을 할애하고 있다. 점화식이 이해가 된다면 코드를 이해하는 것은 큰 문제 없을 것 같다. 재귀함수를 통한 구현 방법을 먼저 아래에 적어 보겠다. C에서 #define은 자바에서 final 키워드를 이용해 처리하였다. import java.util.Scanner; public class ColorCircleSol136 { public static final int MOD = 1000000003; public static int f(int n, int k) { if (k>n/2) return 0; else if (k==1) return n; else return (f(n-2, k-1)+f(n-1,..