반응형
1. 문제 번호 10989
2. 문제 풀이
한줄 평가
- 병합 정렬(Merge Sort) : 분할 정복법을 이용하여 반씩 쪼개어 나중에 정렬한다. O(N logN)을 보장
- 카운팅 정렬/계수 정렬 : 배열에 중복 횟수를 카운팅 해서 한정된 범위에 있을때 가장 효과적이다. O(N)
문제를 먼저 정확히 파악
나의 문제풀이 방식 및 순서
* 나의 다양한 학습이 우선이기 때문에 다양한 방법을 생각 *
3. 소스 인증
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int [] numAry = new int[N];
int [] newAry = new int[N];
for(int i = 0; i < N; i++){
numAry[i] = Integer.parseInt(br.readLine()); // 4,2,5,7
}
mergeSort(numAry,newAry, 0, N - 1);
StringBuilder sb = new StringBuilder();
for(int i : numAry){
sb.append(i).append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
public static void mergeSort(int [] numAry,int [] newAry, int start, int end){
if (start < end){
int middle = (start + end) / 2 ;
mergeSort(numAry, newAry, start, middle);
mergeSort(numAry, newAry, middle+1, end);
merge(numAry, newAry, start, middle, end);
// 첫 번째 호출: mergeSort(numAry, newAry, 0, 3)
// middle = (0 + 3) / 2 = 1
// mergeSort(numAry, newAry, 0, 1)
// mergeSort(numAry, newAry, 2, 3)
// 두 번째 호출: mergeSort(numAry, newAry, 0, 1)
// middle = (0 + 1) / 2 = 0
// mergeSort(numAry, newAry, 0, 0) (기저 조건, 리턴)
// mergeSort(numAry, newAry, 1, 1) (기저 조건, 리턴)
// merge(numAry, newAry, 0, 0, 1)
// 세 번째 호출: mergeSort(numAry, newAry, 2, 3)
// middle = (2 + 3) / 2 = 2
// 호출: mergeSort(numAry, newAry, 2, 2) (기저 조건, 리턴)
// 호출: mergeSort(numAry, newAry, 3, 3) (기저 조건, 리턴)
// 병합: merge(numAry, newAry, 2, 2, 3)
}
}
public static void merge(int [] numAry, int [] newAry, int start, int middle, int end){
int i = start; //왼쪽 배열 인덱스
int j = middle + 1; //오른쪽 배열 인덱스
int k = start; //새배열의 인덱스
//1. i = 0, j = 1, k = 0
//2. 여기서 4 2를 비교하여 -> newAry[ 2 ], i = 0, j = 2, k = 1
while(i <= middle && j <= end){
if(numAry[i] <= numAry[j]){ //작은값을 넣기 위해서
newAry[k] = numAry[i];
i++;
} else {
newAry[k] = numAry[j]; //작은값을 넣기 위해서
j++;
}
k++;
}
// 3. 4를 붙인다. newAry[ 2, 4 ], i = 0, j = 2, k = 2
// 즉 왼쪽 하위 배열의 모든요소가 newAry가 복사되었으면(i>middle) 오른쪽 하위 배열의 남은 요소들 newAry에 복사
if(i > middle){
for(int t = j; t <= end; t++){
newAry[k] = numAry[t];
k++;
}
} else {
for(int t = i; t <= middle; t++){
newAry[k] = numAry[t];
k++;
}
}
// 정렬된 배열을 원본 배열에 삽입 -> 4 2 5 7 에 2 4 를 덮어씌워서 2 4 5 7 로 만들어준다.
for(int t = start; t <= end; t++){
numAry[t] = newAry[t];
}
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int cntNumAry[] = new int [10001]; //0~10까지면 총 11개의 숫자
while(N > 0){
cntNumAry[Integer.parseInt(br.readLine())]++;
N--;
}
for(int i = 1; i <= 10000; i++){
while(cntNumAry[i] > 0){
sb.append(i).append('\n');
cntNumAry[i]--;
}
}
System.out.print(sb);
}
}
- 실패 소스코드 -
4.추가 개념
1. 알고리즘 개요:
- 분할: 배열을 반으로 나누어 더 이상 나눌 수 없을 때까지 반복합니다.
- 정렬 및 병합: 분할된 배열을 정렬하면서 병합합니다.
2. 작동 방식:
- 분할: 배열을 반으로 나누어 더 이상 나눌 수 없을 때까지 반복합니다.
- 예: [3, 7, 8, 1, 5, 9, 7, 10, 2, 4] → [3, 7, 8, 1, 5], [9, 7, 10, 2, 4]
- 정렬 및 병합: 분할된 배열을 정렬하면서 병합합니다.
- 예: [3, 7, 8, 1, 5]는 [3, 7, 8]과 [1, 5]로 나누어지고 각각 정렬 후 병합하여 [1, 3, 5, 7, 8]이 됩니다.
- 같은 방식으로 [9, 7, 10, 2, 4]은 [2, 4, 7, 9, 10]으로 정렬됩니다.
- 최종적으로 [1, 3, 5, 7, 8]과 [2, 4, 7, 9, 10]을 병합하여 [1, 2, 3, 4, 5, 7, 7, 8, 9, 10]이 됩니다.
3. 시간 복잡도:
- 평균: O(N log₂N)
- 최악: O(N log₂N)
- O(N log₂N)을 보장하는 알고리즘
4. 공간 복잡도:
- O(N) (추가적인 배열 공간 필요)
5. 특징:
- 안정성: 안정 정렬 (같은 값의 원소가 순서를 유지함)
1. 빅 오 표기법 개요:
- 데이터 원소 N개에 대한 알고리즘 단계 수
- O(1), O(2), O(3), O(4) 는 모두 데이터 원소가 증가하더라도 1,2,3,4 단계로 고정된 알고리즘 유형
- 데이터가 늘어날 때 단계 수가 어떻게 증가하는가?
- O(N)은 데이터 원소가 증가할 때 단계 수가 비례(N개) 로 증가하는 알고리즘 유형
- 최악의 시나리오
2. 로그 log :
- 2를 몇 번 곱해야 N이 나올까? = log₂N
- 2를 3번 곱하면 8이 나온다. log₂8 = 3
- 1이 될 때까지 N을 2로 몇 번 곱해야 할까? = log₂N
3. O(logN) == O(log₂N)
- 데이터가 두 배로 증가할 때마다 한 단계씩 증가하는 알고리즘
- 데이터 원소 N개가 있을때 알고리즘에서는 log₂단계가 걸린다.
- 8개의 원소가 있을때 log₂8 는 3번의 단계를 거쳐야 한다.
출처 : welloff_jj님의 hyeojung.log블로그
5. 참조 블로그
불편함을 느끼실 경우 연락 주시면 곧 바로 삭제하도록 하겠습니다.
https://youtu.be/O-O-90zX-U4?si=xzvKx12A-w_10F8u
728x90
반응형
'알고리즘(BOJ) 문제풀이' 카테고리의 다른 글
| 카운팅 알고리즘(Counting Sort, 계수 정렬) (0) | 2024.06.29 |
|---|---|
| [BOJ/백준] 정렬_ 1427번 (0) | 2024.06.29 |
| [BOJ/백준] 정렬_ 25305번_ 퀵정렬(Quick Sort) (0) | 2024.06.24 |
| [BOJ/백준] 정렬_ 2587번_ 퀵정렬(Quick Sort) (0) | 2024.06.22 |
| [BOJ/백준] 정렬_ 2751번_ 병합정렬(Merge Sort) (1) | 2024.06.06 |
