알고리즘
-
[문제해결을 위한 창의적 알고리즘] 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..
-
정보 올림피아드 대비 등알고리즘 2016. 8. 7. 21:34
요즘 한국에 소프트웨어 교육 바람이 불고 있다. 초등학생을 대상으로한 교육에서 부터, 대학교도 소프트웨어 교육을 의무화하는 등 소프트웨어를 전국민에게 가르치겠다는 시도가 여기저기서 나타나고 있다. (참고: 2017년 초·중등 교육에 별도 SW과목 생긴다, http://www.zdnet.co.kr/news/news_view.asp?artice_id=20140924105932) 개인적인 생각으로는 모든 국민이 소프트웨어를 할 수 있어야 한다고 생각하지는 않는다. 교육의 목적이 무엇인지는 무엇인지는 모르겠다. 세상의 문제를 소프트웨어적으로 혹은 공학적으로만 해결할 필요는 없다고 생각한다. 문제는 인문학적으로 해결할 수도 있고, 법으로, 사회적 합의로 혹은 예술로 해결할 수도 있다. 21세기, 소프트웨어가 세상..