Java
-
[문제해결을 위한 창의적 알고리즘] 전깃줄 (고급, p249)알고리즘 2017. 4. 15. 21:06
이 문제도 풀이가 바로 떠오르지 않을 것 같은 문제이다. 문제에서는 교차하는 전깃줄을 없애는 방법으로 A(왼쪽) 전봇대 위치를 정렬하고난 후, B(오른쪽) 전봇대 위치의 숫자로 만들 수 있는 오름차순 순열의 최대 길이를 구하는 문제로 일단 변경시켰다. 그 다음 IDT (인덱스 트리)를 이용하여, B 전봇대의 값을 차례로 읽으면서 나보다 작은 값들이 몇개 있나를 업데이트 해 나간다. 모든 값을 읽은 다음 제일 윗 칸 즉, IDT 행렬의 첫번째 값이 오름 차순 순열을 만들 수 있는 최대 길이 값이 되고, 전체 입력 개수에서 최대 길이 값 만큼을 뺀 숫자가 결국 없애야 하는 전깃줄의 숫자가 된다는 풀이 내용이다. 풀이에서는 sort (정렬)을 위해 라이브러리를 사용하고 있으나, 여기서는 알고리즘을 배우는 사람..
-
[문제해결을 위한 창의적 알고리즘] 경비행기 (고급, p232)알고리즘 2017. 4. 1. 23:06
이 문제도 이분 탐색에 의한 결정 문제이다. 처음 문제를 보면서 해결 방법을 찾기란 쉽지 않을 수도 있지만, 이분 탐색 결정으로 푸는 해결 방법을 어느정도 머리속에 넣어 놓고 있으면, 풀만한 문제인 것 같다. 여기서는 자바로 구현하면서 스퀘어 루트 함수를 사용하지 않고 또한 큐도 사용하지 않고 구현해 보았다. import java.util.Scanner; public class LightFlightSol236 {static class P{public int x;public int y;} public static int N;public static int K;public static int T;// 시작점과 도착점을 제외하고 경유할 수 있는 비행장이 최대 1000개이므로, 1002개로 선언public st..
-
[문제해결을 위한 창의적 알고리즘] 암벽등반 (고급, p225)알고리즘 2017. 3. 11. 23:34
이 문제 역시 이분 탐색을 이용한 결정 문제이다. 문제에서 3/4이상을 지나다녀야 한다는 제약 조건이 있는데, 이를 위해 모든 지점에서 모두 출발해 보며 확인할 것이 아니라, 1/4을 초과한 지점만 확인해 보면 된다는 아이디어가 더해져 더 빠르게 수행할 수 있도록 푸는 방법을 적용해 보았다. import java.util.Scanner; public class ClimbingSol231 { public static int N; // N이 500까지 이므로 500으로 선언 public static int[][] M = new int[500][500]; public static boolean[][] chk= new boolean[500][500]; // 상,하,좌,우 탐색 방향 설정 public static..
-
[문제해결을 위한 창의적 알고리즘] 제자리멀리뛰기 (고급, p220)알고리즘 2017. 3. 10. 18:26
이 문제는 이분 탐색에 의한 결정문제이다. 이런 유형의 문제 해결 방법에 익숙하지 않다면 생각해 내기 굉장히 어려운 문제 유형이라는 생각이 든다. 코드를 잘 살펴보고 바로 작성할 수 있도록 익혀야 할 것 같다. 책에서 설명하고 있듯이 최대값의 최소값 구하기 등의 문제에 잘 적용할 수 있다. 책의 해설에서는 c의 알고리즘 라이브러리를 불러 쓰도록 되어 있으나, 여기서는 중급에서 소개한 퀵 정렬 코드를 이용하여 정렬을 구현하였다. import java.util.Scanner; public class JumpSol223 { public static int n, d, m; public static int[] S = new int[50001]; public static int ub = 1000000000; pub..
-
[문제해결을 위한 창의적 알고리즘] 두부 자르기2 (고급, p207)알고리즘 2017. 2. 24. 18:14
앞선 포스트에서는 완전 탐색으로 두부 자르기 문제를 푸는 방법에 대해 적어 보았다. 이번에는 동적 계획법으로 푸는 방법을 소개하고자 한다. 문제 해결을 위한 창의적 알고리즘 고급편의 가장 마지막에 있는 동적 계획법 문제이므로 난이도가 가장 높은 동적 계획법 문제로 보인다. import java.util.Scanner; public class TofuCutSol213 { public static int cu(){ return 1
-
[문제해결을 위한 창의적 알고리즘] 두부 자르기 (고급, p207)알고리즘 2017. 2. 19. 19:14
이 문제는 한국정보올림피아드에 출제되었던 문제인데, 굉장히 어렵다고 알려져 있다. 실제로 어떻게 동적계획법을 세워야할지 감이 잘 오지 않는다. 따라서 먼저, 완전 탐색을 이용한 방법으로 푸는 방법을 알아보고자 한다. import java.util.Scanner; public class TofuCutSol209 { // 두부가 선택되었는지 확인하기 위한 배열public static int[][] chk = new int[20][20];// 가격 배열, 풀이에서는 26x26배열이지만 이미 F가 마지막 배열이므로 26까지 필요 없다. 아래에서 A~F까지 알파벳에서 A를 빼서 배열 위치를// 확인하고 있으므로 6x6을 지정해야 한다. 자바에서 배열 초기화 방법이 C와 다르므로 아래와 같이 초기화했다.public..
-
[문제해결을 위한 창의적 알고리즘] Minimum Sum (고급, p200)알고리즘 2017. 2. 18. 23:09
이 문제는 비트 오퍼레이션을 통해 보다 빠르게 동작하는 방법을 알아보는 문제이다. 역시 동적계획법을 통해 문제를 푸는 방법을 알아본다. 비트 연산을 어떻게 적용하는지 알아두는 것이 핵심이라고 할 수 있겠다. import java.util.Scanner; public class MinSumSol205 { // 최대값 설정 public static final int INF = 987654321; // 입력 받을 공간 public static int[][] m = new int[21][21]; public static int bit, n; // 동적 테이블 선언 public static int[] DT = new int[1
-
[문제해결을 위한 창의적 알고리즘] 공주 구하기2 (고급, p191)알고리즘 2017. 2. 17. 17:07
앞선 포스트에서 메모이제이션 방법을 이용하여 푸는 방법을 적어보았다. 그러나 역시 동적계획법을 사용해야 성능이 보장된다고 할 수 있으므로, 이번에는 동적계획법 (Dynamic Programming) 방법을 이용해 푸는 방법을 알아보고자 한다. 책에는 오타가 있음을 유의한다. 아래에서 DT[a][b]=가는 다리오가 a의 위치 섬에, 오는 다리오가 b의 위치 섬에 있을 수 있는 모든 경우의 수라고 정의한다. import java.util.Scanner; public class SavePrincessSol197 { public static final int MOD = 1000;public static int n;// 풀이에서는 array size가 501로 선언되어 있으나 n이 3~20까지이므로 20이면 충분..