최근접 점쌍 문제 (closest pair problem)
여러 개의 1차원의 점을 표준 입력에서 읽은 후, 그 중 가장 가까운 거리에 있는 두 점의 한 쌍을 출력하는 문제이다.
임의조건 : 입력되어지는 숫자들은 공백으로 구분되며, 각각 10자리 이하의 자연수이다.
완전 탐색 알고리즘 (Brute-force algorithm)
최근접 점쌍은 완전 탐색 알고리즘을 사용하면 O(n2)의 시간에 찾을 수 있다. 이를 위해서는 아래와 같이 개의 모든 쌍들 사이의 거리를 계산하여 그 중 가장 가까운 두 점을 고르면 된다.
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; public class test { public static void main(String[] args) { ArrayList<Integer> numberList = new ArrayList<Integer>(); try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { String input = br.readLine(); String[] numStrList = input.split(" "); for (String numStr : numStrList) { numberList.add(Integer.parseInt(numStr)); } } catch (IOException e) { e.printStackTrace(); } Collections.sort(numberList); //정렬 Collections.reverse(numberList); //내림차순 정렬 //완전 탐색 알고리즘 int minDist = Integer.MAX_VALUE; int temp; for(int i=0; i<numberList.size()-1; i++){ for(int j=i+1; j<numberList.size(); j++){ temp = distance(numberList.get(i), numberList.get(j)); if (temp < minDist) { minDist = temp; System.out.println("minDist = "+minDist); System.out.println("result = "+numberList.get(i)+", "+numberList.get(j)); } } } } public static int distance(int p, int q) { int dis = p-q; return dis; } } | cs |
결과값
8 34 20 38 27 40 minDist = 2 result = 40, 38 |
참고
https://ko.wikipedia.org/wiki/%EC%B5%9C%EA%B7%BC%EC%A0%91_%EC%A0%90%EC%8C%8D_%EB%AC%B8%EC%A0%9C
http://stackoverflow.com/questions/36656225/divide-and-conquer-closest-pair-algorithm
'알고리즘 > 기초정리' 카테고리의 다른 글
| 숫자값이 너무 커서 int로는 커버가 안될 때 (0) | 2016.12.20 |
|---|