2주차(개념)

∙ 그래프 이론 기초

- 정점(verteix) : 노드라고 불리며 그래프를 형성하는 기본 단위이고, 분할할 수 없는 객체이자 "점"으로 표현한다.

- 간선(Edge) : 정점을 잇는 선을 의미한다.

ex) "어떠한 위치나 어떠한 사람" 으로부터 "무엇인가를 통해 간다" => 정점 : 어떠한 사람, 간선 : 무엇가를 통해 간다

- 가중치 : 정점과 정점사이에 드는 비용을 뜻한다.

ex) 1번노드와 2번노드까지 가는 비용이 한칸이라면 1번노드에서 2번까지의 가중치는 한칸이다.

 

∙ 트리(Tree Data Structure)

자식노드와 부모노드로 이루어진 계층적인 구조를 가지며 무방향 그래프의 일종이자 사이클이 없는 자료구조를 의미한다.

 

∙ 이진트리(BT, Binary Tree)와 이진탐색트리(BST, Binary Search Tree)

이진트리는 각각의 노드의 자식노드 수가 2개 이하로 구성되어있는 트리를 의미한다.

- 정이진 트리 : 자식 노드가 0 또는 2개인 이진 트리를 의미

- 완전 이진 트리 : 왼쪽에서부터 채워져 있는 이진트리를 의미(마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우는 왼쪽부터 채워져 있음)

- 변질 이진 트리 : 자식 노드가 하나밖에 없는 이진 트리를 의미

- 포화 이진 트리 : 모드 노드가 꽉 차 있는 이진 트리를 의미

- 균형 이진 트리 : 모든 노드의 왼쪽 하위트리와 오른쪽 하위 트리의 차이가 1이하인 트리를 의미 (map, set)

 

이진탐색트리는 이진트리의 일종으로 노드의 오르쪽 하위 틔에는 "노드의 값보다 큰 값"이 있는 노드만 포함되고 왼쪽 하위트리에는 "노드의 값보다 작은값"이 들어있는 트리를 의미한다.

 

∙ 인접행렬(adjacency matrix)

그래프에서  bool타입의 정사각형 행렬을 의미한다.

ex) 정사각형 행렬의 각 요소가 0 또는 1 이라는 값으로 가짐을 의미하며, 0은 두 정점 사이의 경로가 없음을 의미하고 1은 두 정점 사이의 경로가 있음을 의미한다.

bool a[v][v];

for (int i = 0; i < v; i++){
	for (int j = 0; j < v; j++){
    	if(a[i][j]){
        	cout << i < "부터" << j << "까지 경로가 있다."\n;
            
            // 해당 정점으로부터 탐색하는 로직
            bfs(i);
            dfs(i);
        }
    }
}

Q. 3번노드에서 5번노드로 가는 단방향 경로가 있고 이를 인접행렬로 표현한다면 어떻게 될까?     a[3][5] = 1; Q. 3번노드에서 5번노드로 가는 양방향 경로가 있고 이를 인접행렬로 표현한다면 어떻게 될까?     a[3][5] = 1;     a[5][3] = 1; Q. 정점의 갯수가 20개인 그래프가 있다. 이를 인접행렬로 표현한다고 했을 때 메모리를 최소로 쓴다로 했을 때 배열을 어떻게 만들어야 할까?     bool a[20][20]; Q. 인접행렬을 기반으로 탐색하기 1. 정점은 0번부터 9번까지 10개의 노드가 있다. 1-2 / 1-3 / 3-4 라는 경로가 있다. 이를 인접행렬로 표현한다면? 2. 0번부터 방문안한 노드를 찾고 해당 노드부터 방문, 연결된 노드를 이어서 방문해서 출력하는 재귀함수를 만들고 싶다면 어떻게 해야할까? 또한, 정점을 방문하고 다시 방문하지 않게 만드려면 어떻게 해야할까? #include <iostream> using namespace std; const int v = 10; bool a[v][v], visited[v]; void go(int from){     visited[from] = 1;     cout << from << '\n';     for (int i = 0; i < v; i++){         if (visited[i]) continue;         if (a[from][i]){             go(i);         }     } } int main() {     a[1][2] = 1; a[1][3] = 1; a[3][4] = 1;     a[2][1] = 1; a[3][1] = 1; a[4][3] = 1;          for (int i = 0; i < v; i++){         for (int j = 0; j < v; j++){             if (a[i][j] && visited[i] == 0){                 go(i);             }         }     } }

 

∙ 인접리스트 기반으로 탐색

Q  1. 정점은 0번 부터 9번까지 10개의 노드가 있다. 1-2 / 1-3 / 3-4라는 경로가 있다. 이를 인접리스트로 표현한다면? 2. 0번부터 방문안한 노드를 찾고 해당 노드부터 방문, 연결된 노드를 이어서 방문해서 출력하는 재귀함수를 만들고 싶다면 어떻게 해야할까? 또한, 정점을 방문하고 다시 방문하지 않게 만드려면 어떻게 해야할까? #include <iostream> using namespace std; const int v = 10; vector<int> adj[v]; int visited[v]; void go(int idx){     cout << idx << '\n';     visited[idx] = 1;     for (int there : adj[idx]){         if (visited[there])             continue;         go(there);     }     return; } int main() {     adj[1].push_back(2);     adj[2].push_back(1);          adj[1].push_back(3);     adj[3].push_back(1);          adj[3].push_back(4);     adj[4].push_back(3);          for (int i = 0; i < v; i++){         if(adj[i].size() && visited[i] == 0){             go(i);         }     } }