자료구조/알고리즘 - 자료구조 기초 2(Graph, Tree Search Algorithm)

Graph, Tree Search Algorithm

Tree traversal(트리 순회)

특정 목적을 위해 트리의 모든 노드를 “한번씩” 방문하는 것

ex) 1부터 10까지의 정수로 이루어진 트리에서 5라는 숫자를 찾기 위해 모든 노드를 방문 → 트리 순회

 

트리 구조는 계층적 구조를 가지므로 모든 노드를 순회하는 방법도 3가지가 존재
(단, 노드 조회하는 순서는 항상 왼쪽→ 오른쪽 방향)

 

전위 순회(Preorder)

루트에서 시작해서 왼쪽의 노드들을 순차적으로 둘러본 후, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색
→ 왼쪽으로 가면서 위에서부터 순차적으로 왼쪽의 노드를 탐색함

 

중위 순회(Inorder)

루트를 가운데에 두고 순회함. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다

 

→ 왼쪽 끝에 있는 노드부터 순회하면서, 그 순회가 끝나면 그 부모 노드를 거쳐서 오른쪽에 있는 같은 레벨의 노드로 가는 구조라고 보면 된다

 

후위 순회(Postorder)

루트를 가장 마지막에 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 후, 제일 마지막에 루트를 방문한다

 

→ 왼쪽 끝에 있는 노드부터 순회하면서, 그 순회가 끝나면 그 부모 노드를 거치지 않고 오른쪽에 있는 같은 레벨 레벨의 노드로 이동해 순회 한 후에, 제일 마지막에 그 부모 노드를 방문하는 구조라고 보면 된다

 

Question

이진트리와 BST 이외에도 어떤 트리가 존재?

밸런스와 관련하여

* Balanced: 왼쪽, 오른쪽의 노드의 개수가 정확하게 일치할 필요는 없지만, 
지나치게 한쪽으로 치우치지 않은 트리 (예: red-black tree, AVL tree; 균형 이진 탐색 트리 등)

* Unbalanced: 한쪽으로 지나치게 치우친 tree

 

균형 이진 탐색 트리 란?

오른쪽 서브 트리의 높이와 왼쪽 서브 트리의 높이차가 1이하인 이진 탐색 트리

일반적인 이진 검색 트리에서 트리 구조가 한쪽으로 치우치는 경우가 발생할 수 있음
→ 성능 면에서 아주 비효율적

 

이를 피하기 위해 노드의 삽입과 삭제가 일어나는 경우에 자동으로 그 높이를 작게 유지하도록 리밸런싱 작업이 이루어짐
→ 트리의 균형을 잡기 위한 알고리즘(리밸런싱 작업)에 따라 여러 종류의 트리가 존재

 

대표적인 예: AVL tree, 레드-블랙트리(red-black tree), B트리 등

 

heap이란?

우선순위 큐를 위하여 만들어진 자료 구조

 

우선순위 큐: 우선 순위의 개념을 큐에 도입한 자료 구조
→ 데이터들이 우선 순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나간다

 

heap: 완전 이진 트리의 일종

heap의 특징

* 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료 구조

* 일종의 반정렬 상태(느슨한 정렬 상태)를 유지함
- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리

* 힙 트리에서는 중복된 값을 허용(이진 탐색 트리에서는 중복을 허용x)

힙의 종류에는 최대 힙, 최소 힙이 있다

 

[최대 힙]

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

이러한 대소 관계는 부모 자식 간에만 존재하고 형제 노드 간에는 존재하지 않는다

[최소 힙]

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

이러한 대소 관계는 부모 자식 간에만 존재하고 형제 노드 간에는 존재하지 않는다

[힙의 구현]

보통 “배열”을 이용해서 구현
구현을 쉽게 하기 위해 배열의 첫번째 인덱스인 0은 사용되지 않는다

 

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변화지 않는다
→ 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다

 

힙에서의 부모 노드와 자식 노드의 관계

왼쪽 자식의 인덱스 = (부모의 인덱스 *2)

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

부모의 인덱스 = 자식의 인덱스/2

 

[힙의 삽입]

1.새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드(가장 마지막 위치)에 이어서 삽입
2.새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

 

[힙의 삭제]

1.최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다

- 최대 힙에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것

 

2.삭제된 루트 노드에는 힙의 마지막 노드를 가져온다

3.힙을 재구성한다

 

BFS & DFS

일반적인 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한번씩 방문(탐색)하는 것이 목적
→ 정렬이 되어 있지 않으므로, 원하는 자료를 찾으려면 하나씩 “모두 방문”하여 찾아야 한다

 

그래프에서 모든 정점 탐색 방법에도 여러가지가 존재한다
→ 대표적으로 BFS, DFS가 존재
→ 탐색 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 동일

 

BFS(Breathed First Search; 너비 우선 탐색)

최대한 넓게 이동한 다음, 더이상 갈 수 없을 때 아래로 이동

