[CS] 자료구조 - 스택, 큐, 트리, 인접행렬, 인접리스트, 맵, 셋, 해시테이블, 힙

안녕하세요! 하마코입니다. 😊

 

시간복잡도, 공간복잡도, 포인터를 공부했던 1탄에 이어

스택, 큐, 트리, 이진트리, 인접행렬, 인접리스트 등

자료구조 개념들을 더 공부해보겠습니다-!

 

자료구조 공부 완료해볼게요! 😎

 

---

 

스택 (stack)

스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는

후입선출(LIFO, Last In First Out)을 가진 자료구조입니다.

재귀적인 함수, 알고리즘 에 사용되며 웹 브라우저 방문 기록 등에 쓰입니다.

시간복잡도
- n번째 참조, 탐색 : O(n) / 가장 앞부분 참조, 삽입, 삭제(n번째 제외) : O(1)

#include <bits/stdc++.h>
using namespace std;
stack<string> stk;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    stk.push("하");
    stk.push("마");
    stk.push("코");
    while (stk.size()) {
        cout << stk.top() << "\n";
        stk.pop();
    }
}
// 코마하 로 출력

• 메서드
  • push(value) : 스택에 추가
  • pop() : 가장 마지막에 추가한 요소 지움 (=가장 위에 있는 요소 지움)
  • top() : 가장 마지막에 있는 요소 참조 (=가장 위에 있는 요소 참조)
  • size() : 스택 크기

 

큐 (Queue)

큐는 먼저 집어넣은 데이터가 먼저 나오는 성질인

선입선출(FIFO, First In First Out)을 지닌 자료구조입니다. (스택과 반대!)

CPU 작업을 기다리는 프로세스, 스레드 행렬, 네트워크 접속 기다리는 행렬, 너비우선 탐색, 캐시 등에 사용됩니다.

시간복잡도
- n번째 참조, 탐색 : O(n) / 가장 앞부분 참조, 삽입, 삭제(n번째 제외) : O(1)

#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int main() {
    for(int i=1; i<=10; i++) q.push(i);
    while(q.size()) {
        cout << q.front() << ' ';
        q.pop();
    }
    return 0;
}
// 1 2 3 4 5 6 7 8 9 10

• 메서드
  • push(value) : value를 큐에 추가
  • pop() : 가장 앞에 있는 요소 제거
  • size() : 큐의 크기
  • front() : 가장 앞에 있는 요소 참조

 

그래프 이론 기초 (Graph, Vertex, Edge, Weight)

정점(Vertex)은 노드라고도 불리며 그래프를 형성하는 기본 단위입니다.

정점은 분할할 수 없는 객체이자 '점'으로 표현되는 위치, 사람, 물건 등이 될 수 있습니다.

 

간선(Edge)은 정점을 잇는 선을 의미합니다. 관계, 경로 등이 될 수 있습니다.

한 방향으로만 가면 단방향 간선, 양방향으로 갈 수 있다면 양방향(=무방향) 간선이라고 합니다.

정점으로 나가는 간선을 해당 정점의 outdegree라고 하며, 들어오는 간선을 해당 점점의 indegree라고 합니다.

 

가중치(Weight)는 정점과 정점 사이에 드는 비용을 뜻합니다.

1번 노드에서 2번 노드까지 가는 비용이 한 칸이라면, 1번 노드에서 2번 노드까지의 가중치는 한 칸입니다.

 

지금까지 설명한 정점과 간선들로 이루어진 집합을 "그래프(Graph)"라고 합니다.

 

 

트리 (Tree Data Structure)

트리는 자식노드와 부모노드로 이루어진 계층적인 구조를 가지며,

무방향 그래프이자 사이클이 없는 자료구조를 의미합니다.

 

트리의 특징은 다음과 같습니다.

1. 부모, 자식 계층 구조를 가진다.
2. V-1=E 라는 특징이 있다. (간선 수 = 노드 수-1)
3. 임의의 두 노드 사이의 경로는 유일무이하게 존재한다.
   ( 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있으며 하나만 존재한다.)

노드의 종류

