시간복잡도가 O(n²)인 정렬 알고리즘
: https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
1) 버블정렬
void Bubble_Sort(int arr[], int len) {
int i, j, tmp;
for (i = 0; i < len - 1; ++i) {
for (j = 0; j < len - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}2) 선택정렬
3) 삽입정렬
시간복잡도가 O(NlogN)인 정렬 알고리즘
: https://yxxshin.github.io/2020/03/13/2020-03-13-Sorting-Algorithm-O(NlogN)/, https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html
1) 병합정렬
: 분할 정복 알고리즘의 하나
분할 정복(Divide and Conquer)은 문제를 분리하여 각각을 해결한 다음, 결과를 모아 원래 문제를 해결하는 전략
2) 힙 정렬
: 완전 이진트리의 일종,
최대힙: 내림차순
최소힙: 오름차순
2750번 - 수 정렬하기
시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 삽입 정렬, 거품 정렬 등이 있습니다.
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
N(1 ≤ N ≤ 1,000)
//수 정렬하기 1 - 정렬 < 오름차순으로 정렬
import java.util.Scanner;
public class A_2750 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int a[] = new int[N];
for(int i=0;i<N;i++) a[i]= sc.nextInt();
sc.close();
int tmp; //비어있는 변수
for(int i=0;i<N-1;i++){
for(int k=0;k<N-1;k++){
if(a[k]>a[k+1]){
tmp = a[k];
a[k] = a[k+1];
a[k+1] = tmp;
}
}
}
for(int j:a){
System.out.println(j);
}
}
}
2587번 - 대표값 2
5개의 수의 평균과 중앙값을 구하는 문제
//대표값2 - 정렬
//다섯 개의 자연수가 주어질 때 이들의 평균과 중앙값을 구하는 프로그램
//중앙값: 주어진 수를 크기 순서대로 늘어 놓았을 때 가장 중앙에 놓인 값
import java.util.Scanner;
public class A_2587 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a[] = new int[5];
int sum =0;
for(int i=0;i<5;i++){
a[i]=sc.nextInt();
sum += a[i];
}
sc.close();
int tmp;
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
if(a[k]>a[k+1]){
tmp = a[k];
a[k]= a[k+1];
a[k+1]=tmp;
}
}
}
System.out.println(sum/5);
System.out.println(a[2]);
}
}
25305번 - 커트라인
k번째로 큰 수를 구하는 문제
내림차순으로 정리해 풀이!
//커트라인 - 정렬
//N명의 학생 중 K 명은 상받음 - 상 받는 커트라인 풀력
import java.util.Scanner;
public class A_25305 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int k = sc.nextInt();
int a[] = new int[N];
for(int i=0;i<N;i++) a[i]= sc.nextInt();
sc.close();
int tmp;
for(int j=0;j<N-1;j++){
for(int b=0;b<N-1;b++){
if(a[b]<a[b+1]){
tmp = a[b];
a[b]= a[b+1];
a[b+1] = tmp;
}
}
}
System.out.println(a[k-1]);
}
}2751번 - 수 정렬하기 2
시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다.
오ㅔ요... 내장함수 쓰라매.. 왜 시간초과..냐고....ㅎ ㅡㅇ.ㅡ,,,
Java에서 Arrays.sort에 primitive type array를 전달하면 dual-pivot quicksort를 수행하기 때문에 최악의 경우 O(N^2)이 됩니다. 이는 보통의 방법으로는 웬만해서는 O(N^2)이 안 되지만 이 문제에는 https://www.acmicpc.net/board/view/34491 에 의해 추가된 저격 데이터가 있습니다. Collections.sort를 사용하는 편이 좋습니다.
https://www.acmicpc.net/board/view/31887
https://devlog-wjdrbs96.tistory.com/68
정렬 내장함수 → 두 정렬의 차이:
1) Arrays.sort : 배열정리
import java.util.Arrays;
2) Collections.sort : 클래스의 객체 정리
import java.util.Collections;
Collections.sort 써도 시간초과 나용
import java.util.Arrays;
import java.util.Scanner;
public class A_2751 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int a[] = new int[N];
for(int i=0;i<N;i++) a[i] = sc.nextInt();
sc.close();
Arrays.sort(a);
for(int k:a) System.out.println(k);
}
}import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class A_2751 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0;i<N;i++) list.add(sc.nextInt());
sc.close();
Collections.sort(list);
for(int i=0;i<list.size();i++) System.out.println(list.get(i));
}
}
힙으로 풀어두 왜 시간초과에여ㅜㅜ
힙 정렬이 요구하는 것이 무엇인지 정확하게 알고 사용해야 합니다. 힙 정렬에서 시간 초과가 났다면 힙 정렬에서 해야 할 일을 정확하게 하지 않고 비효율적인 연산들을 했을 가능성이 매우 높습니다.
대표적으로, 원소 하나를 넣거나 뺄 마다 전체 힙을 재구성하면 안 됩니다. 해당 원소가 들어간 자리 / 빠진 자리를 처리하기 위해 O(logN)번을 넘는 연산이 있으면 안 됩니다.
import java.util.PriorityQueue;
import java.util.Scanner;
public class A_2751 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int a[] = new int[N];
PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
for(int i=0;i<N;i++) heap.add(sc.nextInt());
//for(int i=0;i<N;i++) heap.offer(sc.nextInt());
sc.close();
for(int i = 0; i < N; i++) System.out.println(heap.poll());
}
}여러해결법들을 찾아보니 Collections.sort 사용과 함께
새로운 출력방식의 사용!
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
//예외처리 해주기!
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String s = bf.readLine(); //String을 Line 단위로 받음
// .readLine()을 사용하면 return 은 String형이 기본이기 때문에 다른형타입을 사용하려면 형변환 필수!
int i = Integer.parseInt(bf.readLine()); //int
}
수 정렬하기 2 정답코드!
//수 정렬하기 2 - 정렬 < 오름차순으로 정렬
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class A_2751 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String Ns = bf.readLine();
int N = Integer.parseInt(Ns);
List<Integer> list = new ArrayList<>();
for(int i=0;i<N;i++) list.add(Integer.parseInt(bf.readLine()));
bf.close();
Collections.sort(list);
for(int k:list) System.out.println(k);
}
}
10989번 - 수 정렬하기 3
수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.
수 정렬 2랑 같은 코드 넣었다가 메모리초과!
설명대로 counting 정렬을 해보자!
Counting Sort (카운팅 정렬/ 계수정렬)
https://www.youtube.com/watch?v=Urmb0FpW6Hk
O(n)의 시간복잡도를 가지는 정렬
답은 아닌댕.. 답은 나오는데 시간초과에용
//수 정렬하기 3 - 정렬 / N개의 수가 주어졌을 때, 이를 오름차순으로 정렬
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class A_10989 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String Ns = bf.readLine();
int N = Integer.parseInt(Ns);
int list[] = new int[N];
for(int i=0;i<N;i++) list[Integer.parseInt(bf.readLine())]++;
bf.close();
for(int k=0;k<list.length;k++){
if(list[k]>0){
if(list[k]>1){
for(int i=0;i<list[k];i++) System.out.println(k);
}
else System.out.println(k);
}
}
}
}
수 정렬하기 3 정답코드
ㅠㅠ 왜 같은 코드여도 출력방식을 StringBuilder로 하면 통과이고 내껀 아닌지..
//수 정렬하기 3 - 정렬 / N개의 수가 주어졌을 때, 이를 오름차순으로 정렬
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class A_10989 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String Ns = bf.readLine();
int N = Integer.parseInt(Ns);
int list[] = new int[10001];
for(int i=0;i<N;i++) list[Integer.parseInt(bf.readLine())]++;
bf.close();
StringBuilder sb = new StringBuilder();
for(int i = 0; i < 10001; i++){
while(list[i] > 0){
sb.append(i).append('\n');
list[i]--;
}
}
System.out.println(sb);
// for(int k=0;k<list.length;k++){
// while (list[k]>0) {
// System.out.println(k);
// list[k]--;
// }
// }
}
}
1427번 - 소트인사이드
숫자를 정렬하는 문제
바로 위 카운팅 정렬로 해결
//소트인사이드 - 정렬 , 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬
//바로 이전에 배운 카운팅 정렬을 이용!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class A_1427 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String Ns = bf.readLine();
int N = Integer.parseInt(Ns);
bf.close();
int a[] = new int[10]; //0-9까지 1,000,000 자리수 하나씩!
while(N>0){
a[N%10]++;
N = N/10;
}
for(int k=9;k>=0;k--){
while (a[k]>0) {
System.out.print(k);
a[k]--;
}
}
}
}
11650번 - 좌표 정렬하기
좌표를 정렬하는 문제
시간초과ㅎㅎ......
// 좌표 정렬하기 - 정렬
import java.util.Scanner;
import java.util.Arrays;
//import java.util.Comparator;
public class A_11650 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int a[][] = new int[N][2];
//-100,000 < x < 100,000
for(int i=0;i<N;i++){
a[i][0] = sc.nextInt();
a[i][1] = sc.nextInt();
}
sc.close();
int cnt[] = new int[N];
int cnty[] = new int[N];
int small,y,sumo;
int q=0;
while(q<N){
small = 100000;
y=0; sumo=0;
Arrays.fill(cnty, 0);
for(int k=0;k<N;k++){
if(small>a[k][0] && cnt[k]<1){
small = a[k][0];
}
}
for(int j=0;j<N;j++){
if(a[j][0]==small){
if(a[j][1]==0) sumo++;
cnty[y]= a[j][1];
y++;
cnt[j]++;
q++;
}
}
if(y>1){
Arrays.sort(cnty);
for(int i=0;i<N;i++){
if(y==0) continue;
if(cnty[i]==0) {
if(sumo>0){
System.out.println(small+" "+cnty[i]);
sumo--;
}
}
else{
System.out.println(small+" "+cnty[i]);
y--;
}
}
}
else{
System.out.println(small +" " + cnty[0]);
}
}
}
}
수 정렬하기 3 정답코드
다들 람다식을 이용해서 간단히 푸신것을 봤어요.
유튜브로 공부하고 풀어보겠습니다..
11651번 - 좌표정렬하기 2
좌표를 다른 순서로 정렬하는 문제
1181번 - 단어 정렬
단어의 순서를 정의하여 정렬하는 문제
10814번 - 나이순 정렬
값이 같은 원소의 전후관계가 바뀌지 않는 정렬 알고리즘을 안정 정렬(stable sort)이라고 합니다.
18870번 - 좌표 압축
만약 정확한 값이 필요 없고 값의 대소 관계만 필요하다면, 모든 수를 0 이상 N 미만의 수로 바꿀 수 있습니다.
.png)