Algorithm
-
[문제해결을 위한 창의적 알고리즘] 광석 수집 (고급 p.103)알고리즘 2017. 1. 27. 21:00
이 문제는 동적계획법 (Dynamic Programming)을 배울때, 가장 기본적인 유형으로 볼 수 있는 문제이다. 오른쪽과 아래쪽으로만으로 움직일 수 있다는 제약 조건 때문에, 왼쪽의 값과 위쪽의 값을 비교해 가면서 다이내믹 테이블을 업데이트하면서 답을 구해갈 수 있다. 나머지 설명은 책을 참고하면 되겠다. 책을 읽다 보니 한가지 수정했으면 하는 부분이 있는데 바로 106페이지의 T[i][j] 점화식에서 base case로 0 (i=0, j=0)이라고 되어 있는데, mine[0][0]으로 하는 것이 맞을 것 같다. import java.util.Scanner; public class Mining103 {public static int n;public static int m;// 책에서는 220까지 하..
-
[문제해결을 위한 창의적 알고리즘] 숙직 선생님 (고급 p.97)알고리즘 2017. 1. 26. 18:11
이 문제는 책에서 여러가지 형태로 다루고 있으므로, 추가적인 설명은 적지 않도록 하겠다. 가장 마지막 방법이 가장 효율적인 방법이므로, 그 방법을 나름의 방법으로 코딩해 보았다. 개인적으로는 책에 설명된 것보다 더 직관적인 코드라는 생각이 든다. 간략 설명 1) 현재 위치에서 3가지 능력 각각에 대해 갈 수 있는 위치를 업데이트 한다. 2) 해당 위치에 이미 업데이트 된 값이 있으면 작은 경우에만 업데이트 한다. 3) 만약 b의 위치가 지났다면 멈춘다. 4) b의 위치에 적혀 있는 값을 출력한다. import java.util.Scanner; public class DutyTeacher97 { // 선생님과 누군가의 위치 public static int a, b; // 3가지 능력 public stati..
-
[문제해결을 위한 창의적 알고리즘] Combination (고급 p.87)알고리즘 2017. 1. 21. 19:36
이 책의 앞부분에서 살펴본 문제 ([문제해결을 위한 창의적 알고리즘] Combination (고급, p29)) 동적 계획법 (Dynamic Programming)으로 해결해 보는 문제이다. ! (팩토리얼)을 빠르게 증가하므로 오버플로우를 내지 않고 계산하기 위해 이와 같은 방법으로 풀 수 있다고 한다. 여기서는 Dynamic Programming의 성능을 가장 최적화할 수 있는 상향식 풀이를 소개한다. (실제로 재귀함수를 이용한 하향식 접근 방법은 call stack이 오버헤드가 되어 성능이 좋지 않다). 문제에서 가장 중요한 것은 점화식을 유도하는 것인데, n개 중에서 k개를 고르는 방법은 1) n-1개에서 k개를 다 고르는 것과 2)n-1개에서 k-1개를 고르고 마지막 n번째 항목을 그냥 추가하는 방..
-
[문제해결을 위한 창의적 알고리즘] 숫자 뒤집기 (고급 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..