Algorithm
-
[문제해결을 위한 창의적 알고리즘] 고급편 목록알고리즘 2016. 12. 3. 18:54
알고리즘 문제 해결 능력을 기르기 위한 공부를 하다보니, 정보올림피아드를 대비하는 청소년들을 위한 '문제 해결을 위한 창의적 알고리즘'이라는 책을 알게 되었습니다. 많은 고등학교 교사 등이 집필한 책으로 온라인으로 공개되어 있어 누구나 볼 수 있고, 비슷한 유형의 문제 풀이를 차근차근 해 나가다 보면 문제 해결 유형 파악 및 접근 방법을 알 수 있는 좋은 교재인 것 같습니다. 이 책을 보다 보니, 몇가지 보완했으면 좋을 것 같은 사항들이 있어 블로그를 쓰고 있습니다. 먼저 C코드로 작성되어 있어 자바로 배우고 싶은 학생들을 위해 코드를 제공하고자 합니다. 그리고 라이브러리를 최소화하여 구현할 수 있는 방법을 제안해 보고자 합니다. 또한, 오타 등의 내용을 교정하여 실제 동작하는 코드와 이에 대한 설명을 ..
-
[문제해결을 위한 창의적 알고리즘] 이진 암호화 (고급 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,..
-
[문제해결을 위한 창의적 알고리즘] 허프만 인코딩 (고급, 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