2023.05.16 코드스테이츠 25일차. ( Tree , Graph ) Search Algorithm { Deque, LinkedList, Hash Table, Heap Tree }

Tree tracersal

- 특정 목정을 위해 트리의 모든 노드를 한번씩 방문하는 것을 트리 순회라고 한다

- 트리 구조는 계층적 구조라는 특별한 특징을 가지기 떄문에, 모든 노드를 순회하는 방법으로는 3가지가 있다.

 

1. 전위 순회 ( preorder traverse )

- 가장먼저 루트를 방문하고 루트에서 시작해 왼쪽의 노드들을 차례대로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다

- 주로 복사할 때 사용 한다

 

2. 중위순회 ( inorder traverse )

- 제일 왼쪽 끝에 잇는 노드 부터 순회를 시작하여 , 루트, 오른쪽 노드로 이동하여 탐색한다

- 이진 트리 탐색의 오른차수으로 값을 가져올 때 쓰인다

 

3. 후위순회 ( postorder traverse )

- 제일 왼쪽 끝에 있는 노드 부터 순회를 시작하여 루트를 거치지 않고 오른쪽으로 이동해 오른쪽 노드를 순회루 마지막에 루트로 이동하여 탐색한다

- 트리를 삭제 할 때 사용한다

 

 

 

Graph Traversal

- 모든 정점들을 한번씩 방문하여 탐색하는 것이 목적

 

 

BFS ( Breadth-First Search )

- 가장 가까운 정점부터 탐색을 시작하고 더 탐색할 정점이 없을 때 변경된 기준에서 인접한 정점을 순서대로 방문한다

- 너비 우선 탐색

- 두 정점 사이의 최단 경로를 찾을 떄 사용한다

- 최악의 경우에는 모든 경로를 다 살펴봐야 한다

 

특징

- 하나의 정점을 기준으로 해당 정점과 인접한 정점을 모두 방문한다

- 기준점을 방문했던 정점으로 변경하여 해당 정점에서 인접한 정점(이동할 수 있는 )을 방문한다

- 이 과정을 통해서 최상위 정점을 기준으로 이어진 정점을 차례대로 방문한다

- 최단 경로 탐색에 유리하다 : FS는 루트 정점에서부터 거리가 가까운 정점을 먼저 방문하므로 최단 경로를 찾는 문제에서 유용합니다. 그래프에서 두 정점 사이의 최단 경로를 찾을 때도 BFS를 사용한다

- 방문한 정점들을 저장해야 하는 경우 메모리 사용이 크다 : BFS는 큐(Queue) 자료 구조를 사용하기 때문에, 방문한 정점들을 큐에 저장하고 있어야 한다, 그래프의 크기가 큰 경우에는 BFS보다 DFS를 사용해야 한다

- 그래프의 크기와 밀도에 따라서 성능이 달라진다 : 간선의 개수가 많으면 BFS의 성능이 저하될 수 있다, 정점의 개수가 많으면 성능이 떨어질수 있다.

- 시작 정점에서 도달할 수 없는 정점에 대해서는 탐색하지 않는다

- visited 배열과 같은 방문 여부를 체크하는 자료 구조를 사용해야 한다 : visited 배열과 같은 방문여부를 체크하는 자료구조를 사용해야 한다, 이 방문 여부를 체크하는 자료구조를 사용하지 않으면 무한루프에 빠질수 있다.

 

- BFS는 Queue 자료구조를 사용하여 구현한다

- 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 방식으로 동작한다 따라서 BFS에서는 시작 노드를 큐에 삽입한 후, 인접한 노드를 큐에 순차적으로 삽입하면서 탐색을 진행한다

 

- 최단거리를 구해야 하는 문제에 BFS를 사용한다

- 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않는 경우 BFS를 사용한

 

주의할점

1. 방문 여부 체크 : BFS를 진행하면서 방문한 정점은 다시 방문하지 않아야 한다

- BFS를 시작하기 전에 방문 여부를 체크하는 자료구조( boolean형 배열)을 초기화 해야한다

2. 큐의 적절한 활용

