[21.08.25] SORT/ UNION-FIND/ 크루스칼알고리즘

- insert sort 삽입정렬

#include<iostream>
#include<vector>

using namespace std;

int main() {
    int arr[6] = { 4,9,11,8,6,2 };

    int result[6];

    for (int y = 0; y < 6; y++) {
        result[y] = arr[y];

        for (int x = y; x > 0; x--) {
            if (result[x - 1] < result[x])
                swap(result[x - 1], result[x]);
            else break;
        }
    }

    for (int x = 0; x < 6; x++)
        cout << result[x] << " ";

    return 0;
}

- 삽입정렬 구조체, compare함수 사용

#include<iostream>
#include<vector>

using namespace std;

struct node {
    int a;
    char b;
};

bool compare(node front, node back) {
    if (front.a < back.a) return true; //앞의 숫자가 더 작아야 한다 true
    if (front.a > back.a) return false; // 뒤에 숫자가 더 작으면 false
    return front.b > back.b;        // 숫자가 같을경우 문자비교
}

int main() {
    node arr[5] = {
        {1,'A'},{3,'A'},{2,'C'},{1,'B'},{3,'B'}
    };

    node result[5];

    for (int i = 0; i < 5; i++) {
        result[i] = arr[i];

        for (int j = i; j > 0; j--) {
            node front = result[j - 1];
            node back = result[j];
            if (!compare(front, back)) { //우선순위조건에 반하지 않을때 자리바꿈
                swap(result[j - 1], result[j]);
            }
            else break;
        }
    }

    for (int i = 0; i < 5; i++) 
        cout << result[i].a <<" " << result[i].b << endl;

    return 0;
}

- sort STL 사용하기

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main() {

    int arr[6] = { 3,6,2,1,5,8 };

    sort(arr, arr + 6); // 오름차순 (, less<int>()) default
    sort(arr, arr + 6, greater<int>()); //내림차순

    string str = "kevinchoi";
    sort(str.begin(), str.end());
    sort(str.begin(), str.end(), greater<char>());

    string brr[4] = { "kevin","bob","jane","kate" };
    sort(brr, brr + 4);
    sort(brr, brr + 4, greater<string>());

    vector<int>vect = { 6,3,4,6,5,2,1,9 };
    sort(vect.begin(), vect.end());
    sort(vect.begin(), vect.end(),greater<int>());

    vector<vector<int>>t = { {3,2},{1,3}, {6,2} };
    sort(t.begin(), t.end());
    sort(t.begin(), t.end(), greater<vector<int>>());

    pair<int, int> p;
    vector<pair<int, int>>pp = { {8,2},{3,3},{5,2} };
    sort(pp.begin(), pp.end(), greater<pair<int, int>>());

    return 0;
}

- 짝수우선 내림차순 (STL사용)

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

//짝수우선 내림차순
bool compare(int front, int back) {
    if (front % 2 == 0 && back % 2 == 1) return true;
    if (front % 2 == 1 && back % 2 == 0) return false;
    return front > back;
}

int main() {
    int arr[7] = { 2,6,41,3,7,4,8 };

    
    sort(arr, arr + 7, compare);

    return 0;
}

- 구조체배열 sort (숫자내림, 문자오름)

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

struct abc {
    char ch;
    int num;
};

bool compare(abc front, abc back) {
    if (front.num > back.num) return true;
    if (front.num < back.num) return false;
    return front.ch < back.ch;
}

int main() {
    
    abc arr[4] = {
        {'A',1}, {'B',2},{'B',1},{'A',9}
    };
    
    sort(arr, arr + 4, compare);

    return 0;
}

- Counting sort

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main() {
    int arr[7] = { 3,9,1,2,1,3,4 };
    int dat[11] = { 0 };
    int result[11];

    for (int i = 0; i < 7; i++) {
        dat[arr[i]]++;
    }

    for (int i = 1; i < 11; i++) {
        dat[i] += dat[i - 1];
    }

    for (int i = 0; i < 7; i++) {
        int t = arr[i];
        result[dat[t]--] = t;
    }

    return 0;
}

