자바
-
[문제해결을 위한 창의적 알고리즘] 색상환 2 (고급, p131)알고리즘 2017. 2. 1. 09:56
이전 포스트에서는 가장 기초적(?)인 방법을 소개했는데 이번에는 책에서 설명하는 방법 중 가장 효율적인 방법을 적어보고자 한다. 사실 점화식을 유도해 내는 과정이 좀 어렵게 느껴져서 그렇지 이전의 방법으로 문제를 풀 수 있었다면, 동적 계획법 (dynamic programming)으로 바꿔서 푸는 것은 그렇게 어려워 보이지 않는다. n개 색상중 k개를 뽑는 방법은 k가 1이면 n이라는 것과 k가 n/2를 넘으면 0이라는 것, 그외의 경우에는 n-2에서 k-1개를 선택하는 것과 n-1개에서 k개를 선택하는 것을 더하면 된다는 것을 유도해 내는 것이 중요하다. import java.util.Scanner; public class ColorCircleSol138 { public static final int ..
-
[문제해결을 위한 창의적 알고리즘] 잭과 콩나물 (고급 p.118)알고리즘 2017. 1. 30. 10:08
이 문제는 3중 중첩 for문을 사용하여 문제를 해결하고 있다. 문제 설명이 좀 아쉬운 점은, 주어진 m개의 가로 콩나물 외에 가로 콩나물을 더 추가할 수 있는데 주어진 2개의 콩나물 사이에 얼마든지 추가할 수 있다는 점이다. 즉, m개의 가로 콩나물이 1의 간격으로 주어지지만 추가하는 콩나물은 1 간격 사이에 얼마든지 추가할 수 있다. 비슷한 형태로 Floyd-Warshall (all pairs shortest path) 알고리즘도 참고해 보면 좋을 것 같다. import java.util.Scanner; public class JackAndBeanStalkSol123 { public static int n, m; public static int[] p=new int[501]; public static..
-
[문제해결을 위한 창의적 알고리즘] 앱 (고급 p.112)알고리즘 2017. 1. 28. 18:31
이 문제는 배낭 문제와 비슷해 보이지만, 메모리 제약상 테이블을 크게 만들 수 없는 경우 어떻게 해결할 수 있는지 보여주는 문제이다. 해설에 자세하게 설명되어 있으므로 추가적인 설명은 생략하기로 한다. 다이나믹 테이블을 어떻게 채워나가는지 보면 보다 이해가 쉬울 것 같다. import java.util.Scanner; public class App112 { public static int n;public static int M;public static int[] mem = new int[101];public static int[] cost = new int[101];public static int[][] dt = new int[101][10001];public static int max(int a, in..
-
[문제해결을 위한 창의적 알고리즘] 배낭 문제 (고급 p.107)알고리즘 2017. 1. 28. 12:30
책에도 설명되어 있듯이 이 문제는 굉장히 잘 알려진 문제이다. 그러나, 처음 접하는 사람들에게 특히 동적 계획법 (Dynamic Programming)으로 푸는 방법은 낯설게 느껴질 수 있다. 책에 굉장히 깔끔하고 간결한 풀이가 소개되어 있어서 그 코드를 자바로 작성해 보았다. 약간 해설이 부족한 점이 있는 것 같아 보충 설명을 더하였다. DT[i][j]의 정의 1) i는 물건 번호 2) j는 주어진 무게 3) DT[i][j]는 i번째까지 물건까지 고려했을 때 (풀이에서는 n번째부터 거꾸로 계산하고 있음 유의), j 무게가 남아 있다면 가질 수 있는 최대 가치 풀이와 더불어 실제 테이블에 어떤 값이 쓰여지고 있는지 보면 이해가 좀 더 쉬울 것 같다. 예제 입력: 4 5 2 3 1 2 3 3 2 2 정답:..
-
[문제해결을 위한 창의적 알고리즘] 광석 수집 (고급 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..