• 루트노드 : 가장 위에 있는 노드
• 리프노드 : 자식노드가 없는 노드
• 내부노드 : 루프노드와 리프노드 사이에 있는 노드
  • 높이 : 루프 노드부터 리프 노드까지의 거리 중 가장 긴 거리
  • 깊이=레벨 : 각 노드마다 다르며, 루프 노드에서 특정 노드까지 최단 거리로 갔을 때의 거리
  • 서브트리 : 트리 내의 하위 집합
  • 숲 : 트리로 이루어진 집합

 

이진트리 (Binary Tree)

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

[출처] Shutterstock

이진트리 종류	트리 의미
Full Binary Tree (정이진 트리)	자식 노드가 0 또는 2개인 이진 트리
Complete Binary Tree (완전 이진 트리)	왼쪽에서부터 채워져 있는 이진 트리, 마지막 레벨을 제외하고 모든 레벨 완전히 채워져있어야함
Degenerate Binary Tree (변질 이진 트리)	모든 노드가 자식 노드가 하나밖에 없는 이진 트리
Perfect Binary Tree (포화 이진 트리)	모든 노드가 꽉 차 있는 이진 트리
Balanced Binary Tree (균형 이진 트리)	모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 차이가 1이하인 트리

 

 

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

이진탐색트리는 이진트리의 하나로,

노드의 오른쪽 하위 트리에는 "노드의 값보다 큰 값"이 있는 노드만 포함되고

왼쪽 하위트리에는 "노드의 값보다 작은 값"이 들어있는 트리를 말합니다.

[출처] Shutterstock

 

왼쪽에는 작은 값, 오른쪽에는 큰 값이 이미 정해져있기 때문에

특정 값을 찾을 때 왼쪽/오른쪽으로 가면 되는 게 자명해서 전체탐색을 하지 않아도 됩니다.

시간복잡도 : O(logN)

 

 

인접 행렬 (adjacency matrix)

컴퓨터에 그래프를 아려줄 표현방법으로는 인접 행렬, 인접 리스트가 있는데요.

트리 모양을 그대로 컴퓨터에 그릴 수는 없기에 위 방법들을 사용합니다.

 

인접 행렬은 그래프에서 정점과 간선의 관계를 나타내는 Bool 타입의 정사각형 행렬입니다.

부울형이다보니 행렬에는 0과 1만 들어가고,

정점끼리 이어져있으면 1, 정점 사이 경로가 없으면 0으로 나타내는 행렬이 됩니다.

아래 예시로 살펴보겠습니다.

 

이런 그래프가 있을 때, 

그래프

0,1,2,3은 각 행과 열이 되고 간선 여부로 0/1을 나타내면 아래의 표처럼 정사각형 행렬이 만들어집니다.

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

 

그리고 코드로 표현하면 다음과 같습니다.

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

 

 

인접행렬을 이해하기 위한 다양한 예시가 있었어요! (큰돌님의 자료에서 🥹)

• 3번 노드 -> 5번 노드 단방향 경로를 인접행렬로
  a[3][5] = 1;
• 3번 노드 <-> 5번 노드 양방향 경로를 인접행렬로
  a[3][5] = 1;
  a[5][3] = 1;
• 정점 개수 20개인 그래프를 인접행렬로 표현할 때 메모리를 최소로 쓴다고 하면?
  bool a[20][20];

 

인접리스트 (adjacency list)

인접 리스트는 그래프에서 정점과 간선의 관계를 나타내는 연결리스트입니다.

연결리스트뿐만 아니라 벡터로도 구현이 가능합니다.

 

인접리스트를 아까처럼 그래프를 예시로 연결리스트로 바꾸는 과정을 알아보겠습니다.

그래프

이 그래프를 연결리스트로 나타내면 아래와 같이 됩니다.

이를 코드로 나타내면 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
const int V=4;
vector<int> adj[V];

int main() {
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[0].push_back(3);
    
    adj[1].push_back(0);
    adj[1].push_back(2);
    
    adj[2].push_back(0);
    adj[2].push_back(1);
    
    adj[3].push_back(0);
    
    for(int i=0;i<4;i++) {
        cout << i << " :: ";
        for(int j=0;j<adj[i].size();j++) {
    		cout << adj[i][j] << " ";
        }
        cout << "\n";
    }
}

 

연결리스트의 시간복잡도와 vector의 시간복잡도를 비교하면 아래와 같습니다.

	연결리스트	vector