한국에서 미국으로 가는 비행기를 예약하려고 합니다. 비행편에 따라 직항과 경유가 있습니다. 만약 경유를 하게 된다면, 해당 항공사가 필요로 하는 공항에 잠시 머물렀다가 가기도 합니다. 경유를 하는 시간은 비행편마다 다르고, 경유지도 다릅니다. 이렇게 다양한 여정 중에서, 최단 경로를 알아내려면 어떻게 해야 할까요?

 

한국을 기준으로 미국까지 가는 방법을 가까운 정점부터 탐색함
더는 탐색할 정점이 없으면, 그 다음 떨어져 있는 정점을 순서대로 방문함
→ 이렇게 너비를 우선적으로 탐색하는 방법(너비 우선 탐색)

 

일반화해서 생각하면, 루트부터 시작해 다음 레벨 대의 노드들을 탐색하면서 원하는 자료(정점)을 못 찾으면 그 다음 레벨 대의 노드를 탐색하면서 찾은 경우 빠져나오는 구조
→ 주로 두 정점 사이의 최단 경로를 찾을 때 사용

 

DFS(Depth-First Search)

최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

그렇다면, 한국에서 출발하는 항공기의 모든 경로 중에 미국에 도착하는 여정을 알아내고 싶을 때에는 어떻게 해야 할까요?

 

하나의 경로를 끝까지 탐색한 후, 미국 도착이 아니라면 다음 경로로 넘어가 탐색한다
→ 하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어감
→ 이렇게 깊이를 우선적으로 탐색하는 방법(깊이 우선 탐색)

 

한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다.
BFS보다 탐색 시간은 조금 오래 걸리는 편

 

일반화해서 생각하면, 루트에서 시작해 가장 왼쪽의 노드의 최하층 깊이(leaf) 만큼 파고 들어가서 탐색한 후 없으면 다시 그 다음 왼쪽의 최하층 깊이까지 파고 들어가서 탐색하면서 찾으면 빠져나오는 구조

BFS & DFS의 장단점

BFS의 장단점

* 장점
- 최적해를 찾는 것을 보장한다
- 검색 속도가 DFS에 비해 빠르다

* 단점
- 최소 실행시간보다는 오래 걸린다
- DFS보다는 복잡한 로직

DFS의 장단점

* 장점
- 모든 노드를 방문하고자 하는 경우에 적
- BFS보다 조금 더 간단한 로직

* 단점
- 찾은 해(답)가 최적이 아닐 경우가 있다
- 검색 속도가 BFS에 비해서 느림

 

Question?

Q1) 그래프가 굉장히 크다면(대용량 그래프) 어떤 탐색 기법을 고려해야 하는가?
→ DFS를 고려

Q2) 반대로, 그래프의 규모가 작고, depth가 얕다면 어떤 탐색 기법을 고려?
→ BFS를 고려

 

 

---

보충 학습 내용

자료구조 Queue 와 관련된 문제
Queue의 절친은 while문 이다!
→ Queue로 접근해야 하는 상황에서는 while 문을 생각하자!

Tree

트리의 노드 안에는 과연 데이터만 있을까?
→ 결론적으로는 아니다
(구현에 따라서 다르겠지만) 객체로 되어 있다.

let rootNode = new Tree(9);
rootNode;    //    {value: 9, children: []}

 

즉 새로운 데이터를 넣는다고 치면(insertMethod)

let childeNode = new Tree(7); // 이런식으로 해야 할 것
childeNode; //    {value: 7 , children: []}

Binary Search Tree

업다운 게임을 생각!

예: 9 찾기: 절반씩 쪼개어 목표와 먼쪽은 없애기

 

→ 이를 노드에 적용시켜 보면 된다
→ 루트(부모) 노드 기준 작은거는 왼쪽 큰거는 오른쪽에 놓는다

 

Q. root node에 child node를 넣고 싶다면 어떻게 해야?
child node가 null일때까지 파고들어가서
→ 해당 노드 기준 작거나 큰지 비교

Graph

그래프의 표현방식: 매트릭스(인접행렬), 리스트(인접리스트)

→ 보통은 “매트릭스”를 많이 이용함!

 

다만, 매트릭스(행렬)의 경우 데이터(정점)의 값을 추가, 삭제하기가 힘든 구조
→ 데이터의 추가, 삭제 시에는 리스트가 유용함

 

매트릭스는 2차원 배열로 많이 쓴다

matrix[row][column]

[
    [0,0,0,0],    ← 0번째 인덱스; 버텍스
    [0,0,0,0],    ← 1번째 인덱스
    [0,0,0,0],    ← 2번째 인덱스
    [0,0,0,0]    ← 3번째 인덱스
]

matrix[0][1] 이면?
0번째 정점(vertex)가 1번째 정점과 이어져 있는가?
→ 0(false) 또는 1(true)의 값을 가짐

 

반면, list의 경우 각 정점이 자기와 연결된 정점들만 요소로 가진다