전체 글
-
[문제해결을 위한 창의적 알고리즘] 영역 구분 (고급 p.51)알고리즘 2016. 11. 24. 12:57
이 문제는 주어진 영역을 반으로 나누어 가며 그 영역이 하얀색으로 다 채워졌는지 혹은 회색으로 다 채워졌는지 확인하는 문제이다. 해결 방법은 주어진 영역을 반으로 나눠가며, 시작 지점과 끝나는 지점 (혹은 정사각형 영역 크기)가 하나의 색으로 다 채워졌는지 확인하고 그렇지 않다면 다시 4등분하여 다시 하나의 색으로 채워졌는지 확인해 나가는 것이다. 코드에서 유의할 만한 사항은 다음과 같다. 1) 2의 배수의 배열 크기를 지정할 때
-
[문제해결을 위한 창의적 알고리즘] Distance of Nodes (고급, p47)알고리즘 2016. 9. 16. 23:26
이 문제는 결국 두 노드의 공통 조상을 찾아 거기까지 도착하는데 필요한 거리를 구하는 문제라고 할 수 있다. 문제의 해설을 읽어 보면 쉽게 이해할 수 있는 문제이다. 해설에서는 재귀적인 방법으로 풀었으나, 여기에는 반복적 접근으로 푼 코드를 공유하고자 한다. Recursive로 동작하는 코드보다 Iterative로 동작하는 코드가 call stack을 위한 메모리 할당이 필요 없으므로, 더 빠르게 동작한다. import java.util.Scanner; public class NodeDistance { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int first = 0; int second = 0; int f..
-
[문제해결을 위한 창의적 알고리즘] 타일 채우기 (고급, p35)알고리즘 2016. 9. 16. 19:13
이 문제에서 익혀야 할 핵심은 점화식을 만들때, n번째 항과 n-1번째 항과의 관계식을 구하는 것이 아니라, n번째 항과 n/2번째 항과의 관계를 구하는 방법이다. 이를 통해 굉장히 효율적인 점화식을 만들 수 있기 때문이다. 특히 n이 홀수일 때와 n이 짝수일 때를 점화식을 유도하는 방법을 잘 익히는 것이 필요해 보인다. import java.util.Scanner; public class FillTilesSol45 { public static int n; public static int m; public static long f(int k) { if (k0) return (f(k/2)*f(k/2+1)+2*f(k/2)*f(k/2-1))%m; // k가 짝수일 때 else return (f(k/2)*f(k..
-
[문제해결을 위한 창의적 알고리즘] 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..