- union-find 독립된 data를 그룹화시켜서 관리

#include <iostream>

using namespace std;

int arr[200];

char findboss(char member) {
    if (arr[member] == 0) return member;
    char boss = findboss(arr[member]);
    return boss;
}

void setunion(char a, char b) {
    char aboss = findboss(a);
    char bboss = findboss(b);
    if (aboss == bboss) return;
    arr[bboss] = aboss;
}

int main() {

    setunion('A', 'B');
    setunion('E', 'F');
    setunion('B', 'F');
    setunion('F', 'A');
    setunion('C', 'D');
    
    char input1, input2;

    cin >> input1 >> input2;

    if (findboss(input1) == findboss(input2))
    {
        cout << "같은그룹";
    }

    else cout << "다른그룹";

    return 0;
}

- union-find 그룹은 몇개?

#include <iostream>
#include <vector>

using namespace std;

int arr[200];

char findboss(char member) {
    if (arr[member] == 0) return member;
    char boss = findboss(arr[member]);
    arr[member] = boss; //효율성
    return boss;
}

void setunion(char a, char b) {
    char aboss = findboss(a);
    char bboss = findboss(b);
    arr[bboss] = aboss; //bboss가 aboss 밑으로 들어감(같은그룹)
}

int main() {
    vector<string>vect = {
        "AE",
        "BD",
        "FE",
        "CE",
        "DB",
        "CA",
    };

    int len = vect.size();
    int cnt = len;
    for (int x = 0; x < len; x++) {
        if (findboss(vect[x][0]) != findboss(vect[x][1])) {
            setunion(vect[x][0], vect[x][1]);
            cnt--;
        }
    }

    cout << cnt;

    return 0;
}

- union-find를 사용하여 n개의 간선 연결시 cycle 존재여부 확인

#include <iostream>
#include <vector>

using namespace std;

int arr[200];

char findboss(char member) {
    if (arr[member] == 0) return member;
    char boss = findboss(arr[member]);
    arr[member] = boss;
    return boss;
}

void setunion(char a, char b) {
    char aboss = findboss(a);
    char bboss = findboss(b);
    arr[bboss] = aboss;
}

int main() {
    int n;
    cin >> n;

    for (int x = 0; x > n; x++) {
        int a, b;
        cin >> a >> b;
        if (findboss(a) == findboss(b)) { //보스가 같으면 싸이클존재
            cout << "cyle 존재";
            return 0;
        }
        setunion(a, b);
    }

    cout << "cycle 없음";

    return 0;
}

- 최소신장트리 (크루스칼알고리즘)

 1. 비용기준 sort

 2. 그룹화 union-find - 싸이클방지

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct node {
    char a;
    char b;
    int cost;
};

vector<node>arr = {
    {'A','B',5},
    {'A','C',3},
    {'A','D',2},
    {'A','E',6},
    {'B','C',7},
    {'B','E',8},
    {'C','D',4},
    {'C','E',2},
};

char brr[200];

bool compare(node front, node back) {
    return front.cost < back.cost;
}

//char findboss(char member) {
//    if (arr[member] == 0) return member;
//    char boss = findboss(arr[member]);
//    arr[member] = boss;
//    return boss;
//}
//
//void setunion(char a, char b) {
//    char aboss = findboss(a);
//    char bboss = findboss(b);
//    arr[bboss] = aboss;
//}

int main() {
    int n = arr.size();

    sort(arr.begin(), arr.end(), compare);

    int sum = 0;
    int cnt = 0;

    for (int x = 0; x < n; x++) {
        if (findboss(arr[x].a) != findboss(arr[x].b)) {
            setunion(arr[x].a, arr[x].b);
            sum += arr[x].cost;
            cnt++;
            if (cnt == 4) break; //정점의 갯수 -1 최소경로
        }
    }
    
    cout << sum;

    return 0;
}