(해당 정리는 바킹독님, 동빈나님의 강의를 참조합니다)
바킹독 : https://www.youtube.com/channel/UCwFszkz9NbnQyQn5YbDfZtg
동빈나 : https://www.youtube.com/watch?v=94RC-DsGMLo

그리디(욕심쟁이) 알고리즘

• 동적프로그래밍(DP)이 지나치게 많은 일을 하는 것에서 착안된 알고리즘
  --> DP를 보완하는 알고리즘 이다.

• 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘
• 부분에서의 최적의 해가 전체적인 최적의 해가 되는 경우!
• 무조건 큰 경우대로 / 작은 경우대로 처럼 극단적으로 문제에 접근한다
  --> 정렬(sort)기법과 함께 사용되는 경우가 많다

ex) 거스름돈 주기 : 무조건 큰 화폐부터 거슬러 주면 된다 ! (최적의 해)

백트래킹 알고리즘

• 특정 조건을 만족하는 모든 경우의 수에 대해 수행하는 알고리즘
• 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

• 브루트포스(완전탐색)과 유사하지만, 특정 조건을 만족하는 경우의 수를 수행한다는 차이점이 있음
• 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아 간다
  --> 이것을 가지치기 한다고 한다

• 주된 사용
  : DFS등으로 모든 경우의 수를 탐색하는 과정에서,
  조건문 등을 걸어서 답이 절대로 될 수 없는 상황을 정의하여
  그러한 상황에서 탐색을 중지시킨 뒤 돌아가서 다른 경우를 탐색하게 한다.

---

