팥빵 먹으면서 코딩하는 블로그

응용문제 : 백준 10989 카운팅 정렬(counting sort)란 데이터의 개수를 세어 정렬하는 방법이다. 시간복잡도는 O(N)으로 다른 정렬방법(quick sort, radix sort, etc.)보다 압도적으로 시간이 짧다. 하지만 데이터 값이 큰 경우에는 배열의 메모리 문제가 터질 수 있다는 단점이 있다. (아래 백준 문제의 최대 데이터 값은 10,000이다. 이보단 작은 데이터 값을 최대로 가진 문제에 카운팅 정렬을 쓰는 걸 추천한다.) 직관적으로 카운팅 정렬을 보려면 3개의 array가 필요하다. 1. 정렬되지 않은(정렬해야 할) 데이터를 모은 array 2. (index=데이터 값) / 각 데이터 값(=index)의 개수를 입력한 array 3. 덧셈 처리한 2번 array의 각 값에 -1..

응용 백준 문제 : 1929 에라토스테네스의 체는 소수를 찾는 방법이다. 방법 : 2부터 시작해 소수들의 배의 수를 자신을 제외하고 제거해 나가며 소수를 찾는다. @ 찾으려는 최대 구간과 크거나 가장 가까운 제곱수 의 자연수까지의 소수만 search하면 된다. 예를 들어, 1-120 구간 내의 소수를 찾는다고 하면 11의 제곱수는 121이므로 에라토스테네스의 체를 이용하면 2부터 11까지의 소수를 찾아 계산하면 된다. 아래는 백준 1929를 에라토스테네스의 체를 이용해 푼 코드 import java.util.Scanner; public class Main { static boolean [] array; //아무것도 넣지 않았을 때 모든 default는 false다 static int M, N; publi..