Algorithm Cinema

입력되는 정수의 배열의 범위가 보장될때, 유용한 아주 간단하고 효율적인 좋은 알고리즘. package 정렬알고리즘; import java.io.*; //운팅 정렬(Counting Sort)은 정수 배열을 정렬하는 비교 없이 선형 시간에 수행되는 안정적인 정렬 알고리즘입니다 // 알고리즘은 입력 배열의 범위가 제한되어 있을 때 특히 유용합니다 public class 카운팅정렬 { public static void main(String[] args) throws IOException { int[] range = new int[10001]; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parse..

10989번: 수 정렬하기 3 (acmicpc.net) 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 수의 개수의 범위가 상당히 크다. 천만개.. 일단 시간복잡도를 고려하면 O(NlogN)을 사용해야할 생각을하겠다. 이 문제의 경우 하지만 더 좋은 시간복잡도를 활용할수있는 정렬 알고리즘이 있는데 바로 카운팅 정렬이다. 카운팅 정렬은 일반적으로 이 문제와 같이 input받는 정수의 범위가 주어질때 유용하다. 시간복잡도는 O(N+K)이지만. 이상적으로 웬만하면 O(N)에 수렴한다. 즉 상당히 효율적인 정렬이라고 할 수 있다. 또한 ..