- 큐에 현재 정점을 삽입할 때는 반드시 방문 여부를 체크한 후 삽입해야 하며, 정점을 큐에서 꺼낼때는 큐가 비어있는지 확인한 후 꺼내야 한다

3. 최단 경로 탐색

- BFS를 활용하여 최단 경로를 찾아야 하는 경우, 큐에 정점을 삽입할 때 해당 노드까지의 거리를 기록하는 변수를 사용해야 하는 경우도 있다

4. 메모리 공간

- BFS는 큐 자료 구조를 활용하므로, 모든 정점을 큐에 저장해야 합니다. 이로 인해 메모리 공간이 크게 요구될 수 있으므로, 그래프의 크기가 큰 경우에는 메모리 문제가 발생할 수 있다

 

 

 

 

DFS ( Depth-First Search )

- 하나의 경로를 끝까지 탐색후 원하는 결과값이 아니라면 다음 경로로 넘어가 탐색한다

- 깊이 우선 탐색

- BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있다.

 

특징

- 한 분기를 탐색한 후 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색한다

- 더이상 탐색이 불가능한 상태가 되면 이전 분기로 돌아와 다음 분기를 탐색한다 : BFS보다 시간을 오래 걸릴수 있지만 모든 정점을 완전히 탐색할 수 있다, 현 경로상의 정점들만을 기억하면 되므로 저장 공간의 수요가 비교적 적고, 목표한 정점이 깊은 단계에 있으면 해를 빨리 구할 수 있다는 장점이 있ek

- 깊이 우선 탐색은 그래프 내의 순환구조를 고려하여 방문한 정점을 확인하여 이미 방문한 정점을 다시 방문하지 않도록 해야 한다 : 도달할 정점이 없으면 무한 루프에 빠질 수 있다. 실제로는 미리 지정한 임의 깊이 까지만 탐색하고 목표한 정점을 발견하지 못하면 다음 경로를 따라 탐색하는 방법을 활용할 수 있다 (찾아낸 길이 최단 경로가 된다는 보장이 없다, 목표한 정점에 이르는 경로가 다수일 경우 DFS는 목표한 정점에 최초로 다다르는 순간 탐색을 종료하므로 이때 나온 결과가 최적이 아닐수도 있다 )

- 스택 자료 구조나 재귀를 통해 구현이 가능하다

 

- 그래프의 모든 정점을 방문하는 것이 주요한 문제에 사용한다

- 경로의 특징을 저장해 둬야 하는 문제 ( 탐색 중에 장애물이 있는 경우도 포함 )  { Ex. 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된 다는 문제가 있는 등 각각의 경로마다 특징을 저장해 둬야 할 때는 DFS를 사용한다 ( BFS는 경로의 특징을 가지지 못한다 ) }

- 자동 미로 생성과 같은 문제에 활용한다 ( 방향을 무작위로 해서 계속 길을 뚫다가 막혀서 길을 뚫을 수 없다면, 뚫을 수 있는 곳이 발견될 때까지 되돌아 가서 다시 뚫고, 막히면 되돌아가고 이러한 식으로 무한히 반복하다 보면 탈출 경로는 1개만 만들어 진다 )

- 검색 대상 그래프가 정말 크다면 DFS를 고려해야 한다 ( 단지 현 경로상의 정점들만을 기억하면 되므로 저장 공간의 수요가 비교적 적고, 목표한 정점이 깊은 단계에 있으면 방문할 수 있는 루트를 빨리 구할 수 있다는 장점이 있다 )

 

 

주의할 점

- 깊이 우선 탐색을 이용할 때, 모든 정점을 방문할 수 있도록 시작 정점을 선택해야 한다

- 그래프 내의 순환구조(Cycle)를 고려하여 방문한 정점을 체크하여 이미 방문한 정점을 다시 방문하지 않도록 주의해야 한다

- 깊이 우선 탐색은 최단 경로를 보장하지 않기 때문에, 최단 경로를 찾는 것이 필요한 경우에는 다른 알고리즘을 사용해야 한다

 

 

 

Deque

