이진 탐색 트리 (Binary Search Tree) && 그래프*Graph

이진트리의 일종으로 노드의 오른쪽 하위 트리에는 노드보다 큰값, 외쪽에는 작은 값이 위치

                                16
                        /               \
                    8                      24
                 /    \                /       \
               4       12            20         28
             /  \     /  \         /   \       /   \
            2    6   10   14     18    22    26    30
           / \   / \  / \  / \   / \    / \   / \   / \
          1   3 5   7 9 11 13 15 17 19 21 23 25 27 29

 

• 이진 탐색 트리 조건:
  • 왼쪽 자식 < 부모 노드 < 오른쪽 자식
  • 예: 16의 왼쪽 서브트리는 8, 오른쪽 서브트리는 24.
• 탐색 효율:
  • 특정 값을 탐색할 때, 왼쪽 또는 오른쪽 서브트리만 탐색하면 되므로 시간 복잡도는 **O(log N)**
  • 이진탐색트리는 삽입 순서에 따라 영향을 받음
  • 삽입순서가 어떻게 되든 트리의 노드들을 회전시키는 등의 방법을 통해 균형을 잡을 수 있도록 만든 이진탐색트리가 있는데 AVL트리, Red Black Tree가 있음 (map은 삽입, 삭제, 수정 시간복잡도가 모드 O(log N) cause 레드블랙트리를 기반으로 구현되었기 때문)

---

 그래프

 

1. 인접 행렬 (Adjacency Matrix)

정의

• 인접 행렬은 2차원 배열을 사용해 그래프의 노드 간의 연결 관계를 나타내는 방법
• 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬
• 노드 i와 노드 j가 연결되어 있다면 행렬의 해당 위치를 1 또는 가중치 값으로 표시
• 연결되지 않은 경우에는 0으로 표시, 1은 두 정접 사이 경로가 있음을 의미

---

그래프 예시

노드 1, 2, 3, 4가 있는 무방향 그래프에서 간선이 다음과 같다고 가정

• 1 - 2, 1 - 3, 2 - 4

인접 행렬 표현:

    1  2  3  4
1   0  1  1  0
2   1  0  0  1
3   1  0  0  0
4   0  1  0  0

• 행과 열은 노드
• 0: 노드 간에 연결이 없음.
• 1: 노드 간에 연결이 있음.

이걸 코드로 표현하면

 bool a[4][4] = {
 {0, 1, 1, 0},
 {1, 0, 0, 1},
 {1, 0, 0, 0},
 {0, 1, 0, 0},
 };

 

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);
        }
     }  
 }

 

---

특징

1. 메모리: O(V²) (V는 노드의 수)
   • 노드의 개수에 비례하여 V×V 크기의 행렬이 필요
2. 연결 여부 확인: O(1)
   • 두 노드 간의 연결 여부는 행렬의 값을 통해 즉시 확인할 수 있음
3. 간선 추가/삭제: O(1)
   • 행렬의 값을 변경하면 간선을 추가하거나 삭제 가능
4. 메모리 낭비: 간선이 적은 **희소 그래프(Sparse Graph)**에서는 메모리 사용이 비효율적

---

장점

• 두 노드 간의 연결 여부를 빠르게 확인 가능
• 구현이 간단하고 직관적

단점

• 메모리 사용량이 크다 (간선이 적은 경우 비효율적).
• 인접한 노드를 탐색할 때 O(V)O(V) 시간이 소요

 

코드 예시

#include<bits/stdc++.h>
using namespace std;

const int V = 10; // 그래프에서 최대 정점 수 (10개의 정점)
bool a[V][V], visited[V]; // a: 간선 정보를 저장하는 인접 행렬, visited: 방문 여부 저장 배열

// 깊이 우선 탐색(DFS) 함수
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);               // 연결된 노드로 이동하여 재귀적으로 탐색
        }
    }
    return;
}

int main() {
    // 인접 행렬에 간선 정보 입력 (무방향 그래프)
    a[1][2] = 1; a[1][3] = 1; a[3][4] = 1; // 간선 추가: 1-2, 1-3, 3-4
    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); // DFS 탐색 시작
            }
        }
    }

    return 0;
}

결과

1번노드->2번노드->(다시 1번 노드 돌아와서) ->3번노드-> 4번노드

 

---

2. 인접 리스트 (Adjacency List)

정의

• 인접 리스트는 각 노드에 연결된 노드들의 리스트를 저장하는 방식
• 노드마다 인접한 노드들을 연결 리스트나 벡터로 저장

---

그래프 예시

인접 리스트 표현:

#include<iostream>
#include<vector>
using namespace std;

const int V = 10; // 그래프에서 최대 정점 수 (10개의 정점)
vector<int> adj[V]; // 인접 리스트로 간선 정보를 저장
bool visited[V];    // 방문 여부 저장 배열

// 깊이 우선 탐색(DFS) 함수
void go(int from) {
    visited[from] = 1; // 현재 노드를 방문 처리
    cout << from << '\n'; // 방문한 노드 출력

    // 현재 노드와 연결된 다른 노드 탐색
    for (int to : adj[from]) {
        if (!visited[to]) { // 아직 방문하지 않은 노드라면
            go(to);         // 연결된 노드로 이동하여 재귀적으로 탐색
        }
    }
    return;
}

int main() {
    // 인접 리스트에 간선 정보 입력 (무방향 그래프)
    adj[1].push_back(2); adj[2].push_back(1); // 간선 1-2
    adj[1].push_back(3); adj[3].push_back(1); // 간선 1-3
    adj[3].push_back(4); adj[4].push_back(3); // 간선 3-4

    // 그래프 탐색 시작
    for (int i = 0; i < V; i++) {
        if (!visited[i] && !adj[i].empty()) { // 방문하지 않았고 연결된 간선이 있는 정점이라면
            go(i); // DFS 탐색 시작
        }
    }

    return 0;
}

---

특징

1. 메모리: O(V + E) (V는 노드의 수, E는 간선의 수)
   • 간선이 적은 희소 그래프에서 매우 효율적
2. 연결 여부 확인: O(노드의 인접 리스트 길이)
   • 특정 두 노드가 연결되어 있는지 확인하려면 해당 노드의 리스트를 탐색
3. 간선 추가/삭제: O(1) (리스트에 노드 추가 또는 삭제).
4. 인접 노드 탐색: O(인접한 노드 수)
   • 특정 노드와 연결된 노드를 탐색하는 데 빠릅니다.

---

장점

• 메모리 사용이 효율적 (간선이 적은 경우).
• 인접한 노드를 탐색할 때 빠르게 접근 가능

단점

• 두 노드 간의 연결 여부를 확인하는 데 시간이 걸립니다.
• 구현이 인접 행렬에 비해 상대적으로 복잡

---

인접 행렬과 인접 리스트 비교

비교 항목 인접 행렬 (Adjacency Matrix) 인접 리스트 (Adjacency List)

메모리 사용	O(V²)	O(V + E)
연결 여부 확인	O(1)	O(인접 리스트 길이)
인접 노드 탐색	O(V)	O(인접한 노드 수)
간선 추가/삭제	O(1)	O(1)
희소 그래프	비효율적	효율적
밀집 그래프	효율적	비효율적

---

결론

• 인접 행렬: 간선이 많고 밀집된 그래프에 적합합니다. 연결 여부를 빠르게 확인해야 할 때 유리
• 인접 리스트: 간선이 적은 희소 그래프에 적합합니다. 메모리 사용량이 효율적이고 인접 노드 탐색이 빠름