백준 2822: 점수 계산, 분할정복 알고리즘설명

https://www.acmicpc.net/problem/2822

문제 접근

1. 8크기의 2개의 정수형 배열을 준비하고 서로 같은 원소를 가지도록 복사한다.
2. 배열 하나를 정렬알고리즘을 사용해 정렬한다.
3. 정렬된 배열의 3번 원소보다 작은 원소들은 -1로 바꾸고 그 외 나머지 원소들은 모두 합한다.
4. 정렬되지 않은 배열의 원소가 -1이 아니면 출력한다.

⚠️ 합병정렬(Mergesort)과 빠른정렬(Quicksort)

머지소트와 퀵소트 둘다 분할정복 알고리즘이다.

분할정복알고리즘이란,

1. 문제를 작은 여러개로 나누는 분할과정
2. 나눈 문제를 해결하는 정복과정
3. 문제를 해결하고 합치는 통합과정으로 알고리즘이 이루어진다.
   
   합병정렬(Mergesort) :
   시간복잡도 : 최악 == 평균 == 최선 == O(NlogN)
   
   빠른정렬(Quicksort) :
   시간복잡도 : 최선 == 평균 O(NlogN), 최악 == O(N^2)
   

‼️두 알고리즘의 특징 비교

합병정렬 :

장점 :
    안정적이다. 정렬된 후 위치가 바뀌지 않는다.
단점 :
    배열을 이용해 정렬시 원본 크기의 메모리가 더 필요하다. ❗️공간복잡도 고려
사용 :
    메모리 크기에 구애받지 않는 프로그램 작성할 경우
    정렬이 되어있을 가능성이 있는 경우

빠른정렬 :

장점 :
    최선의 시간복잡도가 O(NlogN)이지만, 분할정복 알고리즘 중 가장 빠르다.
    합병정렬과 반대로 메모리공간을 필요로 하지 않는다.
단점 :
    불안정적이다. 정렬된 후 위치가 바뀔 수 있다.
    정렬된 알고리즘에 사용할 경우 시간복잡도가 O(N^2)가 되어 시간이 오래걸린다.
사용 :
    정렬되어있지 않는 데이터를 정렬할 경우 사용한다.
    공간복잡도를 고려해야할 경우 사용한다.

Tip

분할 정복 알고리즘 중복데이터는 어떻게 처리해야 하나요?

합병정렬의 경우)

합병정렬은 2개의 배열을 합쳐 하나의 배열로 만드는 방식으로 진행한다.
이때 중복데이터가 오더라도 임의의 하나의 배열에서 뽑아와 저장시킨다면 다음 시행에서 다른 배열의 중복된 값을 가져오므로 문제를 해결할 수 있다.

빠른정렬의 경우)

빠른정렬은 배열의 양 끝에서 원소를 하나하나 지정한 피벗원소와 비교하여 교차되는 지점의 원소와 피벗의 원소를 교환하는 방식으로 진행한다.
이와 관련된 코드를 아래에 맞게 상황에 맞춰 작성하면 된다.
중복 데이터가 없는 경우

 while(i < j)
 if(i > j)

중복 데이터가 있는 경우

 while(i <= j)
 if(i >= j)

MergeSort

#include <iostream>
using namespace std;

int sorted[8];
void combine(int l, int h, int mid, int *arr)
{
    int i = l;
    int j = mid + 1;
    int cnt = l;
    while(i <= mid && j <= h){
        if(arr[i] < arr[j])
            sorted[cnt++] = arr[i++];
        else
            sorted[cnt++] = arr[j++];
    }
    if(i > mid)
        while(j <= h)
            sorted[cnt++] = arr[j++];
    else
        while(i <= mid)
            sorted[cnt++] = arr[i++];
    for(int k = l; k <= h; k++)
    {
        arr[k] = sorted[k];
    }
}
void divide(int l, int h, int *arr){
    if(l == h)
        return;
    int mid = (l + h) / 2;
    divide(l, mid, arr);
    divide(mid + 1, h, arr);
    combine(l, h, mid, arr);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int sum = 0;
    int arr[8];
    int copy[8];
    for(int i = 0; i < 8; i++){
        cin >> arr[i];
        copy[i] = arr[i];
    }
    divide(0, 7, arr);
    for(int i = 0; i < 8; i++)
    {
        if(copy[i] < arr[3]){
            copy[i] = -1;
            continue;
        }
        sum += copy[i];
    }
    cout << sum << endl;
    for(int i = 0; i < 8; i++)
    {
        if(copy[i] != -1)
            cout << i + 1 << " ";
    }
}

QuickSort

#include <iostream>
using namespace std;

void quickSort(int l, int h, int *arr)
{
    if(h <= l)
        return;
    int p = l;
    int i = p + 1, j = h;
    int temp;

    while(i <= j)
    {
        while(i <= h && arr[i] <= arr[p])
            i++;
        while(j > l && arr[j] >= arr[p])
            j--;
        if(i > j){
            temp = arr[p];
            arr[p] = arr[j];
            arr[j] = temp;
        }
        else{
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    quickSort(l, j - 1, arr);
    quickSort(j + 1, h, arr);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int sum = 0;
    int arr[8];
    int copy[8];
    for(int i = 0; i < 8; i++){
        cin >> arr[i];
        copy[i] = arr[i];
    }
    quickSort(0, 7, arr);
    for(int i = 0; i < 8; i++)
    {
        if(copy[i] < arr[3]){
            copy[i] = -1;
            continue;
        }
        sum += copy[i];
    }

    cout << sum << endl;
    for(int i = 0; i < 8; i++)
    {
        if(copy[i] != -1)
            cout << i + 1 << " ";
    }
}