- 양방향 대기열 이라고 불리는 자료구조

- ex. 실의 양쪽에 구슬을 꿰어 넣는 것과 비슷한 구조로 되어있다

- 양방향으로 열려있는 구조로 Queue와 외형적으론 비슷하지만 스택과 큐와 같이 LIFO, FIFO 같은 순서에 구속되지 않는다

 

특징

1. Stack 및 Queue를 모두 사용할 수 있다 ( 양쪽으로 데이터를 추가하고 삭제 할 수 있어서 둘다 사용 가능 )

 

1.1 추가를 제한하는 구조

---------------------------
-> insert
<- delete         delete ->
---------------------------

- 한쪽에서만 데이터 추가가 가능하고 삭제는 양방향에서 가능하게 구현하면 위 그림과 같은 구조

- 데이터 추가의 방향이 정해진 상태 ( 왼쪽으로 삭제하는 형태는 Stack과 같고 오른쪽으로 삭제하는 구조는 Queue와 같다 )

 

1.2 삭제는 제한하는 구조

---------------------------
-> insert         insert <-
<- delete
---------------------------

- 데이터 추가는 양쪽으로 가능하나 삭제는 한쪽에서만 가능한 구조

- 왼쪽에서 추가하는 형태는 Stack과 같고 오른쪽에서 추가하는 형태는 Queue와 같다

 

2. 양방향 끝에서 데이터를 추가, 삭제가 용이 하다

- Stack과 Queue에서 추가할 데이터나 삭제할 데이터의 인덱스 정보를 가지고 있듯이 Deque도 양쪽의 추가 삭제할 데이터의 인덱스 정보를 가지고 있어서 양쪽 끝의 데이터에 접근과 추가, 삭제가 용이하다

 

3. 양방향 끝이 아닌 임의의 데이터만 추가하거나 삭제하는 건 불가능하다

- Deque는 양방향 끝의 인덱스 정보를 가지고 있기에 양방향 데이터가 아닌 중간에 있는 데이터에 접근하려고 할때 양쪽 끝 이외의 인덱스 정보가 없어서 접근할 수 없다

 

 

 

Linked List

- Linked List 자료구조는 선형으로 그룹화된 데이터의 집합으로 데이터와 다음 데이터의 주소를 포함하고 있는 하나의 노드가 선형으로 연결된 자료구조이다

 

Linked List의 구조

- Linked List는 배열과 같이 선형으로 이뤄진 자료구조

- Linked List 자료구조는 연속된 공간이 아니라 흩어져 있는 공간에 노드들의 연결로 이루어져 있다

- 하나의 노드에는 데이터와 다음 노드의 주소가 담겨 있다

- 연속된 메모리 주소가 아니기에 직접 주소값을 가지고 있어야 다음 노드로 접근할 수 있다

- 마지막 노드는 다음을 가리킬 것이 없으므로 null을 가리킨다

 

LinkedList 특징

1. 노드의 추가와 삭제가 빠르고 쉽다

- 배열은 메모리 순서가 정해져 있어서 값을 추가하거나 삭제할 때 메모리에 재할당을 해야 하지만 Linked List는 순서가 지정되지 않은 특성 때문에 데이터를 담은 노드를 어디에도 손쉽게 추가하거나 삭제할 수 있다

- 7, 2, 5, 3 가 Linked List 자료구조 형태로 있다고 한다면

- 7은 2를 2는 5를 5는 3을 가리키고 있다

- 2 와 5 사이에 9를 추가하고 싶으면 2는 9를 9는5를 가리키게 바꾸면 2와5 사이에 9가 추가되는 형태이다

- 반대로 9를 삭제하려고 한다면 9는 5를 가리키고 있는데 5가 아닌 null을 가리키게 하고 2를 5로 가리키게 한다면 9가 삭제가 가능하다

 

2. 노드의 값을 찾으려면 최대 전체를 순회해야 한다

- Linked List의 노드는 메모리에 흩어져 있어서 특정 노드로 쉽게 접근할 수 없다

- Linked List의 첫 번째 노드를 head node라고 하는데 순회하기 전까지는 head node의 정보만 알고 있다.

