자료구조 - [스택, 큐, 트리, 그래프]

자료구조란 무엇일까요?

자료구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것입니다.

 

...

데이터(data)는 무엇일까요?

데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값

 

 

---

 

Stack의 특징

1. LIFO(Last In First Out)

2. 데이터는 하나씩 넣고 뺄 수 있습니다.

3. 하나의 입출력 방향을 가지고 있습니다.

4. 저장되는 데이터는 유한하고 정적이어야 합니다.

5. 스택의 크기는 제한되어 있습니다.

브라우저 활용: 뒤로가기, 앞으로가기

입력 : push / 출력 : pop

 

 

---

 

Queue의 특징

1. FIFO (First In First Out)

2. 데이터는 하나씩 넣고 뺄 수 있습니다.

3. 두 개의 입출력 방향을 가지고 있습니다.

enqueue : 입력 / dequeue : 출력

활용: 프린트 버퍼 (데이터를 주고받을때 각 장치 사이에 존재하는 속도의 차이나 시간차이를 극복하기 위해 임시기억장치로 큐,,사용)

 

 

---

 

 

Tree

이진 트리(Binary tree)

자식 노드가 최대 두 개인 노드들로 구성된 트리입니다.

이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있습니다.

이진 트리는 자료의 삽입, 삭제 방법에 따라 나뉩니다.

 

정 이진 트리(Full binary tree) - 각 노드가 0개 혹은 2개의 자식 노드를 갖습니다.

 

완전 이진 트리(Complete binary tree) - 정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.

 

포화 이진 트리(Perfect binary tree) - 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.

 

 

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리란 이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 이진트리

각 노드에 중복되지 않는 키(Key)가 있습니다.

루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있습니다.

루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있습니다.

좌우 서브트리도 모두 이진 탐색 트리여야 합니다.

 

이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징

 

이진 탐색 트리의 탐색은 다음과 같은 과정을 거친다.

1. 루트 노드의 키와 찾고자 하는 값을 비교합니다. 만약 찾고자 하는 값이라면 탐색을 종료합니다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행합니다.
3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행합니다.

 

 

전위 순회 (preorder traverse)

전위 순회에서 가장 먼저 방문하는 노드는 루트입니다.

루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색을 합니다.

즉 부모 노드가 제일 먼저 방문되는 순회 방식입니다.

전위 순회는 주로 부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용하게 됩니다.

 

중위 순회 (inorder traverse)

중위 순회는 루트를 가운데에 두고 순회합니다.

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

부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식입니다. 중위 순회는 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰입니다.

 

후위 순회 (postorder traverse)

후위 순회는 루트를 가장 마지막에 순회합니다.

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

후위 순회는 트리를 삭제할 때 사용합니다.

자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문입니다.

 

 

---

 

 

Graph

여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

 

Graph의 목적

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적

 

Graph의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다.
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어집니다.
• 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 합니다.

 

Graph의 표현 방식

인접 행렬

두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 이야기합니다.

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타냅니다.

만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표입니다.

• A의 진출차수는 1개 입니다: A —> C
  • [0][2] === 1
• B의 진출차수는 2개 입니다: B —> A, B —> C
  • [1][0] === 1
  • [1][2] === 1
• C의 진출차수는 1개입니다: C —> A
  • [2][0] === 1

 

 

 

인접 리스트

각 정점이 어떤 정점과 인접하는지 리스트로 표현.
각 정점마다 리스트를 갖고있다.

 

>>

• 우선 순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용하는 것이 합리적입니다. 따라서 보통은 중요하지 않습니다.

• 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용합니다.
• 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지합니다.

 

 

알아둬야 할 Graph 용어들

• 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소입니다.
• 간선 (edge): 정점 간의 관계를 나타냅니다. (정점을 이어주는 선)
• 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.
• 가중치 그래프 (weighted Graph): 연결의 강도가 얼마나 되는지 적혀져 있는 그래프를 뜻합니다.
• 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.
• 무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프입니다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능합니다. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
• 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
• 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다. 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프입니다.

 

 

BFS, DFS 

그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며,
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다.

DFS 깊이 우선 탐색 (Depth-First Search)

출처 https://developer-mac.tistory.com/64

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다.

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있습니다.

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

 

BFS 너비 우선 탐색 (Breadth-First Search)

출처 https://developer-mac.tistory.com/64

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다.
ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우

• 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
• 너비 우선 탐색의 경우 - Sam과 가까운 관계부터 탐색