예시 문제

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
int arr[10];
bool isused[10];
void func(int depth){
    if(depth == M){
        for(int i=0;i < M;i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }else{
        /* 백트래킹 핵심 부분 */
        for(int i=1;i<=N;i++)
        {
            if(!isused[i]){
                arr[depth] = i;
                isused[i] = true;
                func(depth+1);
                isused[i] = false;
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    func(0);
    return 0;
}

다익스트라 최단경로 알고리즘

[ Intro ]

• 그래프에서 정점끼리 최단 경로를 구하는 방법
  • 하나의 정점 --> 다른 하나의 정점까지 최단경로
  • 하나의 정점 --> 다른 모든 정점까지의 최단경로
    : Dijkstra 알고리즘
  • 하나의 목적지로가는 모든 최단 경로
  • 모든 정점끼리의 최단 경로를 구하는 문제
    : 플로이드 워셜 알고리즘

• 다익스트라 최단경로 알고리즘은 하나의 정점 --> 다른 모든 정점까지 최단경로 에 해당

---

[ 로직 ]

1. 모든 노드간 이동거리 배열을 INF(큰 값)으로 초기화
2. 출발 노드(정해짐)를 통해 갈 수 있는 경로 갱신
3. 갱신된 테이블을 통해 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택
4. 노드 간 이동거리가 더짧다면 갱신하며 수행
5. 다시 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택 후 반복!

---

[ 설명 ]

• 다익스트라가 제시안 최단경로 알고리즘
• 현재를 기준으로 방문하지 않는 점들 중 최단거리가 가장 짧은 노드를 선택하는 알고리즘
  --> 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는다
• 현재 상황에서 최선을 선택한다는 원리로 '그리디 알고리즘'으로 분류된다
• 간선이 음의 값을 가지면 성립되지 X
• 단순 값이 아닌 경로를 찾기 위해서는 추가적인 코드가 필요

• 구현 방법에 따라 시간복잡도가 상이하다
  • 배열로 구현 -> O(N^2)
  • 우선순위 큐로 구현 -> O(NlogN)
    : Heap 자료구조를 사용하면 노드를 선택하는 과정을 O(N)이 아닌 O(logN)으로 가능
    (최대 힙 -> 값이 큰 값이 먼저 나옴
    최소 힙 -> 값이 작은 값이 먼저 나옴)
    

---

[ 예시 & 코드 ]

priority_queue를 이용한 Dijkstra

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1e9 // 10억을 의미
using namespace std;
vector<pair<int,int>> graph[30001]; // 0인덱스는 사용하지 X
int dis[30001]; // 0인덱스는 사용하지 X
void dijkstra(int start){
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, start});
    dis[start] = 0;
    while(!pq.empty())
    {
        int dist = pq.top().first; // 비용
        int now = pq.top().second; // 현재 거쳐가는 지점의 인덱스
        pq.pop();
        if(dis[now] < dist) continue;
        /* i는 의미 없고 그냥 순회하기 위한 변수 */
        for(int i=0;i<graph[now].size();i++)
        {
            /* first-> 목적지 , second -> 목적지 까지 필요한 비용 */
            int cost = dist + graph[now][i].second; // 비용 계산
            if(cost < dis[graph[now][i].first]){ // first에는 목적지가 들어가있고 현재 기록된 값이랑 비교 검사
                dis[graph[now][i].first] = cost;
                // first까지 가는데 들어가는 비용 cost를 갱신하고 pq에 삽입
                pq.push({cost, graph[now][i].first});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M, C;
    int cnt=0, MAX=0;
    cin >> N >> M >> C;
    fill(dis, dis+30001, INF);
    for(int i=0;i<M;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        graph[a].push_back({b,c});
    }
    dijkstra(C);
    for(int i=1;i<=N;i++)
        if(dis[i] != INF){
            cnt++;
            MAX = max(MAX, dis[i]);
        }
    cout << cnt-1 << ' '<< MAX << '\n';
    return 0;
}

플로이드 워셜 알고리즘

[ 설명 ]

• 모든 노드 -> 다른 모든 노드까지의 최단경로 모두 계산하는 알고리즘
• 다익스트라 알고리즘과 마찬가지로 거쳐가는 노드를 기준으로 알고리즘을 수행
• 2차원 배열을 통해 모든 노드간 최단거리를 기록
• 2차원 테이블 배열을 점화식에 따라 갱신한다는 점에서 DP에 속함
  : 점화식에 맞게 배열을 갱신한다
  
• 시간복잡도가 무조건 O(N^3)이기 때문에 플로이드 워셜을 쓰는 문제의 입력은 500을 넘지 않게 주어진다

---

[ 코드 ]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1e9 // 10억을 의미
using namespace std;
int graph[501][501];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N,M;
    cin >> N >> M;
    /* 최단거리 테이블을 모두 무한으로 초기화 */
    for(int i=0;i<501;i++)
        fill(graph[i], graph[i]+501, INF);
    /* 자기 자신으로 가는 비용은 0으로 초기화 */
    for(int a=1;a<=N;a++)
        for(int b=1;b<=N;b++)
            if(a==b) graph[a][b] = 0;
    for(int k=1;k<=N;k++)
    {
        for(int a=1;a<=N;a++)
        {
            for(int b=1;b<=N;b++)
                /* a-> 출발노드, b-> 도착노드 , k-> 경유 노드 */
                graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b]);
        }
    }
    /* 수행된 결과를 출력 */
    for(int a=1;a<=N;a++)
    {
        for(int b=1;b<=N;b++)
        {
            if(graph[a][b] == INF)
                cout << "INF" << ' ';
            else
                cout << graph[a][b] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

• 3중 for문을 통해 각 모든 점에 대해 기존 경로 vs 경유 경로를 검사해서 작은 경로로 update!
• 구현 난이도는 Dijkstra보다 낮다

이진 탐색

[ 설명 ]

• 정렬된 상태에서 원소를 O(logN)의 시간복잡도로 찾는 탐색
• 

• 주로 파라메트릭 서치 유형 문제 풀이로 많이 사용됨
  

• 입력의 크기가 매우 큰 상황에서 일정 조건으로 탐색을 해야하면 이진탐색을 가장먼저 떠올려야 한다

• 특정 수의 개수를 구하는 과정을 O(logN)으로 수행할 수 있음
  • 
  • C++에서 upper_bound와 lower_bound를 이용해 countByRange를 정의한 후 leftValue와 ```rightValue에 같은 값을 넣으면 특정 수의 개수를 구할 수 있음

• C++ STL에 binary_search()가 구현되어 있으나 지정 값을 찾는기능에 제한된다

/* stl container */
  binary_search(arr.begin(), arr.end(), M);
/* array */
  binary_search(arr, arr+N, M);

---

[ 코드 - 반복문을 통한 이진탐색 구현 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
ll N,M,high;
vector<ll> arr(1000002);
/* 이진탐색 - O(logN) */
void bs(vector<ll>& arr, ll st, ll en){
    ll ans=0;
    while(st <= en)
    {
        ll tot=0;
        ll mid = (st + en)/2;
        for(auto a : arr)
            if(a > mid)
                tot += a-mid;
        if(tot < M)
            en = mid-1;
        else{
            ans = mid;
            st = mid + 1;
        }
    }
    cout << ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
    {
        cin >> arr[i];
        high=max(high,arr[i]);
    }
    bs(arr,0,high);
    return 0;
}

---

이분매칭 알고리즘

(Ref : https://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240613074&redirect=Dlog&widgetTypeCall=true&directAccess=false)

[ 설명 ]

• 두 집단 사이에서 Max Matching되는 경우를 구하는 것
  

• 노트북 집단과 사람 집단에서 최대로 연결될 수 있는 경우를 구하는 것
• 핵심
  : 내가 선택하려는 노드가 이미 선택되어 있을 때
  그것을 선택한 노드에게 다른 노드를 선택할 수 있도록 권장하는 것

---

[ 예시 코드 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#define ll long long
using namespace std;
vector<pair<int,int>> v(1010);
int work[1010];
bool finish[1010];
int T, N, M;
/* 이분 탐색 */
bool DFS(int x){
    for(int t=v[x].first;t<=v[x].second;t++)
    {
        if(finish[t]) continue;
        finish[t] = true;
        if(work[t] == -1 || DFS(work[t])){
            work[t] = x;
            return true;
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--)
    {
        v.clear();
        cin >> N >> M;
        for(int i=0;i<M;i++)
        {
            int a, b;
            cin >> a >> b;
            v.push_back({a,b});
        }
        /* 연결된 점의 좌표 초기화 */
        fill(work, work+1010, -1);
        int ans=0;
        /* 모든 점들에 대해 연결 */
        for(int i=0;i<M;i++)
        {
            /* 정점 방문 여부 초기화 */
            fill(finish, finish+1010, false);
            if(DFS(i)) ans++;
        }
        cout << ans << '\n';
    }
    return 0;
}

• BOJ 9576

크루스칼(Kruskal) 알고리즘

[ 필요 지식 ]

• 신장 트리(Spanning Tree)
  • 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
    ( 모든노드 포함 + 사이클 X )

• 최소 신장 트리 (MST = Minimum Spanning Tree)
  • 최소한의 비용으로 구성되는 신장 트리

[ 설명 ]

• 최소 신장 트리를 구하는 알고리즘 중 하나
  (MST를 구하는 다른 알고리즘으로 프림(Prim) 알고리즘이 있음 )

• Union-Find 알고리즘 이 사용
  • Union : 두 집합을 합치는 연산
    • 최초 모든 노드는 parent로 자기 자신을 가지고 있다
    • 두개의 노드 중 더 큰 번호에 해당하는 노드의 부모노드를 작은 노드로 갱신!
  • Find : 연결된 루트 노드를 찾는 것(여기서는 부모 노드를 찾는 것)
    • 재귀적으로 구현하여 연결된 가장 부모 노드를 찾는다
      --> findParent 구현시 부모 테이블 값을 바로 갱신하면 '경로 압축'이 가능함!

• 크루스칼(Kruskal) 알고리즘 로직
  1) 모든 간선에 대해 오름차순 정렬
  2) 아직 처리하지 않은 간선 중 가장 짧은 간선을 선택
  3) 사이클이 없으면(부모 노드가 같지 않으면) 현재 MST에 추가
      (사이클이 있으면 제외)

[ 코드 ]

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

using namespace std;
int N,M,ans,max_cost;
int parent[100002]; // 1~100000 사용
/* find 연산 */
int findParent(int x){
    if(x == parent[x]) return x;
    return parent[x] = findParent(parent[x]);
}

/* union 연산 */
void unionParent(int a, int b){
    a = findParent(a);
    b = findParent(b);
    if(a<b) parent[b] = a;
    else parent[a] = b;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    vector<pair<int, pair<int,int>>> edges;
    for(int i=0;i<M;i++)
    {
        int a, b, cost;
        cin >> a >> b >> cost;
        edges.push_back({cost,{a,b}});
    }
    // parent 초기화
    for(int i=1;i<=N;i++)
        parent[i] = i;

    // edges 정렬
    sort(edges.begin(), edges.end());

    for(int i=0;i<edges.size();i++)
    {
        int a = edges[i].second.first;
        int b = edges[i].second.second;
        int cost = edges[i].first;
        if(findParent(a) != findParent(b)){
            unionParent(a,b);
            max_cost = max(max_cost, cost);
            ans += cost;
        }
    }
    cout << ans - max_cost;
    return 0;
}

• findParent
  • find 연산
  • return parent[x] = findParent(parent[x]); 를 통해서 경로 압축을 바로 구현
    --> 바로 위 부모가 아니라 루트를 가리킬 수 있도록 바로바로 갱신!
• findUnion : union 연산
• parent 초기화
• edges 정렬
• MST 추가
  • 짧은 cost 순서대로 사이클이 형성하지 않으면 현재 MST에 추가