- 필요한 값이 있는지 확인하려면 head node에 연결된 다음 노드로 접근해야 하고, 접근한 노드에 원하는 값이 없다면 다시 다음 노드로 이동해야 한다

- 마지막 요소에는 무엇이 있는지 확인하려면 Head node에서 출발하여 마지막 노드까지 전부 순회해야 알수 있다

 

Linked List 실사용 

- 삽입과 삭제가 중요한 곳에 사용한다  ( join, split method처럼 데이터 삽입 삭제가 중요한 메서드의 구현에도 활용할 수 있다 )

- 동적 기억장소 관리 ( 실행되는 작업에 필요한 크기만큼의 메모리를 할당하는 방법에 활용 )

- Garbage collection ( 참조자료형의 데이터 타입을 관리하는 알고리즘 중 하나이다 )

 

 

 

 

Hash Table

- 해쉬 함수를 사용하여 해쉬를 색인( index )으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조이다

- 필요한 데이터의 키(key)를 해시함수를 사용해 별도의 해시(hash)로 바꿔 주고, 해당하는 데이터(value)를 함께 저장하는 자료구조이다

 

Hash Table 구조

- 키(key)와 해시함수(hash function), 해시(hash), 데이터(value)로 이루어져 있다

- 키(key) : 고유한 값으로 해시 함수의 입력값이 된다, 다양한 길이의 값이 들어올 수 있다. 해시 함수를 통해 변환하지 않은 상태로 저장소에 저장이 되면 다양한 길이만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장하게 된다

- 해쉬함수(Hash Function ) : 키(key)를 해시(hash)로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 것이 중요하다.

- 해쉬(Hash) : 키(key)를 해시함수(hash function)를 사용하여 만들어진 결과물로, 저장소에서 데이터(value)와 매칭되어 저장된다. 변환된 값을 배열의 색인(index)과 같이 사용하게 된다.

- 데이터 (value) : 저장소에 최종적으로 저장되는 값으로 색인(index)과 매칭되어 저장된다

 

Hash Table의 특징

- hash table에서 저장, 삭제, 검색 과정은 모두 평균적으로 O(1)의 시간복잡도를 가지고 있어 데이터를 다루는 작업이 매우 빠르다는 장점이 있다

- 해시 충돌이 발생할 수 있고 데이터가 저장되기 전에 저장공간을 미리 만들어놔야 하기 때문에 공간 효율성이 떨어진다 또한 해시함수(hash function)의 의존도가 높다

- 해시 함수(hash function)가 복잡하다면, 해시(hash)값을 만들어내는 데 많은 시간이 소요된다

 

1. 저장, 삭제, 검색 과정

- hash table에서 값을 저장, 삭제, 검색하기 위해서는 해시 함수(hash function)에 키(key) 값을 넣어 해시(hash) 값을 만들게 된다 이후 만들어진 해시(hash)값과 일치하는 색인(index)을 찾아 저장하거나 삭제, 검색한다 ( 기본적인 시간 복잡도는 O(1) 이다 )

- 해시함수(hash function)를 거쳐 해시(hash)값을 찾아내는데 걸리는 과정은 고려하지 않는다 그러나 해싱 충돌이 발생할 경우 저장소의 모든 색인(index)(삽입) 혹은 데이터(value)(삭제, 검색)를 찾아봐야 하기 때문에 O(n)이 된다

 

2. 대표적인 해쉬 알고리즘

- Division Method : Number type의 키(key)를 저장소의 크기로 나누어 나온 나머지를 색인(index)으로 사용하는 방법 ( 이때 저장소의 크기를 소수(Prime Number)로 정하고 2의 제곱수와 먼 값을 사용하는 것이 효과가 좋. 예를 들어 Key 값이 23일 때 테이블 크기가 7이라면 index는 2가 된다 )

- Digit Folding : 키(key)의 문자열을 ASCII 코드로 바꾸고 그 값을 합해 저장소에서 색인(index)으로 사용하는 방법 ( 이때 색인(index)가 저장소의 크기를 넘어간다면 Division Method를 적용할 수 있다 )

