https://www.acmicpc.net/problem/2751
2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
[ 풀이 후기 ]
난이도 : ★☆☆☆ (Beginner)
문제 종류 : Sort
해결 방법 : Merge Sort
* 난이도 구분
★☆☆☆ (Beginner) : 알고리즘 적용만으로 해결 가능
★★☆☆ (Advanced) : 알고리즘을 활용하여 구현해야 해결 가능
★★★☆ (Pro) : 알고리즘을 활용한 구현 + 최적화 아이디어로 해결 가능
★★★★ (Expert) : Pro보다 발전된 최적화 아이디어로 해결 가능
문제
문제 분석
- 입력되는 수는 최대 100만개이고, 각각의 수도 100만 이하의 정수이므로, int 변수를 선언하도록 하자.
- 100만개의 수를 오름차순으로 정렬하자.
접근 방법1 : 무작정 비교해서 Sorting (버블 Sort)
입력 받은 N개의 수를 무작정 비교해서 정렬하는 방법으로 해보자.
0번 Index의 수를 1~4 Index 수들과 비교해서, 0번의 수가 더 크다면, 자리를 바꾸는 방식으로 해보자. (버블 Sort)
- 5 와 4를 비교한다. 5가 더 크니까 자리를 바꾼다.
- 5와 3을 비교한다. 5가 더 크니까 자리를 바꾼다.
- ...
- 5와 1을 비교한다. 5가 더 크니까 자리를 바꾼다.
같은 방식으로 또 해보자.
- 4 와 3을 비교한다. 4가 더 크니까 자리를 바꾼다.
- 4와 2를 비교한다. 4가 더 크니까 자리를 바꾼다.
- ...
- 4와 5을 비교한다. 5가 더 크니까 자리를 바꾸지 않는다.
이 과정을 모두 정렬될때까지 반복하면, 비교횟수와 시간복잡도는 다음과 같이 계산할 수 있다.
5를 기준으로 했을 때 4번 비교,
4를 기준으로 했을 때 4번 비교,
...
▶ 총 5 * 4 번 비교
▶ O( N * (N-1) )
▶ O(N²)
N=5 일때는 O(5²)으로, 시간이 얼마 걸리지 않지만,
위 문제의 경우 N=100만 이므로, O(100만²) 의 시간복잡도를 가지게 된다.
2초 내에 프로그램이 종료되어야 하므로, 이 방법으로는 해결할 수 없다.
※ O(1억) 인 경우 약 1초 걸린다고 판단하면 된다.
접근 방법2 : Merge Sort
위의 방식은 O(N²) 의 시간복잡도 이므로, 문제를 해결할 수 없다.
O(N log N) 의 시간복잡도를 가지는 Merge Sort로 해결해보자.
Merge Sort의 원리는 아래 포스팅을 참고하세요 :)
[자료구조][정렬][C/C++] Merge Sort (병합정렬)
[자료구조][정렬][C/C++] Merge Sort (병합정렬)
Merge Sort (병합정렬) 특징 비교를 통해 정렬하는 비교기반 정렬 알고리즘 Divide & Conquer (분할 정복) 알고리즘 시간 복잡도 : O(N*logN) N크기의 임시 배열 1개가 추가적으로 필요 Merge Sort 과정 이해하
dongdoridong.tistory.com
Merge Sort는 아래와 같이 4단계로 나눠서 구현할 수 있다.
- base condition : 종료 조건
- divide & conquer : 중간을 기준으로 나눠서 재귀
- merge : 나눠졌던 Data를 하나로 합치기 (임시 배열 활용, 아래 코드에서는 trr 배열)
- copy : 임시 배열의 Data를 원래 배열에 복사 (아래 코드에서는 A 배열)
const int LM = 1000000;
int A[LM + 5], trr[LM + 5];
void mergeSort(int s, int e) {
if (s >= e) return; // 1. base condition
int mid = (s + e) / 2; // 2. divide & conquer
mergeSort(s, mid);
mergeSort(mid + 1, e);
int i = s, j = mid + 1, k = s; // 3. merge
while (i <= mid && j <= e) {
if (A[i] < A[j]) trr[k++] = A[i++];
else trr[k++] = A[j++];
}
while (i <= mid) trr[k++] = A[i++]; // left쪽 Data가 남은 경우
while (j <= e) trr[k++] = A[j++]; // right쪽 Data가 남은 경우
for (i = s; i <= e; i++) A[i] = trr[i]; // 4. copy
}
이렇게 구현된 mergeSort 함수는 아래와 같이 main에서 호출하면 된다.
(첫번째 Data를 0번 Index에 저장하는 것이 아닌, 1번 Index에 저장했다.)
mergeSort(1, N); // Sorting
이제 main을 포함한 전체 코드를 살펴보자.
#include <stdio.h>
const int LM = 1000000;
int N;
int A[LM + 5], trr[LM + 5];
void mergeSort(int s, int e) {
if (s >= e) return; // 1. base condition
int mid = (s + e) / 2; // 2. divide & conquer
mergeSort(s, mid);
mergeSort(mid + 1, e);
int i = s, j = mid + 1, k = s; // 3. merge
while (i <= mid && j <= e) {
if (A[i] < A[j]) trr[k++] = A[i++];
else trr[k++] = A[j++];
}
while (i <= mid) trr[k++] = A[i++]; // left쪽 Data가 남은 경우
while (j <= e) trr[k++] = A[j++]; // right쪽 Data가 남은 경우
for (i = s; i <= e; i++) A[i] = trr[i]; // 4. copy
}
int main() {
scanf("%d", &N); // N 입력
for (int i = 1; i <= N; i++) {
scanf("%d", A + i); // N개의 수 입력
}
mergeSort(1, N); // Sorting
for (int i = 1; i <= N; i++)
printf("%d\n", A[i]); // 정렬된 수 출력
return 0;
}
제출 결과
'알고리즘 문제풀이' 카테고리의 다른 글
[Pro][삼성] 15942번 : 외계인 침공 - 1 (6) | 2023.01.25 |
---|---|
[Advanced][백준] 11650번 : 좌표 정렬하기 (4) | 2023.01.23 |
[Advanced][정올] 1190번 : 모두더하기 (4) | 2023.01.22 |
[Advanced][정올] 1318번 : 못생긴 수 (2) | 2023.01.21 |
[Beginner][백준] 24060번 : 알고리즘 수업 - 병합 정렬 1 (1) | 2023.01.17 |
댓글