[중급 알고리즘] 분할 정복, 정렬

분할 정복(Divide & Conquer)

- 분할 정복은 문제를 2개 또는 그 이상의 작은 부분 문제로 나눈 다음 푸는 것(분할)

- 푼 다음에는 다시 합쳐서 정답을 구함(정복)

- 대표적인 분할 정복 알고리즘

📌 퀵 소트

📌 머지 소트

📌 큰 수 곱셈(카라추바 알고리즘)

📌 FFT

 

✅ DP와 분할정복의 차이

작은 부분 문제가 중복이 되는가?의 차이다

 

DP는 작은 부분이 중복되기 때문에 메모이제이션으로 중복 제거

분할 정복의 경우에는 중복되지 않기 때문에 한 번씩만 연산하면 된다.

 

이분 탐색(Binary Search)

정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘

정렬이 전제되어야 한다.

 

리스트의 크기를 N이라고 했을 때, O(lgN)의 시간이 걸린다.

상한과 하한(Upper & Lower Bound)

- 상한: 큰 수 중 첫 번째 수

- 하한: 크거나 같은 수 중 첫 번째 수

 

이분 탐색 시에 찾아도 종료하지 않고 left, right를 조정하여 추가 탐색해나가야 한다.

머지 소트(Merge Sort)

- N개를 정렬하는 알고리즘

- N개를 N / 2, N / 2개로 나눈다.

- 왼쪽과 오른쪽을 각각 정렬한다.

- 두 정렬 결과를 합친다.

퀵 소트(Quick Sort)💡

- 평균적인 상황에서 최고의 성능을 자랑하는 알고리즘(O(NlogN))

- 피벗(pivot)을 하나 고른 다음, 그것보다 작은 것은 앞으로 큰 것은 뒤로 보낸다.

- 그 다음 피벗의 앞과 뒤에서 퀵 정렬을 수행

- 최악의 경우에는 O(N^2)이 걸린다.

 

int choosePivot(int low, int high) {
    return low + (high - low) / 2;
}

int partition(int low, int high) {
    int pivotIndex = choosePivot(low, high);
    int pivotValue = a[pivotIndex];
    // 맨 뒤로 보냄
    // 피벗 외의 숫자를 모두 정렬의 대상으로 삼기 위해
    swap(a[pivotIndex], high);
    int storeIndex = low;
    //
    for(int i = low;i < high;i++) {
        if(a[i] < pivotValue) {
            swap(a[i], a[storeIndex])
            storeIndex++;
        }
    }

    swap(a[storeIndex], a[high]);
    return storeIndex;

}

void quicksort(int low, int high) {
    if(low < high) {
        int pivot = partition(low, high);
        quicksort(low, pivot - 1);
        quicksort(pivot + 1, high);
    }
}

정렬

정렬을 어떻게 활용할 수 있는지에 대해 초점을 맞춘다.

선택, 버블, 삽입, 퀵, 힙, 병합 정렬 등...

O(NlogN)제일 빠른 거 쓰면 된다.

정렬을 직접 구현하는 것보다는 언어에 구현되어 있는 것을 사용하는 것이 좋다.

algorithm 헤더에 있는 std::sort를 쓰면 된다.

 

Java의 경우 비교하는 방법이 크게 2가지 방법이 있다.

- Comparable: 클래스 내에서 CompareTo를 구현

- Comparator: 별도의 클래스에서 equals와 compare을 구현

- 비교함수를 잘못 만들 경우 런타임 에러 발생 가능성 존재

 

Stable Sorting

같은 것이 있는 경우에 정렬하기 전의 순서가 유지되는 정렬 알고리즘

O(NlogN)에서는 MergeSort, O(N^2)에서는 Bubble Sort

C++에서는 stable_sort라는 알고리즘이 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Person {
    int age;
    string name;
};

vector<Person> members;

int main() {
    int n, age;
    string name;
    cin >> n;
    for(int i = 0;i < n;i++) {
        cin >> age >> name;
        members.push_back({age, name});
    }

    stable_sort(members.begin(), members.end(), [](Person a, Person b) {
        return a.age < b.age;
    });

    for(int i = 0;i < n;i++) {
        cout << members[i].age<< ' ' << members[i].name << '\n';
    }


}