섹션 2. 코딩테스트 - 04. 정렬
⬛ 04. 정렬
⬛ 04-1. 버블 정렬
🟦 버블 정렬
- 두 인접한 요소끼리 비교한 뒤, swap 연산 수행하며 정렬
- O(n2) 속도 느린 편
🟦 백준 2750번. 수 정렬하기 -1
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
package to_0605_6;
import java.util.*;
/* 2750번. 수 정렬 하기 1 - 버블 정렬 사용
* */
public class Main {
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++) arr[i] = kb.nextInt();
for(int i=0; i<n; i++) {
for(int j = 0; j<n-i-1; j++) {
if(arr[j] > arr[j+1]) {
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
for(int i=0; i<n; i++) System.out.println(arr[i]);
}
}⬛ 04-2. 선택 정렬
🟦 선택 정렬
- 대상에서 가장 크거나 작은 데이터를 찾아 선택 반복하여 정렬하는 방식
- 대상 데이터에서 최대/최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방식이다
- 시간 복잡도 O(N2) 비효율적이다.
🟧 설명
- 최솟값, 최댓값을 찾고, 남은 정렬 부분의 가장 앞 데이터와 swap 하는 것이 핵심
🟦 백준 1427번. 내림차순 정렬 - 선택 정렬로 풀이
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int[] A = new int[str.length()];
for (int i = 0; i < str.length(); i++) {
A[i] = Integer.parseInt(str.substring(i, i + 1));
}
for (int i = 0; i < str.length(); i++) {
int Max = i;
//i 뒷부분에서 가장 max값 찾고
for (int j = i + 1; j < str.length(); j++) {
if (A[j] > A[Max]) //내림차순이므로 최대 값을 찾음
Max = j;
}
//i로 찍은 값보다 max로 찍은값이 더 크면 두 값 swap
if (A[i] < A[Max]) {
int temp = A[i];
A[i] = A[Max];
A[Max] = temp;
}
}
//정답 출력
for (int i = 0; i < str.length(); i++) {
System.out.print(A[i]);
}
}
}⬛ 04-3. 삽입 정렬
🟦 삽입 정렬
- 이미 정렬된 범위에 아직 정렬 전의 데이터 중 적절한 값을 적절한 위치에 삽입시켜 정렬하는 방식
🟦 백준 11399번. ATM 문제
문제
인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.
줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.
줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
출력
첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.
풀이
- 이 문제는 필요한 최솟값을 구할 때, 결국 인출 시간 적은 순으로 먼저 인출하도록 하면 되는 거라 인출시간 오름차순으로 정렬한 뒤, 그값에 대한 구간합 S[i] ( s[i-1] + a[i] ) 을 구한 뒤, 구간합을 누적시켜 최종 sum을 출력하면 되는 문제이다.
- 물론 정렬 시 삽입 정렬을 이용해도 된다.
package to_0605_7;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int[] A = new int[str.length()];
for (int i = 0; i < str.length(); i++) {
A[i] = Integer.parseInt(str.substring(i, i + 1));
}
for (int i = 0; i < str.length(); i++) {
int Max = i;
//i 뒷부분에서 가장 max값 찾고
for (int j = i + 1; j < str.length(); j++) {
if (A[j] > A[Max]) //내림차순이므로 최대 값을 찾음
Max = j;
}
//i로 찍은 값보다 max로 찍은값이 더 크면 두 값 swap
if (A[i] < A[Max]) {
int temp = A[i];
A[i] = A[Max];
A[Max] = temp;
}
}
//정답 출력
for (int i = 0; i < str.length(); i++) {
System.out.print(A[i]);
}
}
}⬛ 04-4. 퀵 정렬
🟦 퀵 정렬
- 피봇값을 선정하여 해당값보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 분류하는 것을 반복하여 정렬하는 알고리즘
- 평균 시간복잡도 O(nlogN)
🟦 백준 11004번. k번째 수
문제
수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.
둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)
출력
A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.
코드
package to_0608_1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(in.readLine());
int[] A = new int[N];
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
quickSort(A, 0, N - 1, K - 1);
System.out.println(A[K - 1]);
}
public static void quickSort(int[] A, int S, int E, int K) {
if(S<E){
int pivot = partition(A, S, E);
if (pivot == K) { //K번째 수가 pivot이면 더이상 구할 필요 없음
return;
}
else if(K < pivot) { //K가 pivot보다 작으면 왼쪽만 정렬
quickSort(A, S, pivot - 1, K);
}
else if(K > pivot){ //K가 pivot보다 크면 왼쪽만 정렬
quickSort(A, pivot+1, E, K);
}
}
}
private static int partition(int[] A, int S, int E){
if(S+1==E) {
if(A[S]>A[E])swap(A,S,E);
return E;
}
int M = (S + E) / 2;
swap(A, S, M); // 중앙값을 1번째 요소로 이동하기
int pivot = A[S];
int i = S+1, j = E;
while (i <= j) {
while (pivot < A[j] && j > 0 ){ //피벗보다 작은 수가 나올때까지 j--
j--;
}
while (pivot > A[i] && i <A.length-1){ //피벗보다 큰 수가 나올 떄까지 i++
i ++;
}
if (i <= j) {
swap (A, i++, j--); // 찾은 i와 j를 교환하기
}
}
// i == j 피벗의 값을 양쪽으로 분리한 가운데에 오도록 설정하기
A[S] = A[j];
A[j] = pivot;
return j;
}
public static void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}⬛ 04-5. 병합 정렬
🟦 병합 정렬
- 분할 정복 방식을 사용하여 데이터 분할 후, 분할한 집합을 정렬하며 합치는 알고리즘
- 평균 시간복잡도 O(nlogN)
⬛ 04-6. 기수 정렬
🟦 기수 정렬
- 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다.
- 시간 복잡도 O(kn) : k는 데이터 자릿수
'알고리즘 이론 [개념] > [개념] 코테 알고리즘 공부 - 시즌 2' 카테고리의 다른 글
| 섹션 2. 코딩테스트 - 05. 탐색 - (2) 이분 탐색 (0) | 2023.06.13 |
|---|---|
| 섹션 2. 코딩테스트 - 05. 탐색 파트 - (1) DFS, BFS (0) | 2023.06.08 |
| 섹션 2. 코딩테스트 - 자료구조 (2) 파트 (0) | 2023.06.05 |
| 섹션 2. 코딩테스트 - 자료구조 (1) 파트 (0) | 2023.05.31 |
| 섹션 1. 코딩테스트 [준비] 하기 - 시간 복잡도, 디버깅 (0) | 2023.05.30 |