- Multiplication Method : 숫자로 된 Key 값 K와 0과1 사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같이 계산한 값을 사용한다  index = (KA mod 1)m

- Universal Hashing : 다수의 해시함수를 만들어 특정한 장소에 넣어두고, 무작위로 해시함수를 선택해 해시(hash)값을 만드는 기법

 

해쉬 충동을 해결할 수 있는 방법 

 

1. 개방 연결법

- 해시 충돌이 발생하면 다른 색인(index)에 해당 자료를 삽입하는 방식

1.1 Linear Probing : 현재 중복된 색인(index)으로부터, 고정된 숫자만큼 이동하여 비어있는 저장소(버킷)를 찾아 데이터(value)를 저장한다

1.2 Quadratic Probing : 재 중복된 색인(index)으로부터 이동할 숫자를 제곱으로 사용하는 방식 ( 처음 충돌이 발생하면 1(1^2)만큼 이동하고, 또 충돌이 발생한다면 4(2^2)만큼, 3번째는 9(3^2)만큼, 4번째는 16(4^2)만큼 이동하여 빈 공간을 탐색하는 방법 )

1.3 Double Hashing Probing : 하나의 해시함수(hash function)에서 충돌이 발생한다면 미리 지정해 둔 다른 해시함수(hash function)를 이용해 새로운 주소를 받아 사용하는 방법,  다른 방법들보다 많은 연산이 필요하다

 

2. 분리 연결법

- 분리 연결법이란 동일한 색인(index)의 데이터에 대해 연결리스트(linked list), 트리(Red-Black tree) 등의 자료구조를 활용해 데이터의 주소를 저장하는 방법

- 구현이 간단하며, 데이터(value)를 쉽게 삭제할 수 있다는게 장점이지만 중복으로 저장되는 데이터(value)가 많아지면 동일한 버킷에 연결되는 데이터(value)가 많아져서 검색의 효율성이 감소하는 단점이 있다

 

3. 저장소 확장

- 저장소에 크기가 작다면, 불필요한 메모리 사용을 줄일 수 있지만, 해시 충돌이 발생하며 개방 연결법(Open Addressing)이나 분리 연결법(Separate Chaining)을 사용해도 성능상 손실이 발생한다

- 실제 Java에서 사용되는 HashMap이라는 자료 구조는 매치된 key-value 데이터 개수가 일정 이상이 된다면(저장소의 75% 이상 사용) 저장소의 크기를 두 배로 늘리게 된다. 이 방식으로 해시 충돌로 인한 성능이 감소하는 문제를 어느 정도 해결이 가능하다

 

 

 

 

 

Heap Tree

- 트리 구조로 구현된 자료구조

- 일반적인 트리 구조와는 다르게, heap tree는 우선순위에 따라서 빠르게 자료를 검색할 수 있는 구조

- 우선순위를 정해서 먼저 자료를 찾아내고 처리하기 위해 만들어진 자료구조

 

Heap Tree의 구조

- 느슨한 정렬 구조로 되어있다 ( 부모 노드의 값은 자식 노드의 값보다 항상 크거나 항상 작게 정렬되어 있지만 자식 노드끼리의 값의 크기에 따라 좌우 위치는 정렬하지 않기 때문에 느슨한 정렬 구조라고 한다 ) 

 

Heap Tree의 구조

1. 완전 이진 트리 : 완전 이진트리로 구성되어 있습니다. 단순히 최대값, 최소값을 찾기 위해서는 완전 이진트리로 구성할 필요는 없지만, 삽입/삭제 시 성능을 위해 완전 이진트리로 구현하게 된다

2. 중복된 값 저장 : 일반적인 이진 탐색 트리와 다르게 중복된 값을 저장할 수 있다. 단순히 최소, 최대값을 찾아내기 위한 구조이기 떄문이다

