아쉬웠던 점

구역을 성북천으로 한정지은 만큼 위치 차이가 별로 나지 않아 데이터 하나하나의 위도와 경도의 값을 소숫점까까지 정확히 알아야 비교적 정확한 최단거리를 구할 수 있는데 성북천 데이터의 위도, 경도 값을 하나로 통일시키놓은 학우분들이 많아서 다른 위치의 쓰레기여도 같은 위치에 있는 쓰레기로 인식되는 것이 아쉬웠다.

csv 파일, 파이썬 코드

https://drive.google.com/drive/folders/1V1lWCFRn444FfEKeT-cPdDJJA7OV-bq2?usp=sharing

• 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 • 시간복잡도 O(VE) V: 정점 수, E: 간선 수 • 다익스트라 알고리즘이 모든 가중치가 양수인 경우에만 사용할 수 있는 반면, 벨만-포드 알고리즘은 노드 간의 간선 가중치가 음수인 경우에도 사용할 수 있다. ✲ 다만 시간 복잡도는 벨만-포드가 더 크기 때문에 가중치가 모두 양수라면 굳이 벨만-포드를 사용할 필요 없다.

음수 사이클이 문제가 되는 이유

단순 음수 간선일 경우 : 단순 경로이므로 그대로 가중치를 계산하면 된다. 사이클이 존재하나 양수값이 더 클 경우 : 사이클을 순환하여도 이득이 없으므로 그대로 진행한다. 사이클이 존재하고 음수값이 더 클 경우 : 사이클을 순환할 수록 가중치가 감소해 최소 비용을 찾는 입장에서 사이클을 무한히 순환하고 목적지에 도착함은 실질적인 최단 경로라 보기 어렵다. 적어도 동일 노드를 방문하면 안된다는 등 제약 조건이 있어야 할 것이다. ⭐️ 최단 거리는 순환되어서는 안된다는 가정을 담고 있으므로 경로(Edge) 길이는 |V|−1 이 된다.

벨만포드 알고리즘이 사이클을 판단하는 방법

다른 알고리즘들의 경우 대부분 if문에서 기존의 경로와 비교를 한 뒤 계속해서 이득이 되는곳을 찾는다. 하지만 벨만-포드는 '노드 to 노드'에 관점을 두기보다 경로 자체를 탐색하게 된다. 그래서 모든 경로를 대상으로 1번 탐색을 하고 이후 한번 더 탐색을 할 때 기존 값에서 줄어드는 값이 있다면 사이클로 판단하게 된다. 한마디로 보는 관점이 다르기 때문에 한번 더 돌릴 수 있는 것이다.

작동 원리

1️⃣ 시작 노드에 대해서 거리를 0으로 초기화, 나머지 노드는 거리를 무한으로 설정 2️⃣ 정점 수(n) -1 만큼 다음 과정을 반복 3️⃣ 매 반복 마다 모든 간선 확인 4️⃣ 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우, 거리 정보 갱신 5️⃣ n-1번 반복 이후, n번째 반복에서도 거리 값이 갱신된다면 음수 순환이 존재 ⭐️ 다익스트라와의 차이점은 매 반복마다 모든 간선을 확인한다는 것 (다익스트라는 방문하지 않는 노드 중에서 최단 거리가 가장 가까운 노드만을 방문)

예시

📌 위 그래프를 예시로 벨만포드 알고리즘을 적용해보자.

먼저 시작정점을 정하고 각 정점들의 값을 초기화 해주어야 한다. 이 예시에서는 시작점을 A로 정하겠다. 그리고 A만 길이 변수를 0으로 초기화 하고 나머지 정점들에 대해서는 양의 무한대를 지정한다.

시작점인 A 정점으로부터 연결되어 있는 노드들에 대해 Relaxtion 을 진행한다. • B 정점에 저장된 최단거리 값은 양의 무한대였는데, A로부터 B까지의 거리인 6이 더 작기 때문에 d[B]는 6이 되고, p[B]는 A가 된다. p[v]는 최단경로에서 정점 v 바로 직전에 나온 정점을 의미한다. • 같은 맥락으로 A로부터 D까지의 거리를 계산하게 되면 d[D]는 7이 된다.

이제 정점 A에 대한 Relaxation 이 끝났으니, 다른 정점들도 모두 Relaxation을 진행해야한다. 다음 정점은 B 정점이다(사실 순서는 상관없다). 우리는 시작점 A로부터 B와 연결된 모든 정점들 까지의 거리를 구하면 된다. • B와 연결된 C정점까지 도달하기 위해서는 A에서 B까지의 최단 거리인 6에 B에서 C로 이동하는 최단거리를 더해주면 된다. 현 시점에서 C까지 도달하는 최단거리는 양의 무한대로 설정되어 있으므로 간선 BC를 통해 연결되는 것이 가장 작을 수 밖에 없다. 따라서 d[C]는 6+5 인 11이 된다. • B와 연결된 정점 E에 도달하는 최단거리 역시 위와 같은 과정을 통해 6-2로 4가 되는 것을 알 수 있다. • B와 연결된 마지막 정점 D에 도달하기 위해서는 거리 AB와 거리 BD를 더해주어야 한다. 그럼 거리가 6+8=14가 되는데, 이 거리는 A에서 곧바로 D로 이동하는 거리보다 크다. 우리는 최단거리를 유지해야하기 때문에 D까지의 최단거리는 A에서 곧장 이동하는 7로 유지한다.

이제 정점 D에 대한 Relaxation을 진행해보자. 정점 D는 C와 E로 연결된다. • 정점 D를 거쳐서 C로 이동하게 되면 총 거리가 7 - 3 = 4가 된다. 기존에 C까지의 최단거리는 B를 통해가는 11로 설정되어있었기 때문에 더 짧은 최단거리가 나왔으므로 d[C]를 새로운 값으로 갱신해준다. • 정점 D를 거쳐서 정점 E로 이동하게 되면 총 거리가 7 + 9 + 11이 된다. 이 거리는 기존에 최단거리였던 정점 B를 거쳐서 E로 이동하는 거리보다 작기 때문에 새로 갱신하지 않고 넘어간다.

C에 대한 Relaxation을 진행해보자. 현재 정점 C까지의 최단경로를 거쳐서 B로 이동하게 되면, A에서 바로 B로 이동하는 거리보다 짧다. 따라서 B의 새로운 최단거리는 4 - 2 = 2 가 된다.

E정점에 대한 Relaxation을 진행하면 E를 거쳐 C로 가는 최단거리는 9이기 때문에 현재 C까지 가는 최단 경로보다 크다. 따라서 최단 경로를 업데이트 하지 않고 끝낸다. 이렇게 하면 한번의 relaxation 세트가 끝나게 된다. 이 작업을 시작 노드를 제외한 노드의 수 만큼 반복한다.

relaxation을 V-1 번 반복하게 되면 다른 간선들의 값은 변하지 않고 B에서 E로 가는 간선의 값이 업데이트 된다. 이 이후로 모든 rexlation 값은 변하지 않으므로 그래프 도식은 생략하기로 하겠다.

⭐️ Relaxation은 끝났지만, negative weight cycle이 있는지 확인하기 위해서 위 작업을 한번 더 거쳐야 한다. 현재 각 정점에 대한 최단거리가 기록되어 있는데 만약 이 거리가 새로운 최단거리로 갱신될 수 있다면, negative weight cycle이 존재한다는 의미일 것이다. 이때는 false 를 반환해서 지금까지 구한 최단거리가 의미가 없음을 알린다.

💻 C++ 구현

