Informatics
-
[문제해결을 위한 창의적 알고리즘] 전깃줄 (고급, 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..