n번째 인덱스에 삽입, 삭제	O(1)	O(n)
마지막 요소에 삽입, 삭제	O(1)	O(n)
특정 요소 탐색	O(n)	O(n)
n번째 요소 참조	O(n)	O(1)

 

 

인접행렬 vs 인접리스트

• 공간복잡도
  • 인접행렬 : O(V^2)
  • 인접리스트 : O(V+E)
• 간선 한 개 찾기 시간복잡도
  • 인접행렬 : O(1)
  • 인접리스트 : O(V)
• 모든 간선 찾기 시간복잡도
  • 인접행렬 : O(V^2)
  • 인접리스트 : O(V+E)

 

맵 (Map)

맵은 고유한 키를 기반으로 키-값(Key-Value) 쌍으로 이루어져 있는 자료구조입니다.

삽입할 때마다 자동 정렬되는 구조를 갖고 있습니다.

시간복잡도
- 참조, 탐색, 삽입, 삭제 : O(logn)

 

고유한 키를 갖기 때문에 하나의 키에 중복한 값이 들어갈 수 없으며

자동으로 오름차순 정렬되기 때문에 순서대로 Map을 탐색할 수 있는 것이 아닌

아스키코드 순으로 정렬된 값들을 기반으로 탐색하게 됩니다.

또한, [] 로 키를 직접 참조할 수 있습니다.

맵의 key와 value는 string, int 등 다양한 값이 들어갈 수 있습니다.

 

셋 (Set)

셋은 고유한 요소만을 저장하고 중복을 허용하지 않는 자료구조입니다.

맵처럼 {key, value}로 집어넣지 않아도 되며, 중복된 값은 제거되고 맵처럼 자동 정렬됩니다.

시간복잡도
- 참조, 탐색, 삽입, 삭제 : O(logn)

 

해시테이블 (Hash Table)

해시 테이블은 큰 범위를 가진 다양한 데이터들을 해싱을 통해 한정된 범위의 정수값을 가진 해시로 만들고,

해시라는 키에 대응하여 원본 데이터들을 매핑시켜놓은 테이블입니다.

• 해시 : 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값
• 해싱 : 임의의 데이터를 해시로 바꿔주는 과정이며 해시 함수가 이를 담당
• 해시 함수 : 임의의 데이터를 입력으로 받아 고정된 길이의 해시로 바꿔주는 함수

 

힙 (Heap)

힙은 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 완전 이진 트리를 의미합니다.

가장 작은 요소가 루트노드에 있는 최소힙,

가장 큰 요소가 루트노드에 있는 최대힙이 있습니다.

• 최대힙 : 부모노드 값은 자식노드의 값보다 항상 큰 규칙을 지키는 힙 (최대값 O(1)만에 찾을 수 있음!)
• 최소힙 : 부모노드 값은 자식노드 값보다 항상 작은 규칙을 갖는 지키는 힙 (최소값 O(1)만에 찾을 수 있음!)

힙의 데이터 삽입은 아래 순서로 이루어집니다.

1. 리프노드에 삽입할 노드를 삽입한다.
2. 해당노드와 부모노드를 서로 비교한다.
3. 규칙(최소힙 또는 최대힙)에 맞으면 그대로 두고, 그렇지 않으면 부모노드와 교환한다. (스왑)
4. 규칙에 맞을 때까지 3번 과정을 반복한다.

힙의 데이터 삭제는 아래 순서로 이루어집니다.

1. 루트 노드를 제거한다.
2. 루트 자리에 가장 마지막 노드를 삽입한다.
3. 올라간 노드와 그의 자식 노드를 비교한다.
4. 규칙을 만족하면 그대로 두고, 그렇지 않으면 자식노드와 교환한다.

시간복잡도
- 참조(최대/최소값) : O(1)
- 탐색 : O(n)
- 삽입, 삭제 : O(logn)

 

---

 

오늘은 자료구조 정리 마무리를 해보았습니다!

트리도 알고리즘 문제 풀 때 꼭 필요한 개념이라

정리를 하면서도 꼼꼼히 보았던 것 같습니다-!

도움이 되셨다면 좋아요, 댓글 남겨주세요!

 

긴 글 읽어주셔서 감사합니다. :)

HAMACO