[자료구조] 그래프이론

이번 포스팅에서는 자료구조, 알고리즘에 대해 알아보고 둘의 관계를 살펴보겠습니다.

1. 자료구조란?
데이터에 효율적으로 접근, 변경하기 위해 설계해놓은 데이터 저장 방법입니다.

 

 

2. 알고리즘이란?

알고리즘이란 문제 해결을 위한 명령어들의 집합입니다. 간단히 말하면 문제의 풀이과정들입니다. 알고리즘은 자료구조와 매우 밀접한 관계가있습니다. 문제 해결을 위해서는 데이터들을 원하는 형태로 저장해야 하기 때문에 이 과정에서 어떤 자료구조를 사용하는냐에 따라 속도가 천차만별이다. 잘선택

일반적으로 데이터는 그래프로 나타낼 수 있습니다. 이 그래프는 노드와 간선들로 연결되어 있는데요, 노드와 간선들의 종류에 따라 

 

[가중치를 연결한 그래프]

#include<iostream>
#include<vector>
#define F first
#define S second
using namespace std;
typedef pair<int, int> PII;

int V, E;
vector<PII> G[20001];

int main(void){
    cin >> V >> E;
    while(E--) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
    }

    for(int i=1; i<=V; i++){
        cout << i << "의 노드와 가중치: ";
        for(auto e: G[i]) cout << "{" << e.F << " " << e.S << "}, ";
        cout << "\n";
    }
}

입력
5 6
2 1 3
2 2 6
1 3 5
3 2 5
2 5 9
3 6 9
결과
1의 노드와 가중치: {3 5},
2의 노드와 가중치: {1 3}, {2 6}, {5 9},
3의 노드와 가중치: {2 5}, {6 9},
4의 노드와 가중치:
5의 노드와 가중치:

이후에 따로 다시 정리하겠지만, 문제에서 어떠한 상황들(정점)이 어떻게 서로 연결되어지고 관계를 맺는지(간선)를 파악하는 것이 매우 중요하다. 어찌 보면 가장 중요하다고도 볼 수 있을 것 같다.

 

• 하나의 정점(상황)에서 일정한 규칙에 의해서 다음 정점 또는 정점들로 이동한다면 DP(Dynamic Programming, 동적 계획법)을 사용할 수 있고, 
• 하나의 정점에서 연결된 이웃 정점들로만 갈 수 있다면 트리, 그래프 등의 비선형 구조 문제인 것으로 생각해 볼 수 있으며,
• 하나의 정점에서 일정한 처리를 한 후, 원복하여 다시 돌아간다면 백트래킹,
• 확인할 정점들을 범위로 나누어 확인하거나 합칠 경우, 이분 탐색 또는 분할 정복,
• 그리고 이번 문제처럼, 단지 매 정점에서 항상 최선의 선택만 한다면, 그리디 알고리즘 문제라고 볼 수 있다.

위와 같이, (내가 이해하기엔) 한 정점에서 어떤 판단을 하느냐가 문제를 풀어내는 방법을 결정하는 중요한 요소이며, 그에 따라 어떤 자료구조, 알고리즘을 적용할 수 있는지가 결정된다.