#include <iostream>
#include <vector>
#include <string>
#define MAX_SIZE 500
#define INF 9999
using namespace std;
int D[MAX_SIZE], Adj[MAX_SIZE][MAX_SIZE]; // Adj는 간선의 가중치를 저장할려고 하는 변수이기에 갱신 X, D는 최단거리를 저장해주는 변수이므로 갱신O
int V,E ;// V는 정점, E는 간선 
void Init_D(int sp);
void Init_Adj(int sp);
int main(){
    int from,to,weight; // 그래프의 간선에 값을 넣기 위한 변수.
    int S; // 어디 정점부터 시작할지 입력.
    cout << "정점의 개수, 간선의 개수, 시작할 정점 위치를 입력하세요:\n";
    cin >> V >> E >> S;
    Init_Adj(S);
    Init_D(S);
            /* 간선 정보 입력 */
    for(int i=1;i<=E;i++){
        cin >> from >> to >> weight;  // 기본적인 간선 데이터 입력. 이 입력은 수정이 불가능.
        Adj[from][to] = weight;
    }
            /* 벨만-포드 알고리즘 */
    for(int i = 1; i<V ; ++i){
        for(from=1; from<=V ; ++from){
            for(to = 1; to<=V ; ++to){
                if( D[from] == INF ) continue;
                int dist = Adj[from][to] + D[from];
                if ( D[to] > dist) D[to] = dist;
            }
        }
    }
    return 1;
void Init_D(int S){
    for(int i= 1;i<V;++i)
        D[i] = INF;
    D[S] = 0; // 초기 시작값은 0으로 초기화.
}
void Init_Adj(int S){
    for(int i=1;i<V;++i)
        for(int j=1;j<V;++j)
            Adj[i][j] = INF;
    Adj[S][S] = 0;
}

> 

##   ✏️ Leet code #743
> ### 📌 다익스트라를 이용한 풀이
  ```c
class Dijkstra {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<pair<int,int>> adj[n+1];
        for(int i=0;i<times.size();i++)
                adj[times[i][0]].push_back({times[i][1],times[i][2]});
        vector<int> dist(n+1,INT_MAX);
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        pq.push({0,k});
        dist[k]=0;
        while(!pq.empty())
        {
            pair<int,int> t=pq.top();
            pq.pop();
            for(pair<int,int> it:adj[t.second])
            {
                if(dist[it.first]>t.first+it.second)
                {
                    dist[it.first]=t.first+it.second;
                    pq.push({dist[it.first],it.first});
                }
            }
        }
        int res=0;
        for(int i=1;i<=n;i++)
        {
            if(dist[i]==INT_MAX)
                return -1;
            res=max(res,dist[i]);
        }
        return res;
    }
};

📌 벨만포드를 이용한 풀이

void Bellman_Ford()
{
    Dist[1] = 0;
    for (int i = 1; i <= N - 1; i++)
    {
        for (int j = 0; j < Edge.size(); j++)
        {
            int From = Edge[j].first.first;
            int To = Edge[j].first.second;
            int Cost = Edge[j].second;
            if (Dist[From] == INF) continue;
            if (Dist[To] > Dist[From] + Cost) Dist[To] = Dist[From] + Cost;
        }
    }
    for (int i = 0; i < Edge.size(); i++)
    {
        int From = Edge[i].first.first;
        int To = Edge[i].first.second;
        int Cost = Edge[i].second;
        if (Dist[From] == INF) continue;
        if (Dist[To] > Dist[From] + Cost)
        {
            cout << "음수 간선 순환이 존재하는 그래프입니다." << endl;
            return;
        }
    }
    cout << "음수 간선 순환이 존재하지 않는, 정상적인 그래프 입니다." << endl;
}

✏️ 백준 1916번

📌 다익스트라를 이용한 풀이

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
using pii= pair<int, int>;
vector<pii> vec[1001];
vector<int> dist(1001, INF);
void dijkstra(int dept){
    dist[dept] =0;
    priority_queue<pii> pq;
    pq.push({dist[dept], dept}); // 시작 weight, vertex
    while(!pq.empty()){
        int cur = pq.top().second;
        int distance = pq.top().first * -1; //현재까지 dept에서 cur 정점까지 가는 dist
        pq.pop();
        if(dist[cur]<distance) continue; //이미 distance가 최소로 변경됨 
        for(int i=0; i<vec[cur].size(); i++){
            int nxt=vec[cur][i].first; //cur 정점과 연결된 정점들
            int nxtdist = vec[cur][i].second + distance;
            //현재까지 dept에서 cur정점까지의 최소 거리와 
            //cur을 지나 nxt까지의 거리를 더한것 cur정점에서 nxt까지의 distance      
            // e.g) 1 -> 4(cur) -> 5(nxt)
            if(nxtdist<dist[nxt]){//만약 cur을 지나가는 것이 더 가깝다면
                dist[nxt]= nxtdist;
                pq.push({nxtdist*-1, nxt});//새롭게 갱신된 weight와 vertex
            }
        }
    }
}
int main(){
    int N, M; cin>>N>>M;//도시의 개수, 버스의 개수
    while(M--){
        int s, e, w; cin>>s>>e>>w;
        vec[s].push_back({e, w});
    }
    int dept, dest;
    cin>>dept>>dest;
    dijkstra(dept);
    cout<<dist[dest];
    return 0;
}

📌 벨만포드를 이용한 풀이

#include <iostream>
#include <vector>
#define INF 987654321
using namespace std;
/* 
    벨만포트 알고리즘 
    마지막 V번에서도 완화가 되면 음수 사이클이 존재함을 알려준다.    
*/
int V,M; 
vector<pair<int, int> > v[1001];
int upper[1001]; 
int bellmanFord(int src) { 
    //시작점 제외 모든 정점까지의 최단거리 INF로 초기화 
    fill_n(upper, 1001, INF);
    upper[src] = 0;
    bool updated;
    for(int i = 0; i < V; i++) {
        updated = false;
        for(int j = 1; j <= V; j++)
            for(int k = 0; k < v[j].size(); k++) {
                int there = v[j][k].first;
                int cost = v[j][k].second;
                if(upper[there] > upper[j] + cost) { // 완화 성공 
                    upper[there] = upper[j] + cost;
                    updated = true;
                }
            }
        if(!updated) break; //모든 간선에 대해 완화가 실패할경우 break; 
    }
    if(updated) return 1; //음수 사이클이 존재 
    return 0;
}
int main(void) {
    //ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> V >> M;
    for(int i = 0; i < M; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }
    int start, arrive; cin >> start >> arrive;
    if(!bellmanFord(start))
        cout<<upper[arrive];
    return 0;
}

다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

과정

① 출발 노드와 도착 노드를 설정한다. ② '최단 거리 테이블'을 초기화한다. ③ 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다. ④ 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트한다. ⑤ ③~④의 과정을 반복한다.

'최단 거리 테이블'은 1차원 배열로, N개 노드까지 오는 데 필요한 최단 거리를 기록한다. N개(1부터 시작하는 노드 번호와 일치시키려면 N + 1개) 크기의 배열을 선언하고 큰 값을 넣어 초기화시킨다.

'노드 방문 여부 체크 배열'은 방문한 노드인지 아닌지 기록하기 위한 배열로, 크기는 '최단 거리 테이블'과 같다. 기본적으로는 False로 초기화하여 방문하지 않았음을 명시한다.

예시

위와 같은 그래프가 있다고 하자. 시작정점은 0번 정점이라고 가정하고 나머지 정점까지의 최단거리를 계산해보자. 1차원 배열 dist[]에 각 정점까지의 최단거리를 갱신해 나갈 것이다. 초기에는 모두 INF(무한대)로 설정한다.

• 가장 먼저 시작정점을 방문한다. • 시작 정점에서 방문 할 수 있는 정점들에 대한 거리를 갱신한다.

• 방문하지 않은 정점 중 가장 가중치가 작은 2번 정점을 방문한다. • 0번 정점에서 2번 정점을 거쳐서 4번 정점을 가면 기존 거리 보다 최단 거리이므로 갱신한다. ( INF > 11) • 0번 정점에서 2번 정점을 거쳐서 3번 정점을 가면 기존 거리 보다 최단 거리이므로 갱신한다. ( 7 > 6 )

• 방문하지 않은 정점 중 가장 가중치가 작은 3번 정점을 방문한다. • 0번 정점-2번 정점-3번정점을 거쳐서 4번 정점을 가면 기존 거리보다 최단 거리이므로 갱신한다. ( 11> 10 )

• 방문하지 않은 정점 중 가장 가중치가 작은 4번 정점을 방문한다. • 갱신할 거리가 없다.

• 방문하지 않은 정점 중 가장 가중치가 작은 1번 정점을 방문한다. • 갱신할 거리가 없다. • 모든 정점을 방문했으므로 종료한다.

⭐️ 위와 같은 과정을 거치면 dist 배열에 0번정점부터 각 정점까지의 최단거리가 기록되게 된다.

💻 C++ 구현

1. 순차탐색

#include <vector>
#include <queue>
// 아직 방문하지 않은 노드 중 
// 가장 거리값이 작은 노드의 인덱스 반환
int FindSmallestNode()
{
    int min_dist = INF;
    int min_idx = -1;
    for (int i = 0; i<= N; i++)
    {
        if (visited[i] == true)
            continue;
        if (dist[i] < min_dist)
        {
            min_dist = dist[i];
            min_idx = i;
        }
    }
    return min_idx;    
}
// 다익스트라
void Dijkstra()
{
    for (int i = 1; i <= N; i++)
        dist[i] = map[start][i];  // 시작 노드와 인접한 정점에 대해 거리 계산
    dist[start] = 0;
    visited[start] = true;
    for (int i = 0; i < N - 1; i++)
    {
        int new_node = FindSmallestNode();
        visited[new_node] = true;
        for(int j = 0; j <= N; j++)
        {
            if (visited[j] == true)
                continue;
            if (dist[j] > dist[new_node] + map[new_node][j])
                dist[j] = dist[new_node] + map[new_node][j];
        }
    }
}

2. 우선순위 큐

#include <vector>
#include <queue>
#include <iostream>
using namespace std;
# define INF 99999999
// 시작 위치와 정점의 개수, 인접 행렬을 받아
// 최소 거리 행렬을 반환함
vector<int> dijkstra(int start, int N, vector<pair<int, int>> graph[])
{
    vector<int> dist(N, INF);  // 거리를 저장할 리스트 초기화
    priority_queue<pair<int, int>> pq;  // 우선순위 큐 선언
    dist[start] = 0;  // 시작 노드 거리를 0으로 함
    pq.push({ 0, start });  // 우선순위 큐에 넣기
    while (!pq.empty())
    {
        int cur_dist = -pq.top().first; // 큐에서 꺼내 방문하고 있는 정점의 거리
        int cur_node = pq.top().second;  // 정점의 인덱스(번호)
        pq.pop();
        for (int i = 0; i < graph[cur_node].size(); i++)
        {
            int nxt_node = graph[cur_node][i].first;  // 인접 정점 번호
            int nxt_dist = cur_dist + graph[cur_node][i].second;  // 인접 정점까지 거리
            if (nxt_dist < dist[nxt_node])  // 지금 계산한 것이 기존 거리값보다 작다면
            {
                dist[nxt_node] = nxt_dist;  // 거리값 업데이트
                pq.push({ -nxt_dist, nxt_node });  // 우선순위 큐에 넣기
            }
        }
    }
    return dist;  // start 노드로부터 각 노드까지 최단거리를 담은 벡터 리턴
}
int main()
{
    const int N = 10;  // 노드의 개수가 10개라 가정.
    int E = 20;  // 간선의 개수가 20개라 가정.
    vector<pair<int, int>> graph[N];  // 그래프 형태 선언
    for (int i = 0; i < E; i++)
    {
        int from, to, cost;  // 간선의 시작점, 끝점, 가중치
        cin >> from >> to >> cost;
        graph[from].push_back({ to, cost });  // 무향 그래프라 가정하므로 시작점과 끝점 둘 다 벡터에 넣어야 함
        graph[to].push_back({ from, cost });
    }
    vector<int> dist = dijkstra(0, N, graph);
    cout << "끝점까지의 최단거리" << dist[N - 1] << endl;
    return 0;
}

✏️ 백준 1238

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
int dist_x_to_n[1001];
vector<int> dist[2];
vector<pair<int, int>> graph[2][1001];
int n, m, x;
void dijkstra(int k) {
    dist[k][x] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0,x});
    while (!q.empty()) {
        int d = q.top().first;
        int now = q.top().second;
        q.pop();
        if (d > dist[k][now]) continue;
        for (int i = 0; i < graph[k][now].size(); i++) {
            int next = graph[k][now][i].second;
            int next_d = d + graph[k][now][i].first;
            if (next_d < dist[k][next]) {
                dist[k][next] = next_d;
                q.push({ next_d,next });
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    fill_n(dist_x_to_n, 1001, INF);
    cin >> n >> m >> x;
    for (int i = 0; i < m; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        graph[0][a].push_back({t,b});
        graph[1][b].push_back({ t,a });
    }
    dist[0].resize(n + 1, INF);
    dist[1].resize(n + 1, INF);
    dijkstra(0);
    dijkstra(1);
    int result = 0;
    for (int i = 1; i <= n; i++) {
        result = max(result, dist[0][i] + dist[1][i]);
    }
    cout << result << '\n';
    return 0;
}

✏️ 백준 1504

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 987654321;
int N, E, v1, v2, res = INF;
int sToV1, sToV2, V1ToV2, V1ToN, V2ToN;
vector<pair<int, int>> v[801]; // v[a] = (b,c) : a에서 b까지 c의 거리로 이동 가능
int dist[801];
void dijk(int start)
{
    for (int i = 0; i <= N; i++) dist[i] = INF;
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({ 0,start }); // 현재까지 거리, 현재 위치
    while (!q.empty()) {
        int cur = q.top().second;
        int curDist = q.top().first;
        q.pop();
        for (int i = 0; i < v[cur].size(); i++) {
            int next = v[cur][i].first;
            int nextDist = v[cur][i].second;
            if (dist[next] > curDist + nextDist) {
                dist[next] = curDist + nextDist;
                q.push({ dist[next],next });
            }
        }
    }
}
int main()
{
    cin >> N >> E;
    while (E--) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
    }
    cin >> v1 >> v2;
    dijk(1);
    sToV1 = dist[v1];
    sToV2 = dist[v2];
    dijk(v1);
    V1ToV2 = dist[v2];
    V1ToN = dist[N];
    dijk(v2);
    V2ToN = dist[N];
    res = min(res, sToV1 + V1ToV2 + V2ToN);
    res = min(res, sToV2 + V1ToV2 + V1ToN);
    if (V1ToV2 == INF || res == INF) cout << -1;
    else cout << res;
}

✏️ 백준 1753

#include <iostream>
#include <vector>
#include <queue>
#define INF 1000000 // 시작 노드에서 해당 노드까지의 경로가 없는 경우의 비용
#define MAX_VERTEX 20001 // 최대 vertex 개수
#define MAX_EDGE 300001 // 최대 edge 개수
using namespace std;
// 최소 비용 배열
int d[MAX_VERTEX];
// 간선 정보를 담은 Vector 생성
// index : 시작 노드
// value : pair<비용, 도착 노드> 목록
vector<pair<int, int> > edge[MAX_EDGE];
void dijkstra(int start_node){
    // 시작 노드에서 시작 노드로 가는 비용은 0
    d[start_node] = 0;
    // 시작 노드부터 어떤 도착 노드까지의 최소 비용을 제시하는 간선 목록이며,
    // pair<비용, 도착 노드> 형식의 우선 순위 큐이다.
    priority_queue<pair<int, int> > pq;
    // 시작 노드에서 시작 노드로 가는 경로와 비용을 pq 에 삽입
    pq.push(make_pair(0, start_node));
    // pq 의 모든 경로들을 확인할 때까지 반복
    while(!pq.empty()){
        // 기존의 우선 순위 큐는, 첫 번째 값을 기준으로 큰 값이 top 에 오도록 정렬되어있다.
        // 하지만, 해당 알고리즘에선, 비용 값을 음수화 한 뒤 첫 번째 값으로 삽입하고, 도착 노드는 두 번째 값으로 삽입한다.
        // 따라서, 비용이 가장 작은 값이 top 에 오도록 정렬되어있다.
        // 즉, 가장 최소 비용을 주장하는 경로부터 확인하게 된다.
        // 시작 노드에서 어떤 도착 노드까지의 최소 경로를 주장하는 pq 의 top 에서,
        // 도착 노드를 현재 노드로 설정한다.
        int current = pq.top().second;
        // 시작 노드에서 현재 노드까지의 비용을 설정한다.
        // 비용은 음수화되어있는 상태이므로, 양수화해서 사용한다.
        int start_to_current_distance = -pq.top().first;
        // 현재 경로는 확인 되었으므로, 우선 순위 큐에서 제거한다.
        pq.pop();
        // pq 의 top 에서 뽑은, 시작 노드부터 현재 노드까지의 비용과
        // 최소 비용 배열에 있는, 시작 노드부터 현재 노드까지의 비용을 비교함으로써,
        // pq 의 top 에서 뽑은, 시작 노드부터 현재 노드까지의 비용이 더 크면
        // 굳이 해당 경로를 통해 인접한 노드들을 확인할 필요가 없으므로, 더 이상 확인하지 않음
        if (d[current] < start_to_current_distance){
            continue;
        }
        // 상단 조건문에 걸리지 않고 통과하면,
        // 시작 노드부터 현재 노드까지는 최소 비용으로 이루어진 상태이므로, 
        // 이제 현재 노드와 연결된 노드들을 모두 검사한다.
        for (int i=0; i<edge[current].size(); ++i){
            // 다음 노드 설정
            // 즉, 현재 노드와 i 번째로 인접한 노드
            int next = edge[current][i].second;
            // 시작 노드에서 다음 노드까지의 비용 설정
            // 즉, 시작 노드에서 현재 노드까지의 비용 + 현재 노드에서 i 번째로 인접한 노드까지의 비용
            int start_to_next_distance = start_to_current_distance + edge[current][i].first;
            // 기존의, 시작 노드에서 다음 노드까지의 최소 비용보다
            // 새롭게 계산한, 시작 노드에서 다음 노드까지의 비용이 더 작다면
            // 최소 비용을 업데이트
            if (d[next] > start_to_next_distance){
                d[next] = start_to_next_distance;
                // 이제, 갱신된 경로가 최소 비용임을 주장하기 위해
                // 우선 순위 큐에 해당 경로 삽입
                pq.push(make_pair(-start_to_next_distance, next));
            }
        }
    }
}
int main(){
    // 노드의 개수와 간선의 개수 입력
    int v, e;
    cin >> v >> e;
    // 시작 노드 입력
    int start_node;
    cin >> start_node;
    // 최소 비용 배열 초기화
    for (int i=1; i<v+1; ++i){
        d[i] = INF;
    }
    // 간선 저장
    for (int i=0; i<e; ++i){
        // 시작 노드, 도착 노드, 비용 입력
        int start, end, cost;
        cin >> start >> end >> cost;
        // 시작 노드에 따른 <비용, 도착 노드> 저장
        edge[start].push_back(make_pair(cost, end));
    }
    // 다익스트라 함수 실행
    dijkstra(start_node);
    // 최소 비용 배열 출력
    for (int i=1; i<v+1; ++i){
        if (d[i] == INF){
            cout << "INF" << " ";    
        }
        else{
            cout << d[i] << " ";
        }
    }
    return 0;
}

📷 총 105장의 사진 데이터

1. 여의도 한강 공원 → 53장의 사진 데이터
2. 성북천 → 52장의 사진 데이터

데이터 분류 및 공유 방법

1. data.csv파일에 각각의 사진 데이터의 이름, 사이즈, 위도와 경도를 적고 사진 속 쓰레기를 Rubbish, Plastics, Cans, Glass, Papers로 나누어 사진 속에 각각 몇개가 있는지를 적었다. ✲ 데이터의 이름은 20211408_001 ~ 20211408_105이다.
2. data.csv파일에서 정리한 걸 바탕으로 Google Drive에 사진 데이터를 업로드 했다. ✲ 추가로 data.csv파일도 업로드

• data_전체
• data_Rubbish
• data_Plastics
• data_Cans
• data_Glass
• data_Papers ⭐️ 링크가 있는 모든 사용자가 접근할 수 있도록 설정했다. 📌 링크 주소 ( 클릭하면 이동 ) https://drive.google.com/drive/folders/1fmWB0uS3c0OmNs9lSi3x8tXFqQ56CCC6?usp=sharing

문제 소개

_"어떻게 하면 재활용되지 못하고 강이나 하천에 떠다니는 쓰레기를 줄일 수 있을까?" _

⭐️ 문제 대상 : 강이나 하천에 떠다니는 쓰레기들

강이나 하천에 무분별하게 떠다니는 쓰레기들이 많다. → 이로 인해 환경이 오염되고 지구온난화가 촉진되며 생태계 또한 파괴될 수 있다.

⭐️ 접근 방법

1. 나의 사진 데이터와 다른 학우들의 사진 데이터를 합쳐 많은 양의 사진 데이터를 포함하는 데이터 베이스를 구축한다.
2. 자료구조를 이용해 강과 하천에 떠다니는 쓰레기를 위치와 종류별로 분류하는 프로그램을 생성한다.

AVL 트리가 무엇인지 알아보기 전에 알아야 할 것이 있다. → 이진 탐색 트리의 단점 : 불균형한 트리 모형을 하고 있을 때 트리의 성능이 O(log n)에서 O(n)으로 떨어진다는 것 ⭐️ AVL 트리는 이러한 문제를 해결하기위해 만들어졌다. 이진트리이면서, 균형을 유지하기 때문에 이진 검색 시 효율성을 보장하게 된다.

✔︎ AVL 트리 특징

• AVL 트리는 이진 탐색 트리의 속성을 가진다.
• 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
• 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄인다.
• AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)이다.

균형 트리 (Balanced tree)

트리에는 3가지의 상태가 있다.

1. 완전 균형 상태 (Perfect Balance)
2. 충분한 균형 상태 (Good Enough Balance)
3. 불균형 상태 (Unbalance)

   완전 균형 상태 (Perfegt Balance) ✔︎ 모든 레벨에서 노드가 가득 차있는 상태

충분한 균형 상태 (Good Enough Balance) ✔︎ 가장 아래쪽 레벨을 제외하고 모든 노드가 채워져 있는 상태

불균형 상태 (Unbalance) ✔︎ 완전 균형 상태와 충분한 균형 상태의 트리를 제외한 나머지 트리 모양은 불균형한 상태의 트리 → 성능 저하의 원인 → 이 문제를 해결하기 위해 AVL Tree를 사용 AVL Tree는 자동으로 균형 잡힌 트리를 제공하기 때문에 탐색, 삽입, 삭제 오퍼레이션들은 O(log n)으로 진행할 수 있게 한다.

균형 인수(Balance Factor)

⭐️ 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값

• BF가 1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한단계 높다는 것을 의미한다.
• BF가 0이면 왼쪽 서브트리와 오른쪽 서브트리의 높이가 같다는 것을 의미한다.
• BF가 -1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한단계 낮다는 것을 의미한다.
• 균형 인수의 절대값이 크면 클수록 트리의 균형이 무너진 상태이다. → 균형 인수의 절대값이 2 이상인 경우에 균형을 잡기 위한 재조정을 진행한다. ✔︎ 위의 ALV 트리를 보면 BF가 -1과 +1 사이에 있음을 알 수 있다.

회전 (Rotation)

이때 우리는 rotation을 활용하여 불균형 트리들을 균형트리로 바꿔준다.

< rotation의 4가지 종류 >

1. Left Left
2. Right Right
3. Left Right
4. Right Left

   LL( Left Left) case y는 z의 왼쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우 right rotation을 수행하여 균형을 맞춘다. < ⭐️ right rotation 수행 과정 >

5. y노드의 오른쪽 자식 노드를 z노드로 변경한다.
6. z노드 왼쪽 자식 노드를 y노드 오른쪽 서브트리(T2)로 변경한다.
7. y는 새로운 루트 노드가 된다. < 💻 right rotation 구현 >

   struct node *rightRotate (struct node *z) {
   struct node *y = z->left;
   struct node *T2 = y->right;
   // right 회전 수행
   y->right = z;
   z->left = T2;
   // 노드 높이 갱신
   z->height = 1 + max(z->left->height, z->right->height);
   y->height = 1 + max(y->left->height, y->right->height);
   // 새로운 루트 노드 y를 반환  
   return y;
   }

RR (Right Right) case y는 z의 오른쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left rotation을 수행하여 균형을 맞춘다. < ⭐️ left rotation 수행 과정 >

1. y노드의 왼쪽 자식 노드를 z노드로 변경한다.
2. z노드 오른쪽 자식 노드를 y노드 왼쪽 서브트리(T2)로 변경한다.
3. y는 새로운 루트 노드가 된다. < 💻 left rotation 구현 >

   struct node *leftRotate (struct node *z) {
   struct node *y = z->right;
   struct node *T2 = y->left;
   // left 회전 수행
   y->left = z;
   z->right = T2;
   // 노드 높이 갱신
   z->height = 1 + max(z->left->height, z->right->height);
   y->height = 1 + max(y->left->height, y->right->height);
   // 새로운 루트 노드 y를 반환  
   return y;
   }

LR (Left Right) case y는 z의 왼쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left , right 순으로 총 두 번의 rotation을 수행하여 균형을 맞춘다. < 💻 구현 >

y = z->left;
y = leftRotate(y);
z = rightRotate(z);

RL (Right Left) case y는 z의 오른쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우, right, left 순으로 총 두번의 rotation을 수행하여 균형을 맞춘다. < 💻 구현 >

y = z->right;
y = rightRotate(y);
z = leftRotate(z);

삽입

AVL트리의 삽입 삭제 방식은 이진 탐색 트리와 같다. 하지만 높이 균형을 유지하기 위해 노드의 높이 정보와 case별 rotation 과정이 추가된다. < 💻 구현 >

struct node {
  int key;
  struct node *left, *right;
  int height;
};

int max(int a, int b) {
  return (a > b)? a : b;
}

struct node* newNode(int key) {
  struct node *temp = (struct *node)malloc(sizeof(struct node));

  temp->data = key;
  temp->left = NULL;
  temp->right = NULL;
  temp->height = 1;
  return temp;
}

struct node *leftRotate (struct node *z) {
  struct node *y = z->right;
  struct node *T2 = y->left;

// left 회전 수행
  y->left = z;
  z->right = T2;

// 노드 높이 갱신
  z->height = 1 + max(z->left->height, z->right->height);
  y->height = 1 + max(y->left->height, y->right->height);

// 새로운 루트 노드 y를 반환  
  return y;
}


struct node *rightRotate (struct node *z) {
  struct node *y = z->left;
  struct node *T2 = y->right;

// right 회전 수행
  y->right = z;
  z->left = T2;

// 노드 높이 갱신
  z->height = 1 + max(z->left->height, z->right->height);
  y->height = 1 + max(y->left->height, y->right->height);

// 새로운 루트 노드 y를 반환  
  return y;
}

// BF(BalanceFactor)값을 가져오는 함수.
int getBalanceFactor(struct node *n) {
  if (n == NULL)
    return 0;
  return n->left->height - n->right->height;
}

// 트리의 높이 균형을 유지하는 함수.
// 4가지 케이스를 가지고 rotate를 수행함.
struct node* rebalance(struct node* root) {

  int bFactor = getBalanceFactor(root);

  // LL Case
  if (bFactor > 1 && key < node->left->key)
    return rightRotate(root);
  // RR Case
  if (bFactor < -1 && key > node->right->key)
    return leftRotate(root);
  // LR Case
  if (bFactor > 1 && key > node->left->key){
    root->left = leftRotate(root->left);
    return rightRotate(root);
  }
  // RL Case
  if (bFactor < -1 && key < node->right->key){
    root->right = rightRotate(root->right);
    return leftRotate(root);
  }

  return root;
}

// 삽입 함수.
struct node* insert(struct node* root, int key) {

// 삽입 수행
  if (root == NULL)
    return newNode(key);
  if (key > root->data)
    root->right = insert(root->right, key);
  else if (key < root->data)
    root->left = insert(root->left, key);
  else
    return root;

// 노드 높이 갱신
  root->height = 1 + max(node->left->height, node->right->height);

// 노드 균형 유지  
  root = rebalance(root);

  return root;
}

✏️ LeetCode 110

class Solution {
private:
    pair<bool,int> isBalancedFast(TreeNode* root){
        if(root == NULL){
            pair<bool , int> p = make_pair(true , 0);
            return p;
        }

        pair<bool,int> left = isBalancedFast(root->left);
        pair<bool,int> right = isBalancedFast(root->right);

        bool leftAns = left.first;
        bool rightAns = right.first;

        bool curr = abs(left.second - right.second) <= 1;

        pair<bool,int> ans;
        ans.second = max(left.second , right.second) + 1;

        if(leftAns && rightAns && curr){
            ans.first = true;
        }
        else
            ans.first = false;

        return ans;
    }

public:
    bool isBalanced(TreeNode* root) {
        return isBalancedFast(root).first;
    }
};

• 레코드 (record)

• 필드 (field)
• 테이블 (table)
• 키 (key)
• 주요키 (primary key)

이진 탐색 트리 ?

✔︎ BST (Binary Search Tree) ✔︎ 이진트리 기반의 탐색을 위한 자료구조로 효율적인 탐색 작업을 위한 자료구조이다. ✔︎ 이진 탐색 트리를 중위 순회 방법으로 순회하면 오름차순으로 정렬된 값을 얻을 수 있다. ✔︎ 다음과 같이 순환적으로 정의된다.

• 모든 노드는 유일한 키를 갖는다.
• 왼쪽 서브트리의 키들은 루트의 키보다 작다.
• 오른쪽 서브트리의 키들은 루트의 키보다 크다.
• 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

이진 탐색 트리의 추상 자료형

데이터 : 이진 탐색 트리(BST)의 특성을 만족하는 이진트리 : 어떤 노드 x의 왼쪽 서브트리의 키들은 x의 키보다 작고, 오른쪽 서브트리의 키들은 x의 키보다 크다. 이때 왼쪽과 오른쪽 서브트리도 모두 이진 탐색 트리이다. 연산 : • insert(n) : 이진 탐색 트리의 특성을 유지하면서 새로운 노드 n을 이진 탐색 트리에 삽입한다. • remove(n) : 이진 탐색 트리의 특성을 유지하면서 노드 n을 트리에서 삭제한다. • search(key) : 키 값이 key인 노드를 찾아 반환한다.

이진 탐색 트리의 클래스 다이어그램

이진 탐색 트리의 탐색 연산

이진 탐색 트리에서 어떤 탐색키를 가진 노드를 찾기 위해서는 먼저 주어진 탐색키와 현재의 루트 노드의 키 값을 비교해야 한다.

• 비교한 결과가 같으면 탐색이 성공적으로 끝난다.
• 비교한 결과 탐색키가 루트 노드의 키 값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작한다.
• 비교한 결과 탐색키가 루트 노드의 키 값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다.

⭐️ 루트 아래의 노드에서도 같은 과정을 되풀이한다.

1. SearchRecur() : 순환으로 구현한 탐색 함수

💻 C++ 구현 ✔︎ 이 함수는 임의의 노드 n을 루트 노드로 하는 트리에서 탐색키 key를 갖는 노드를 찾아 반환한다.

// 키 값으로 노드를 탐색하는 함수 (순환적인 방법)
// 일반 함수로 구현 (BinSrchTree의 멤버 함수로 넣어도 됨)
BinaryNode* searchRecur(BinaryNode *n, int key) {
    if(n == NULL) return NULL;                // n이 NULL
    if(key == n->getData())                   // (1) key == 현재노드의 data
        return n;
    else if(key < n->getData())               // (2) key < 현재노드의 data
        return searchRecur(n->getLeft(), key);  
    else                                      // (3) key > 현재노드의 data
        return searchRecur(n->getRight(), key); 
}

2. SearchIter() : 반복으로 구현한 탐색 함수

💻 C++ 구현 ✔︎ BinSrchTree 클래스의 멤버로 구현

// 키 값으로 노드를 탐색하는 함수 (반복적인 방법)
// 일반 함수로 구현 (BinSrchTree의 멤버 함수로 넣어도 됨)
BinaryNode* searchIter(BinaryNode *n, int key) {
     while(n != NULL) {
         if(key == n->getData())        // (1) key == 현재노드의 data
             return n;
         else if(key < n->getData())    // (2) key < 현재노드의 data
             n = n->getLeft();
         else                           // (3) key > 현재노드의 data
             n = n->getRight();
     }
     return NULL;                       // 탐색에 실패한 경우 NULL 반환
 }

3. BinaryNode::search() : 노드 클래스에서 순환으로 구현

💻 C++ 구현 ✔︎ BinaryNode 클래스의 멤버로 구현 ✔︎ 트리의 각 노드들은 모두 자신을 루트로 갖는 서브트리를 대표한다고 생각할 수 있다.

// 키 값으로 노드를 탐색하는 함수 (순환적인 방법)
// 노드 클래스의 멤버로 구현 (일반 함수가 아님)
BinaryNode* BinaryNode::search(int key) {
    if(key == data)                         // (1) key == 현재노드의 data
        return this;
    else if(key < data && left != NULL)     // (2) key < 현재노드의 data
        return left->search(key);
    else if(key > data && right != NULL)    // (3) key > 현재노드의 data
        return right->search(key);
    else                                    // 찾는 노드 없음 
        return NULL;
}

이진 탐색 트리의 삽입 연산

이진 탐색 트리에 원소를 삽입하기 위해서는 먼저 탐색을 수행하는 것이 필요하다. → 이진 탐색 트리에서는 같은 키 값을 갖는 노드가 없어야 하기 때문 → 탐색에 실패한 위치가 바로 새로운 노드를 삽입하느 위치가 되기 때문

⭐️ 이진 탐색 트리에 노드9를 삽입하는 과정

루트에서부터 9를 탐색해본다.

• 만약 탐색이 성공하면 이미9가 트리 안에 존재하는 것이고, 키가 중복되므로 삽입 불가능하다.
• 만약 9가 트리 안에 없으면 어디선가 탐색이 실패로 끝날 것이다. 바로 실패로 끝난 위치가 9가 있어야 할 곳이다.

→ 따라서 탐색이 실패로 끝난 위치인 12의 왼쪽에 9를 삽입하면 된다.

💻 C++ 구현

// 이진 탐색 트리의 삽입 함수 (순환적인 방법)
// 일반 함수로 구현 (BinsrcTree의 멤버 함수로 넣어도 됨)
void insertRecur( BinaryNode* r, BinaryNode* n ) {
     if( n->getData() == r->getData() )
          return;
    else if( n->getData() < r->getData() ) {
         if( r->getLeft() == NULL ) r->setLeft(n); 
         else insertRecur( r->getLeft(), n );
    } 
    else {
         if( r->getRight() == NULL ) r->setRight(n);
         else insertRecur( r->getRight(), n );
     }
}

이진 탐색 트리의 삭제 연산

✔︎ 노드 삭제의 3가지 경우

1. 삭제하려는 노드가 단말 노드일 경우
2. 삭제하려는 노드가 왼쪽이나 오른쪽 서브트리 중 하나만 가지고 있는 경우
3. 삭제하려는 노드가 두 개의 서브트리 모두 가지고 있는 경우

   case1 : 삭제하려는 노드가 단말 노드일 경우

   단말 노드를 지운다는 것은 단말 노드의 부모 노드를 찾아서 부모 노드의 링크필드를 NULL로 만들어서 연결을 끊으면 된다. → 연결 관계가 정리되면 마지막으로 단말 노드를 동적으로 해제시키면 된다. ⭐️ 삭제를 위해 알아야 할 노드 ⭐️

-삭제할 노드 : 30 -삭제할 노드의 부모 : 26

case2 : 삭제하려는 노드가 하나의 서브트리만 가지고 있는 경우

삭제되는 노드가 왼쪽이나 오른쪽 서브트리 중 하나만 가지고 있는 경우에는 그 노드는 삭제하고 삭제된 노드의 유일한 자식을 부모 노드에 붙여주면 된다. ⭐️ 삭제를 위해 알아야 할 노드 ⭐️ -삭제할 노드 : 68 -삭제할 노드의 부모 : 35 -삭제할 노드의 유일한 자식 :99

case3 : 삭제하려는 노드가 두 개의 서브트리를 가지고 있는 경우

Q. 어떤 노드를 가져와야 다른 노드들을 변경시키지 않고 이진 탐색 트리의 조건을 계속 만족시킬 수 있을까? A. "삭제되는 노드와 가장 값이 비슷한 노드" (후계자 노드) → 왼쪽 서브트리에서 가장 큰 값 or 오른쪽 서브트리에서 가장 작은 값 → 왼쪽 서브트리의 가장 오른쪽에 있는 노드 or 오른쪽 서브트리에서 가장 왼쪽에 있는 노드 ✲ 후계자 노드 찾는법 ( 여기서는 오른쪽 서브트리에서 가장 작은 값을 후계자로 한다.) → 삭제되는 노드의 오른쪽 서브트리에서 가장 작은 값을 갖는 노드는 오른쪽 서브트리에서 왼쪽 자식 링크를 타고 NULL을 만날 때까지 계속 진행하면 된다. → 최종적으로 22가 후계자가 되고 22가 18 자리로 이동되게 된다. ⭐️ 삭제를 위해 알아야 할 노드 ⭐️ -삭제할 노드 : 18 -삭제할 노드의 부모 : 35 -후계 노드 : 22 -후계 노드의 부모 : 26 💻 C++ 구현 ✔︎ 삭제할 노드 node와 함께 node의 부모 노드의 포인터도 함께 제공해야 한다.

// 이진 탐색 트리의 삭제 함수 (순환적인 방법)
// 일반 함수로 구현 (BinSrchTree의 멤버 함수로 넣어도 됨)
void remove (BinaryNode *parent, BinaryNode *node) {
    // case 1 : 삭제하려는 노드가 단말 노드일 경우
    if( node->isLeaf() ) {
        if( parent == NULL )      // node == root인 경우 → 공백상태가 됨
            root = NULL; 
        else {                    // 아닌 경우 → parent의 해당 자식을 NULL
            if( parent->getLeft() == node )
                parent->setLeft(NULL);
            else
                parent->setRight(NULL);
        }
    }
    // case 2 : 삭제하려는 노드가 왼쪽이나 오른쪽 자식만 갖는 경우
    else if( node->getLeft()== NULL|| node->getRight()==NULL ) { 
        // 삭제할 노드의 유일한 자식 노드 → child
        BinaryNode *child = (node->getLeft() != NULL )
            ? node->getLeft() : node->getRight(); 
        // 삭제할 노드가 루트이면 → child가 새로운 root가 됨
        if( node == root ) root = child;
        // 아니면 → 부모 노드의 자식으로 자식 노드 child를 직접 연결
        else {
            if( parent->getLeft() == node )
                parent->setLeft(child);
        else
            parent->setRight(child);
        }
    }
    // case 3 : 삭제하려는 노드가 두개의 자식이 모두 있는 경우
    else {
        // 삭제하려는 노드의 오른족 서브트리에서 가장 작은 노드를 탐색
        // succ → 후계 노드 : 오른쪽 서브트리에서 가장 key가 작은 노드
        // succp → 후계 노드의 부모 노드
        BinaryNode* succp = node; 
        BinaryNode* succ = node->getRight();
        while (succ->getLeft() != NULL) {   // 후계 노드 탐색 
            succp = succ;                   // 후계 노드의 부모 노드
            succ = succ->getLeft();         // 후계 노드
        }
        // 후계 노드의 부모와 후계 노드의 오른쪽 자식을 직접 연결
        if( succp->getLeft() == succ )
            succp->setLeft(succ->getRight());
        else                        // 후계 노드가 삭제할 노드의 바로 오른쪽 자식인 경우
            succp->setRight(succ->getRight());
        // 후계 노드 정보를 삭제할 노드에 복사
        node->setData(succ->getData());
        // 삭제할 노드를 후계 노드로 변경 : 실제로는 후계 노드가 제거됨
        node = succ; 
    }
    delete node;                     // 메모리 동적 해제    
}

이 함수는 일반 함수가 아니라 BinSrchTree의 멤버 함수로 구현해야 하며, 삽입이나 탐색 연산과 같이 노드 클래스에서 구현할 수는 없다. → 삭제를 위해 여러 노드의 정보가 필요하기 때문

이진 탐색 트리의 성능 분석

이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을 때 O(h)가 된다. (높이 h에 비례)

✏️ LeetCode 98

class Solution {
public:
    bool validate(TreeNode* root, TreeNode* low, TreeNode* high) {
        // Empty trees are valid BSTs.
        if (root == nullptr) {
            return true;
        }

        // The current node's value must be between low and high.
        if ((low != nullptr and root->val <= low->val) or
            (high != nullptr and root->val >= high->val)) {
            return false;
        }

        // The left and right subtree must also be valid.
        return validate(root->right, root, high) and
               validate(root->left, low, root);
    }

    bool isValidBST(TreeNode* root) {
        return validate(root, nullptr, nullptr);
    }
};

✏️ LeetCode 99

class Solution {
    TreeNode*first;
    TreeNode*prev;
    TreeNode*mid;
    TreeNode* last;

    void inorder(TreeNode*root)
    {
        if(root==NULL)
        {
            return;
        }
        inorder(root->left);
        if(prev!=NULL && (root->val<prev->val))
        {
            if(first==NULL)
            {
                first=prev;
                mid=root;
            }
            else
            {
                last=root;
            }
        }
        prev=root;
        inorder(root->right);
    }

public:
    void recoverTree(TreeNode* root) {
        first=mid=last=NULL;
        prev=new TreeNode(INT_MIN);
        inorder(root);
        if(first&& last)
        {
            swap(first->val,last->val);
        }
        else if(first && mid)
        {
            swap(first->val,mid->val);
        }
    }
};

✏️ LeetCode 700

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
      if(root==NULL){
          return root;
      }
      if(root->val> val){
          root=searchBST(root->left,val);
      }
      else if(root->val < val){
          root=searchBST(root->right,val);
      }
      return root;
    }
};

✏️ LeetCode 701

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL) {
            TreeNode* n = new TreeNode(val);
            root = n;
            return root;
        }
        helper(root, val);
        return root;
    }

    void helper(TreeNode* root, int val) {
        if(root->left == NULL && root->val > val)  {
            TreeNode* n = new TreeNode(val);
            root->left = n;
            return;
        }

        if(root->right == NULL && root->val < val) {
            TreeNode* n = new TreeNode(val);
            root->right = n;
            return;
        } 
        if(root->val > val) {
            helper(root->left, val);
        }

        else {
            helper(root->right, val);
        }
    }
};

• 스택 : 가장 최근에 들어온 데이터가 삭제되는 자료구조 → 후입선출 (LIFO)

• 큐 : 가장 먼저 들어온 데이터가 삭제되는 자료구조 → 선입선출 (FIFO)

• 우선순위 큐 : 가장 우선순위가 높은 데이터가 삭제되는 자료구조

  우선순위 큐는 우선순위 개념을 큐에 도입한 자료구조이다. 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 출력된다. 우선순위 큐는 삭제 연산에서 어떤 요소가 먼저 삭제되는가에 따라 두 가지로 나뉜다.

  최대 우선순위 큐 : 우선순위가 가장 높은 요소 먼저 삭제 최소 우선순위 큐 : 우선순위가 가장 낮은 요소 먼저 삭제

우선순위 큐의 추상 자료형

• 데이터 : 우선순위를 가진 요소들의 모음

• 연산
• *insert(item)** : 우선순위 큐에 항목 item을 추가
• *remove()** : 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이를 반환
• *find()** : 우선순위가 가장 높은 요소를 삭제하지 않고 반환
• *isEmpty()** : 우선순위 큐가 공백 상태인지 검사
• *isFull()** : 우선순위 큐가 포화상태인지 검사
• *display()** : 우선순위 큐의 모든 요소들을 출력

우선순위 큐의 구현 방법

힙(heap) ?

• 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조

• 부모 노드의 키 값이 자식 노드의 키 값보다 큰 이진트리
• 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도의 느슨한 정렬 상태를 유지
• 힙의 목적 : 삭제 연산에서 가장 큰 값을 효율적으로 찾아내는것 → 전체를 정렬할 이유 없음

힙의 종류

최대 힙(max heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
• key(부모 노드 ) >= key(자식 노드)

**최소 힙(min heap) **

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
• key(부모 노드 ) <= key(자식 노드)

  힙의 구현 방법

  힙은 완전 이진트리이기 때문에 중간에 비어있는 요소가 없다. 이 번호를 배열의 인덱스로 생각하면 배열에 힙의 노드들을 저장할 수 있다. → 힙을 저장하는 가장 효과적인 자료구조 : 배열 ✔︎ 프로그램 구현을 쉽게 하기 위해 배열의 첫 인덱스인 0는 사용 ✘ ✔︎ 트리의 모든 위치의 노드 번호는 새로운 노드가 추가되더라도 변하지 ✘

< 힙 트리에서의 자식 노드와 부모 노드와의 관계>

• 왼쪽 자식의 인덱스 = (부모의 인덱스)*2
• 오른쪽 자식의 인덱스 = (부모의 인덱스)*2 + 1
• 부모의 인덱스 = (자식의 인덱스)/2

💻 C++를 이용한 우선순위 큐 프로그래밍

✔︎ STL의 우선순위 큐를 이용한 정렬 함수

#include <queue>
#include <functional>
using namespace std;
// STL의 우선순위 큐를 이용한 내림차순 정렬, 최대힙 사용
void heapSortDec(int a[], int n) {
    priority_queue<int> maxHeap;
    for(int i=0; i<n; i++) {
        maxHeap.push(a[i]);
    }
    // MaxHeap을 이용해 내림차순으로 정렬하기 위한 반복문
    for(int i=0; i<n; i++) {
        a[i] = maxHeap.top();
        maxHeap.pop();
    }
}
// STL의 우선순위 큐를 이용한 오름차순 정렬, 최소힙 사용
void heapSortInc(int a[], int n) {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for(int i=0; i<n; i++) {
        minHeap.push(a[i]);
    }
    // MinHeap을 이용해 오름차순으로 정렬하기 위한 반복문
    for(int i=0; i<n; i++) {
        a[i] = minHeap.top();
        minHeap.pop();
    }
}

✏️ 백준 1966번

위에서 다룬 내용과 관련된 백준 문제를 풀어보자!

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int count=0;
    int test_case;
    cin >> test_case;
    int n, m,ipt;//문서의 개수, 궁금한 문서 위치, 중요도
    for (int i = 0; i < test_case; ++i) {
        count = 0;
        cin >> n >> m;
        queue<pair<int, int>> q;
        priority_queue<int> pq; // 우선순위 큐
        for (int j = 0; j < n; ++j) {
            cin >> ipt;
            q.push({ j, ipt });
            pq.push(ipt);
        }
        while (!q.empty()) {
            int index = q.front().first;
            int value = q.front().second;
            q.pop();
            if (pq.top() == value) {
                pq.pop();
                ++count;
                if (index == m) {
                    cout << count << endl;
                    break;
                }
            }
            else q.push({ index,value });
        }
    }
}

1. 큐에 인덱스와 그 인덱스에 해당하는 중요도의 값을 넣는다.
2. C++에서 제공하는 STL에서 자동으로 크기가 큰 순으로 정렬 해준다.
3. 큐가 빌 때까지 현재 중요도와 우선순위 큐에 있는 중요도를 확인하고 현재 인덱스와 찾을 인덱스 값이 일치할때까지 갯수를 증가시키며 반복한다.

• 큐 STL 에서 pair 을 사용하면 2개의 데이터를 저장하기 위한 2개의 큐를 동시에 만들 수 있다.

코로나 19로 인해 전 세계의 많은 아이들은 학습과 복지 부분에서 큰 피해를 입었다. 하지만 코로나 19 이전에도 'Quality Education(양질의 교육)'이라는 목표에 달성하기에는 교육의 진전은 너무나도 느렸다. 코로나 사태가 터진지 1년이 지났음에도 3명 중 2명의 학생은 여전히 학교를 가지 못하고있다. (아마 이 글이 작성된 시기는 코로나 사태가 터진지 1년이 지난 시기였다보다.. 그리고 실제로 나도 1년 반동안 비대면으로 수업을 들었고 대학교에 입학한지 1년 반이 지난 지금에서야 학교에 가서 수업을 들을 수 있게 되었다.😂) 또한 사회적으로 가난한 아이들이 위기를 직격탄으로 맞으며 오랫동안 이어져온 불평등이 더욱 더 악화되고 있다. (이 부분에 나도 전적으로 동의하고 이 부분이 가장 큰 문제점이라고 생각한다. 가난하고 취약한 아이들일수록 교육을 받고 스스로를 지키고 일어날 수 있는 힘을 길러야 하는데 오히려 이러한 아이들이 가장 먼저 교육에서 멀어진다는 현실이 애석하기만 하다ㅜㅜ)

Exceptional meaures are needed to get students back on track after a catastrophic year for education

위에서 말했지만 코로나 19 이전에도 교육의 진전은 느렸고 세계는 목표하고 있는 교육 수준에 도달하지 못했다. 2019년, 3학년 아이들의 59퍼센트만이 글을 읽는데 능숙했다. 코로나 사태는 이러한 교육 수준을 더욱 떨어뜨릴 것으로 예상된다. 이는 지난 20년 동안 교육에서 성취한 진보를 무용지물로 만든다. (코로나.. 너 때문에 나도 학교 못갔다고..🥹) 뒤쳐지는 아이들의 거의 3분의 2가 중앙아시아와 남아시아, 그리고 동아시아와 동남아시아에 살고 있다. 코로나 이전 사하라 이남 아프리카에서는 이미 읽기 숙련도가 매우 낮았기 때문에 이 지역의 학습 손실은 최소 숙련도 이하의 어린이들 사이에서 발생할 가능성이 높다. (이 말은 즉슨 이미 못 배우고 있는 아이들이 더 못 배우게 된다는 뜻..😭) 세계적인 학습 부족의 회복은 2024년까지 일어날 수 있지만 특별한 노력이 있어야지만 가능하다. (여기에서 말하는 특별한 노력, 제목에서의 exceptional measures(예외적인 조치)는 이러한 지역들을 더욱 특별하고 예외적으로 신경쓰자는 의미인 것 같다.)

Large disparties in school completion are likely to get worse, especially among poor or vulerable children

위의 그래프를 보면 2010년과 2019년 사이에 전 세계 중등학교 이수율은 46%에서 53%로 증가했다. 사하라 이남 아프리카에서는 26%에서 29%로 증가하여 그 지역에서 가장 뒤쳐졌다. (여기에서도 사라하 이남 아프리카가 뒤쳐진다..) 연구 집단 간의 격차는 여전히 크게 벌어져있다. 위치와 부에 따른 격차는 굉장히 극명하다. 빈곤의 증가와 원격 학습으로의 전환은 가난한 가정과 다른 취약 계층의 아이들이 영구적으로 또는 장기적으로 교육받지 못하게 할 가능성을 증가시킨다. (당연히 취약 계층 아이들은 원격 수업을 받을 전자기기조차 제대로 갖춰져있지 않을텐데 어떻게 원격수업을 받을 수 있단 말인가..🤦🏻‍♀️)

Good progress in early chilhood education has been brougt to a halt by the pandemic

위의 그래프를 보면 초등 전 학습에 대한 참여는 코로나 이전인 2010년 65%에서 2019년 73%로 꾸준히 증가했다. 그러나 지역마다 상당한 차이가 있다. 2019년 조기 학습 참여율은 라틴 아메리카와 카리브해의 96%에 비해 사하라 이남 아프리카에서 43%였다. (여기에서도 위치와 부에 따른 격차가 나타난다.) 코로나로 인해 대부분의 국가에서 보육 및 조기 교육 시설이 문을 닫았기 때문에 2020년 이후 이러한 진전은 위협받고 있다. 이는 아이들의 일생 동안 성공의 기회를 감소시킬 수 있다. (조기 교육이 성공으로 가는 필수요건이라고 할 수는 없지만 어린 나이에 다양한 경험을 해 보는 것도 중요한데 아이들에게서 이러한 기회를 뺏어가는 것이 안타깝게 느껴지긴한다. 아이들이 무슨 죄가 있겠습니까,,, 👧🏻🧒🏼👦🏾)

Broader participation in continuing education and training is needed to create resilient and adaptable workers

지속적인 교육과 훈련은 생계 개선과 경제적 충격을 극복하고 기술 변화에 적응할 수 있는 노동력을 개발하는 데 핵심적이다. 펜데믹 이전에는 공식 및 비공식 교육에 대한 청소년과 성인의 평균 참여율은 25%에 불과했으며 데이터가 있는 73개 국가에 걸쳐 상당한 차이가 있었다. 그들 중 거의 절반의 참여율은 10% 미만이었지만 유럽과 북미 국가에서는 40% 이상이었다. (국가마다 참여율 차이는 있지만 평균적으로 봤을때 참여율 25%는 너무 낮다고 생각한다.🥴) 코로나 19로 인해 학교와 업무 공간이 온라인으로 전화됨에 따라 정보통신 기술(ICT)기술이 매우 중요해졌다. 그러나 2017-2019년의 가용 데이터에 따르면 청소년 및 성인의 40% 미만이 첨부 메일을 보내는 등 지난 3개월 동안 기본적인 ICT 기술 중 하나를 수행했다. (다들 열심히들 합시다 ㅎ.ㅎ)

Building back better from the crisis can start with basic school infrastructure, which is sorely lacking in many countries

코로나 19 회복의 첫걸음인 개학을 위해서는 기본적인 학교 인프라가 개선이 필수적이다. 위 그래프에 따르면 2016년부터 2019년까지 전 세계적으로 초등학교의 5분의 1 이상이 기본적인 식수나 단일 성별 화장실에 대한 접근성이 부족했고, 3분의 1 이상이 기본적인 손 씻기 시설이 부족했으며, 4분의 1은 전기가 공급되지 않았다. 학교의 인터넷 서비스와 컴퓨터는 훨씬 더 부족하다. 코로나 19는 아이들이 학교에서 안전하게 유지하는 데 있어 적절한 위생 시설의 중요성과 원격 학습을 지원하기 위한 ICT 인프라의 필요성을 강조하고 있다. (제발 아이들 교육 환경 개선에 신경 좀 써주세요ㅜ.ㅜ)

이 자료를 읽고 좋은 환경에서 교육 받을 수 있음에 감사했다.🙏🏻🙇🏻‍♀️ 항상 불평, 불만을 가지고 있었는데 세계 각 지역에는 공부하고 싶어도, 학교에 가고 싶어도 그러지 못하는 아이들도 많다는 생각에 지금 나의 상황에 감사하며 내가 할 수 있는 최선을 다해야겠다는 생각이 들었다. 양질의 교육을 받지 못하는 아이들도 하루빨리 불평등이 사라져서 다양한 경험을 하고 원하는 공부를 할 수 있게 되었으면 좋겠다. 아 그리고 자료가 영어여서 쬐끔 힘들었다ㅎ~~