📍개념
1. 선택 정렬
- 처리되지 않은 데이터 중 가장 작은 데이터와 가장 앞 데이터를 교환하며 정렬하는 알고리즘.
- O(N^2)
public class Main {
public static void main(String[] args) {
int n = 10;
int[] arr = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };
for (int i = 0; i < n; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[min_idx] > arr[j]) {
min_idx = j;
}
}
// 가장 앞 데이터와 가장 작은 데이터 위치 교환
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
for (int i : arr)
System.out.print(i + " ");
}
}
2. 삽입 정렬
- 특정한 데이터를 적절한 위치에 삽입하여 정렬하는 알고리즘.
- O(N^2)이지만, 거의 정렬된 상태에서는 O(N)에 가까움
public class Main {
public static void main(String[] args) {
int n = 10;
int[] arr = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
// 바로 앞의 데이터와 비교
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
else break;
}
}
for (int i : arr)
System.out.print(i + " ");
}
}
3. 퀵 정렬
- 왼쪽부터 피벗보다 큰 데이터를, 오른쪽부터 피벗보다 작은 데이터를 찾아 서로 교환하여 정렬하는 알고리즘.
- O(NlogN)
public class Main {
public static void quickSort(int[] arr, int start, int end) {
if (start >= end)
return;
// 배열의 첫 번째 원소를 pivot으로 설정
int pivot = start;
int left = start + 1;
int right = end;
while (left <= right) {
// pivot보다 큰 left, pivot보다 작은 right 교환
while (left <= end && arr[left] <= arr[pivot])
left++;
while (right > start && arr[right] >= arr[pivot])
right--;
// left와 right 위치가 역전됐다면 pivot과 right 값 교환
if (left > right) {
int temp = arr[pivot];
arr[pivot] = arr[right];
arr[right] = temp;
} else {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
// 분할 후 반복
quickSort(arr, start, right - 1);
quickSort(arr, right + 1, end);
}
}
public static void main(String[] args) {
int n = 10;
int[] arr = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };
quickSort(arr, 0, n - 1);
for (int i : arr)
System.out.print(i + " ");
}
}
4. 계수 정렬
- 각 값의 빈도 수를 저장한 다음 그 값을 빈도수 만큼 출력하는 알고리즘. (비교 방식이 아니다.)
- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용.
- 데이터의 크기가 중복될 수록 유리하다.
- 최악의 경우에도 O(N+K)
public class Main {
public static final int MAX_VALUE = 9;
public static void main(String[] args) {
int n = 15;
int[] arr = { 7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2 };
// 최댓값까지 담을 수 있는 크기의 배열 생성
int[] cnt = new int[MAX_VALUE + 1];
// 빈도수 저장
for (int i = 0; i < n; i++) {
cnt[arr[i]] += 1;
}
// 빈도수 만큼 출력
for (int i = 0; i <= MAX_VALUE; i++) {
for (int j = 0; j < cnt[i]; j++) {
System.out.print(i + " ");
}
}
}
}
📖 [예제 6-1] 위에서 아래로
더보기
문제
- 하나의 수열에는 다양한 수가 존재한다.
- 이러한 수는 크기에 상관없이 나열되어 있다.
- 이 수를 큰 수부터 작은 수의 순서로 정렬해야한다.
- 수열을 내림차순으로 정렬하는 프로그램을 만드시오.
입력 조건
- 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1 <= N <= 500)
- 둘째 줄부터 N + 1 번째 줄 까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하 자연수이다.
출력 조건
- 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다.
- 동일한 수의 순서는 자유롭게 출력해도 괜찮다.
🔑 풀이
입력받은 후 Arrays.sort를 이용하여 내림차순 정렬하고 차례대로 출력한다.
import java.util.*;
public class Main {
public static void main(String[] args) {
// 입력
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
Integer[] arr = new Integer[N];
for (int i = 0; i < N; i++) {
arr[i] = scan.nextInt();
}
// 정렬
Arrays.sort(arr, Collections.reverseOrder());
// 출력
for (int i : arr)
System.out.print(i);
}
}
📖 [예제 6-2] 성적이 낮은 순서로 학생 출력하기
더보기
문제
- N명의 학생 정보가 있다.
- 학생 정보는 학생의 이름과 학생의 성적으로 구분된다.
- 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.
입력 조건
- 첫 번째 줄에 학생의 수 N이 입력된다. (1 <= N <= 100,000)
- 두 번째 줄부터 N + 1 번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다.
- 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.
출력 조건
- 모든 학생의 이름을 성적이 낮은 순서대로 출력한다.
- 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다.
🔑 풀이
HashMap을 사용하여 stream으로 정렬
import java.util.*;
import java.util.stream.Collectors;
public class Main {
public static void main(String[] args) {
// 입력
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
HashMap<String, Integer> students = new HashMap<>();
for (int i = 0; i < N; i++) {
String name = scan.next();
Integer score = scan.nextInt();
students.put(name, score);
}
// value(성적) 기준 정렬
List<Map.Entry<String, Integer>> entries = students.entrySet().stream().sorted(Map.Entry.comparingByValue())
.collect(Collectors.toList());
// 출력
for (Map.Entry<String, Integer> e : entries) {
System.out.println(e.getKey() + " " + e.getValue());
}
}
}
📖 [예제 6-3] 두 배열의 원소 교체
더보기
문제
- 동빈이는 두 개의 배열 A와 B를 가지고 있다.
- 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다
- 동빈이는 최대 K 번의 바꿔치기 연산을 수행할 수 있는데,
- 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다.
- 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야한다.
- N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.
- 예를 들어 N = 5, K = 3이고, 배열 A와 B가 다음과 같다고 하자.
- 배열 A = [1, 2, 5, 4, 3]
- 배열 B = [5, 5, 6, 6, 5]
- 이 경우, 다음과 같이 세 번의 연산을 수행할 수 있다.
- 연산 1) 배열 A의 원소 '1'과 배열 B의 원소 '6'을 바꾸기
- 연산 2) 배열 A의 원소 '2'와 배열 B의 원소 '6'을 바꾸기
- 연산 3) 배열 A의 원소 '3'과 배열 B의 원소 '5'를 바꾸기
- 세 번의 연산 이후 배열 A와 배열 B의 상태는 다음과 같이 구성될 것이다.
- 배열 A = [6, 6, 5, 4, 5]
- 배열 B = [3, 5, 1, 2, 5]
- 이때 배열 A의 모든 원소의 합은 26이 되며, 이보다 더 합을 크게 만들 수는 없다.
입력 조건
- 첫 번째 줄에 N, K 가 공백으로 구분되어 입력된다. (1 <= N <= 100,000, 0 <= K <= N)
- 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
- 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수입니다.
출력 조건
- 최대 K번 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.
🔑 풀이
- N, K, A, B를 입력 받는다
- A와 B를 각각 오름차순 정렬한다
- A의 첫 번째 원소와 B의 마지막 원소를 교환한다( A 첫번째 원소가 더 작은 경우만)
- K만큼 2,3을 반복한 후 A 원소들의 합을 구하여 출력한다
import java.util.*;
public class Main {
public static void main(String[] args) {
// 입력
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int K = scan.nextInt();
int[] A = new int[N];
int[] B = new int[N];
for (int i = 0; i < N; i++)
A[i] = scan.nextInt();
for (int i = 0; i < N; i++)
B[i] = scan.nextInt();
// A의 최솟값과 B의 최댓값 교환
for (int i = 0; i < K; i++) {
Arrays.sort(A);
Arrays.sort(B);
if (A[0] < B[N - 1]) {
int temp = A[0];
A[0] = B[N - 1];
B[N - 1] = temp;
} else
break;
}
// A 합 출력
int answer = 0;
for (int a : A)
answer += a;
System.out.println(answer);
}
}
'알고리즘' 카테고리의 다른 글
[프로그래머스] 가장 큰 수 (java) (0) | 2023.06.22 |
---|---|
[프로그래머스] K번째수 (java) (0) | 2023.06.21 |
[백준] 2331. 반복수열 (java) (0) | 2023.06.15 |
[백준] 10971. 외판원 순회 2 (java) (2) | 2023.06.14 |
[백준] 1389. 케빈 베이컨의 6단계 법칙 (java) (0) | 2023.06.13 |