cpp를 복습하고 백준 알고리즘 문제를 풀면서 감을 익히고 있다. 그중 나름 공부가 되었던 것을 위주로 기록을 남기려 한다.
백준 2751번 문제이고 N개의 수를 입력받아 오름차순으로 정렬해 출력하는 간단한 문제이다. 겉보기엔 간단한 문제이지만 N의 입력 범위가 1 <= N <= 1,000,000 이므로 N이 커질 수록 프로그램 시간이 오래 걸릴 수 밖에 없다. 시간제한이 2초이기에 적절한 정렬 알고리즘을 구현해서 답을 내는 것이 중요하다. 빅오 표기법에 따라 복잡도가 적은 정렬 알고리즘을 찾는 것이 관건이다.
정렬 알고리즘 종류
1. 선택 정렬 빅오: O(n^2)
가장 단순한 방법이고 오름차순일 경우에 가장 작은 수부터 (배열의 앞부분부터) 채워나가는 것이다. 직관적인 방법이고 처음 배열을 정렬시킬 때 이 방법을 썼었다. 0번부터 정렬한다고 생각하면 최솟값을 찾아 0번 째 값이랑 바꾸고, 다시 1번부터 끝까지의 최솟값을 1번에 채우는 식으로 차례대로 채워간다.
알고리즘
1. 정렬되지 않은 배열 중 최솟값을 찾는다. (search)
2. 정렬된 배열 바로 뒤의 값이랑 최솟값을 바꾼다.
3. 모든 배열이 정렬된 상태일 때까지 반복한다.
ex) 4 2 1 5 3
-> 처음엔 모든 부분이 정렬되어 있지 않으므로 전체 중 최솟값을 찾는다.
-> 최솟값인 1과 정렬된 부분의 뒤(처음엔 정렬된 부분이 없으므로 0번째) 와 값을 바꾼다. 1 2 4 5 3
-> 1은 정렬된 배열이므로 그 다음 최솟값을 찾는다.
-> 정렬된 배열 뒤의 값과 최솟값이 일치한다. 1 2 4 5 3
-> 그 다음 최솟값인 3을 4와 바꾼다. 1 2 3 5 4
-> 그 다음 최솟값인 4를 5와 바꾼다. 1 2 3 4 5
복잡도
최악의 경우의 수는 n + (n-1) + ... + 2 + 1 이고, 즉 n(n+1)/2 이다. 빅오 표기법으로 O(n^2)이다.
2. 버블 정렬 빅오: O(n^2)
(오름차순 기준에서) 선택정렬이 최솟값부터 채우는 거라면 버블정렬은 최댓값부터 채우는 알고리즘이다. 다만 알고리즘이 선택정렬과 같은 방식이 아니다. 0번째 부터 바로 뒤의 값과 비교하면서 클 경우 서로의 자리를 바꾸는 방식이다. 그러면 최종적으로 정렬되지 않은 배열 부분 중에서 가장 큰 값이 가장 뒤에 밀려난다. (오름차순에서)
알고리즘
1. 0번을 기준 인덱스로 삼는다.
2. 기준 인덱스와 (기준인덱스 + 1) 의 값을 비교한다.
3. 기준 인덱스가 더 크면 자리를 바꾸고, 작으면 기준이 (기준인덱스 +1)이 된다.
4..최종적으로 기준이 되는 인덱스가 정렬되지 않은 배열의 부분 중 가장 큰 값이 되고 정렬된 상태를 이룬다.
ex) 4 2 1 5 3
-> 2 4 1 5 3
-> 2 1 4 5 3
-> 2 4 1 3 5
-> 2 1 4 3 5
-> 2 1 3 4 5
-> 1 2 3 4 5
복잡도
최악의 경우는 (n-1) + (n-2) + ... + 2 + 1 이고, 즉 n(n+1)/2 이다. 빅오 표기법으로 O(n^2)이다.
3. 삽입 정렬 빅오: O(n^2)
특정 값이 정렬된 배열의 어느 인덱스에 삽입되어야 하는지를 파악하고 넣는 알고리즘이다. 1번부터 끝까지 차례로 이동하면서 해당 값이 정렬된 배열의 어느 부분에 삽입되어야 할지를 알고 넣는다.
알고리즘
1. 1번 값이 0번 값보다 큰지 작은지를 비교하고 작으면 자리를 바꾼다.
2. 2번 값이 더 큰 값이 될 때까지 바로 앞과 비교하며 자리를 바꾼다.
3. 3번, 4번 .... 끝까지 진행한다.
ex) 4 2 1 5 3
-> 2 4 1 5 3
-> 2 1 4 5 3
-> 1 2 4 5 3
-> 1 2 4 3 5
-> 1 2 3 4 5
복잡도
최악의 경우는 (n-1) + (n-2) + ... + 2 + 1 이고, 즉 n(n+1)/2 이다. 빅오 표기법으로 O(n^2)이다.
4. 병합 정렬 빅오: O(n*logn) log의 밑은 2다.
병합정렬은 이미 sorting 된 두 배열을 sorting 시키면서 합치는 것이다. 그럼 배열을 쪼개서 각 배열을 각각 정렬 시키는 것은 똑같지 않나 싶었는데 병합 작업을 한 번 하는 것이 아니라 배열의 크기가 1이 될 때까지 쪼개는 것이다. 그러면 크기가 1인 배열은 어차피 sorting 된 상태이므로 따로 sorting 작업 없이 병합만 잘 하면 되는 것이다. 이 개념을 분할정복(Divide and Conquer) 방식이라고 한다.
알고리즘
1. 배열의 크기를 2로 나눈 기준점으로 배열을 나눈다.
2. 나눈 배열 각각에 또 병합정렬을 적용한다. (재귀함수)
3. 만약 배열의 크기가 1이라면 쪼개는 것을 멈춘다.
4. 각 배열의 맨 앞을 비교해가며 작은 것을 우선적으로 새 배열 앞 부분에 넣어준다.
5. 어느 한 배열에 값이 더 이상 없으면 남은 배열의 값들을 순차적으로 새 배열에 순서대로 넣어준다.
6. 모든 재귀함수가 끝나면 정렬된 새 배열을 얻을 수 있다.
ex) 4 2 1 5 3
-> 4 2 1 5 3
-> 4 2 1 5 3
-> 2 4 1 5 3
-> 2 4 1 3 5
-> 2 4 1 3 5
-> 1 2 3 4 5
복잡도
나누는 것은 logn(밑은 2) 이고 병합 시 비교하는 것의 최악의 경우는 n이다. 고로 빅오 표기법으로 O(n*logn)이다. (밑은 2)
5. 퀵 정렬 빅오: O(n*logn)
병합 정렬과 같이 분할정복(Divide and Conquer) 방식으로 진행되는 알고리즘이다. 마찬가지로 배열의 크기가 1이 되면 정렬된 상태라고 판단한다. 기준값을 두고 나누되 기준값보다 작은 값들의 배열과 큰 값들의 배열로 나누는 방식이다.
알고리즘
1. 랜덤으로 기준값을 정한다. 주로 pivot point라고 하는 것 같다.
2. p.p를 기준으로 가장 왼쪽의 값을 가르키는 left 변수와, 가장 오른쪽 값을 가르키는 right 변수를 둔다.
3. right 값이 p.p보다 작을 때까지 right를 왼쪽으로 한 칸 씩 이동한다.(left 보다 먼저) 근데 left랑 같아지면 멈춘다.
4. left 값이 p.p보다 클 때까지 left를 오른쪽으로 한 칸 씩 이동한다. 근데 left랑 같아지면 멈춘다.
5. right와 left의 값을 서로 바꾼다.
6. 이 과정을 right가 left 보다 클 때까지 반복한다.
7. left값과 p.p 값을 바꾼다.
7. p.p 기준으로 나뉜 두 개의 배열에 또 퀵정렬을 각각 쓴다.
아무래도 퀵 정렬은 예제가 조금 헷갈릴 것 같아 정리가 잘 된 블로그를 들고 왔다. 그림도 잘 나와있고 이 블로그가 가장 이해 잘 되었던 것 같다.
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
복잡도
비교는 n만큼 일어난다. 하지만 분할은 조금 다른데 분할이 보통은 logn에서 (밑은 2) 끝나는데 만약 정렬이 이미 정렬된 상태에서 퀵정렬을 한다면 분할이 모든 수에 대해 다 일어나기 때문에 n이 된다.
보통의 경우 -> O(nlogn)
정렬된 상태의 경우 -> O(n^2)
이다.
=======================================================================================
=======================================================================================
백준 2751은 위에서 언급했듯이 단순한 정렬문제가 아니다. 입력의 범위가 크기 때문에 시간복잡도를 계산해서 최악의 경우에도 주어진 시간안에 문제를 풀 수 있어야 한다. 배열의 요소 수가 1,000,000가 되는 경우를 최악의 수로 볼 수 있다. 그러면 선택, 버블, 삽입 알고리즘을 사용할 경우, 1,000,000 ^ 2 만큼의 연산이 들어갈 수 있기 떄문에 적절치 않다.
처음에 백준 2751번 문제를 풀 때, 이런 점을 고려하지 않고 cpp 의 <algorithm> 헤더파일에 있는 sort 함수를 끌어와 썼다가 시간초과가 났다. 그래서 sort 함수가 어떤 알고리즘을 쓰는지 보려고 <algorithm> 헤더파일을 찾아봤다. 근데 조금 의아한 점이 있었는데 sort 함수의 복잡도가 O(nlogn)이라는 것이다.
그래서 혹시나 입출력 과정에서 시간을 줄여보면 되지 않을까 싶어 main 함수 내에
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);를 추가해 주고
줄바꿈 함수도 cout << endl; 이 아닌 cout << '\n'; 으로 해주었다.
(입출력 시간 줄이기는 나중에 따로 포스팅으로 다룰려고 한다.)
입출력 시간을 줄여서 코드를 제출하니 되었다. 그래도 정렬 알고리즘들을 직접 짜보는게 좋을 듯하여 병합 정렬 알고리즘을 구현해서 다시 체출했다.
#include <iostream>
using namespace std;
void mergeSort(int* arr, int length){
if(length != 1){
int index = length/2;
int temp1[index]; int temp2[length-index];
for(int i =0;i<index;i++) temp1[i] = arr[i];
for(int i =0;i<length-index;i++) temp2[i] = arr[index+i];
mergeSort(temp1, index);
mergeSort(temp2, length-index);
//병합
int left=0, right=0; int arrIndex=0;
while(left != index && right != length-index){
if(temp1[left] < temp2[right]) {arr[arrIndex] = temp1[left]; left++;}
else {arr[arrIndex] = temp2[right]; right++;}
arrIndex++;
}
if(left == index) for(int i=right;i<length-index;i++) {arr[arrIndex] = temp2[i]; arrIndex++;}
else for(int i=left;i<index;i++) {arr[arrIndex] = temp1[i]; arrIndex++;}
}
}
int main(){
int N;
cin >> N;
int arr[N];
for(int i=0;i<N;i++) cin >> arr[i];
mergeSort(arr, N);
for(int a : arr) cout << a << endl;
return 0;
}
처음에 이렇게 짜서 제출했는데 시간초과가 떠서 다시 한 번 확인해보니 정말 바보 같이 알고리즘을 짰다. 배열을 분할할 때 그냥 처음과 끝 인덱스만 저장해서 기존 배열에 표시하는 방식으로 알고리즘을 짜면 되었는데 나는 새로운 배열을 하나 더 만들어서 옮겨 붙였던 것이다. 그래서 새로운 배열을 생성하고 값을 옮기는 데에 시간이 들어 시간초과가 났던 것 같다.
새롭게 인덱스로 분할을 표시해 다시 제출하니 문제가 정상적으로 풀렸다.
아래 코드는 각 정렬 알고리즘을 구현한 것이다. 나중에 퀵 정렬까지 구현해서 업로드 수정할 예정이다.
#include <iostream>
using namespace std;
void showArr(int* arr, int length) {
for (int i = 0; i < length; i++) cout << arr[i] << " ";
cout << endl;
}
//선택 정렬
void selectionSort(int* arr, int length) {
int index = 0, min, temp, check;
while (index != length) {
min = arr[index]; check = index;
for (int i = index; i < length; i++) if (min > arr[i]) { min = arr[i]; check = i; }
temp = arr[index];
arr[index] = min;
arr[check] = temp;
showArr(arr, length);
index++;
}
}
//버블 정렬
void bubbleSort(int* arr, int length) {
int index = 0, temp;
for (int i = length; i > 0; i--) {
for (int j = 0; j < i; j++) if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; }
showArr(arr, length);
}
}
//삽입 정렬
void insertSort(int* arr, int length) {
int temp;
for (int i = 1; i < length; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[i]) {
temp = arr[i];
for (int k = i; k > j; k--) arr[k] = arr[k - 1];
arr[j] = temp;
break;
}
}
showArr(arr, length);
}
}
//병합 정렬
void mergeSort(int* arr, int* sortedArr, int begin, int end){
int middle;
//분할
if(begin<end){
middle = (begin+end)/2;
mergeSort(arr,sortedArr,begin,middle);
mergeSort(arr,sortedArr,middle+1,end);
//병합
int left = begin; int right = middle+1; int arrIndex = begin;
while (left <= middle && right <= end) {
if (arr[left] < arr[right]) sortedArr[arrIndex] = arr[left++];
else sortedArr[arrIndex] = arr[right++];
arrIndex++;
}
if (left > middle) while(right <= end) sortedArr[arrIndex++] = arr[right++];
if(right > end) while(left <= middle) sortedArr[arrIndex++] = arr[left++];
for (int k = begin; k <= end; k++) arr[k] = sortedArr[k];
}
}
int main() {
int N;
cin >> N;
int arr[N];
int sortedArr[N];
for (int i = 0; i < N; i++) cin >> arr[i];
//선택정렬
//selectionSort(arr, N);
//버블정렬
//bubbleSort(arr, N);
//삽입정렬
//insertSort(arr,N);
//병합정렬
/*mergeSort(arr, sortedArr, 0, N-1);
cout << "==================" << endl;
showArr(arr, N);*/
return 0;
}
자료구조 시간에 공부했던 자료들이랑
https://hsp1116.tistory.com/33
이 블로그를 참고하면서 공부했다.
당장의 가벼운 문제를 해결하는데에 있어서는 코드를 직관적으로 아무렇게나 짜도 상관 없지만 코드가 길어져 프로그램이 무거워진다고 생각해보자. 그때는 프로그램에 걸리는 시간, 할당되는 메모리의 정도가 굉장히 중요해질 것이다. 간단한 프로그램을 짤 때도 항상 메모리와 복잡도를 고려하는 습관이 훗날 좋은 거름이 되어 프로그래밍 실력을 질적으로 향상 시킬 수 있을 것이다.
우선 정렬 알고리즘 부터 좀 익숙해 지자..... sort() 함수도 좋고 편리하지만 직접 짤 수 있어야지... 잊지말고 계속 익숙해지게 연습하자.
'알고리즘' 카테고리의 다른 글
| 알고리즘 유형 (DP, 다이나믹 프로그래밍) (0) | 2023.08.27 |
|---|---|
| 알고리즘 유형 (백트래킹) (0) | 2023.08.25 |
| 알고리즘 시간 줄이기 (입출력 시간 줄이기 : 버퍼 비동기화 & io untied) (0) | 2023.05.21 |
| cpp 복습 후 느낀 점 (0) | 2023.04.25 |
