자바
-
[문제해결을 위한 창의적 알고리즘] 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,..
-
[문제해결을 위한 창의적 알고리즘] 허프만 인코딩 (고급, p125)알고리즘 2016. 8. 15. 15:01
이 문제는 문제만 읽고 나서는 무언가 생략된 설명이 많은 듯한 문제다. 문제의 그림만 보고 가만히 생각해 보면 각 문자에 해당하는 값을 보고 암호화된 문자열 값을 하나씩 대입해 보는 것으로도 풀 수 있지 않을까라는 생각이 든다. 그렇다면 굳이 트리를 구현할 필요가 없기 때문이다. 그러나 문제에서 원하는 바는 트리를 탐색하는 것을 구현하고자 하는 것이다. import java.util.Scanner; public class HuffmanEncoding { public static int k;public static char[] longcode = new char[251];public static char[] hufftree = new char[1
-
[문제해결을 위한 창의적 알고리즘] 숫자 뒤집기 (고급, p18)알고리즘 2016. 8. 7. 22:18
이 문제는 재귀적 방법으로 접근하면 된다. 문제 접근법에 대해서는 책에 설명이 잘 나와 있으므로, 참고하면 이해할 수 있을 것이라고 기대한다. 자바 코드 및 코드 설명은 아래와 같다. import java.util.Scanner; public class ReverseNum18 { public static int n; public static void f(int i) { // 숫자가 0보다 크면 if (i > 0) { // 제일 마지막 자리를 출력한다. System.out.print(i%10); // 그리고 제일 마지막 자리를 없애고 재귀 호출 한다. f(i/10); } return; } public static void main(String[] args) { // TODO Auto-generated me..