알고리즘
-
[문제해결을 위한 창의적 알고리즘] 숫자 뒤집기 (고급 p.83)알고리즘 2017. 1. 21. 18:46
이 책의 동적 계획법 (Dynamic Programming)의 첫번째 문제로 이 문제가 등장한다. 앞에서도 등장했던 문제로, 풀이를 보면 이 문제를 왜 이렇게 풀어야 하는지 조금 의심스럽긴 하다. 계산량이 줄어든다고 보기도 어렵고, 주어진 n까지 (최대 50,000) 메모리를 확보해야 한다. 앞선 포스트 ([문제해결을 위한 창의적 알고리즘] 숫자 뒤집기 (고급, p18))에서도 풀이를 한 적이 있지만, 다시 한번 풀이를 작성해 보았다. 또한 pow()와 log10()는 직접 구현하여 라이브러리 참조를 최소화하였다. 나머지 부분은 풀이를 참고하기 바란다. import java.util.Scanner; public class ReverseNumSol84 { // 최대 숫자까지 다이나믹 테이블 선언 publi..
-
[문제해결을 위한 창의적 알고리즘] partitioned 2 (고급 p.68)알고리즘 2016. 12. 30. 17:44
앞선 포스트에서는 본 문제에 대한 보다 직관적인 풀이를 적었습니다. 그러나 책의 해설이 보여주는 풀이도 나름 의미가 있고 이해하고 있는 편이 좋을 것 같다는 생각이 들어 여기에 적어보자 합니다. 책의 풀이를 보면 f(n, k) = k이하의 자연 수 합으로 n을 만들 수 있는 경우의 수 라고 되어 있는데, 예제 입력의 경우를 살펴보면 n=5일때, 5이하의 자연수 합으로 5를 만들 수 있는 경우의 수를 구하는 함수라고 보면 될 것 같습니다. (실제 출력은 경우의 수가 아니라 각 경우를 출력해야 한다는 점은 주의해야 겠지요.) 코드를 살펴 보겠습니다. import java.util.Scanner; public class PartitionedSol70 { // 문제에서 30이하의 수라고 했으므로 30개의 정수 ..
-
[문제해결을 위한 창의적 알고리즘] 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..
-
[문제해결을 위한 창의적 알고리즘] 고급편 목록알고리즘 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의 배수의 배열 크기를 지정할 때