3. 최대 힙 / 최소 힙 :  최대 힙과 최소 힙으로 구현한다 ( 루트 노드에 가장 큰 값이 위치하며 자식 노드로 내려갈수록 작은 값이 위치하게 구현한다면, 최대 힙 // 루트 노드에 가장 작은 값이 위치하며, 자식 노드로 내려갈수록 큰 값이 위치하게 구현한다면, 최소 힙)

 

 

Heap Tree의 데이터 처리 방식

1. 데이터 검색 ( 최대 / 최소 값 )

- 최대 힙일 경우 최대값을 찾는 데 걸리는 시간복잡도는 O(1), 최대 힙일 경우 항상 루트 노드의 값이 가장 큰 값이기 때문에, 최대값은 항상 루트 노드의 값을 불러오기만 하면 된다

- 최소 힙일 경우도 마찬가지로, 루트 노드의 값이 가장 작은 값이기 때문에, 동일하게 O(1)의 시간복잡도를 가지게 된다

2. 데이터 삽입

- 가장 마지막 노드에 새로운 값을 저장

- 삽입된 노드의 값과 부모 노드의 값을 비교

- 최대 힙일 경우, 부모의 값이 더 크다면 부모의 값과 위치를 서로 변경

- 더 이상 위치가 바뀌지 않을 때까지 1~3까지의 과정을 반복

3. 데이터 삭제

- 루트 노드의 값을 제거

- 루트 자리에 마지막 노드의 값을 삽입

- 올라간 노드의 값과 그 자식 노드들의 값과 비교

- 모보다 더 큰 자식이 있다면(최대 힙) 해당 자식의 값과 서로 교환 ( 두 자식의 값이 모두 부모보다 작다면 두 값중 큰 값과 위치 변경 )

- 더 이상 큰 값이 없을 때까지 반복

 

Heap Tree를 배열로 구현하기

- Haep Tree는 완전 이진 트리로 구성되어 있어 배열로 표현이 가능하다

- 완전 이진트리의 특성상 중간에 빈값이 없기 때문에, 루트 노드부터 높이 순서대로 배열에 모두 정렬이 가능하다

- 현과 노드의 위치를 찾기 쉽게 하기 위해 일반적으로 배열의 0번째 인덱스는 사용하지 않고, 첫 번째 인덱스부터 사용한다

- 위의 그림처럼 높이 순서대로 배열에 값을 저장하며, 좌에서 우로 순서대로 값을 저장한다

- 배열로 heap tree를 구현한다면 배열의 크기에 따라서 heap tree의 depth가 얼마인지, 부모와 자식 노드의 위치까지도 쉽게 검색할 수 있다

- depth(깊이)는 배열의 길이가 1, 3, 7, 15 순서대로 2의 배수를 계속 더한 만큼 depth(깊이)가 늘어난다

- 부모와 자식 노드의 인덱스를 찾는 방법도 수식으로 계산할 수 있다

- 현재 노드의 왼쪽 자식 노드의 인덱스는 `현재 노드의 인덱스 * 2`입니다.
- 현재 노드의 오른쪽 자식 노드의 인덱스는 `(현재 노드의 인덱스 * 2) + 1`입니다.
- 부모의 인덱스는 `자식 노드의 인덱스 / 2` (내림)입니다.

 

Heap Tree가 우선 사용되는 곳은 우선순위 큐, 힙 정렬이 있다

 

 

 

 

 

## 금일은 트리와 그래프를 순회 하면서 탐색하는 방법, 과정을 학습하였다

트리는 어떤식으로 어떤 구조를 가지고 만들어지는 지를 이해하고 있기 떄문에 탐색을 하는 방법을 학습하는 데에는 큰 어려움이 있지 않았지만, 그래프의 경우 아직 어떻게 짜여지고 어떻게 정점과 정점을 간선으로 이어야 하는지 그 개념 자체를 이해하는데 어려움이 있기 때문에 코드를 구현하는것 부터 어려움이 있었다. 그렇기에 그래프는 순회 하면서 탐색하는 과정을 학습하는데에도 어려움이 다수 있었다.

오늘은 정규 학습 시간 이후에 시간을 더 내어 구글링이나 동영상을 통해 그래프에 대해 좀더 학습하는 시간을 가져야 겠다.