이분탐색결정
-
[문제해결을 위한 창의적 알고리즘] 경비행기 (고급, 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..