자료구조 정리

찬비의 개발블로그·2021년 11월 2일

cs공부

자료구조

Array (배열)

같은 타입의 데이터를 나열한 선형 자료구조
연속된 메모리 공간에 순차적으로 저장
랜덤 액세스가 가능
탐색에는 O(1) , 삽입 삭제일 경우 데이터들의 이동으로 인해 O(n)
장점
- 인덱스를 가지고 있어 바로 접근 가능
- 연속된 메모리 공간에 존재하기 때문에 관리하기가 편하다.
단점
- 삽입과 삭제가 어렵고 오래 걸린다
- 배열의 크기를 바꿀 수 없다.
- 연속된 메모리라서 중간에 데이터가 삭제되면 공간 낭비가 발생
- 처음에 배열 크기를 100으로 생성했는데 10정도만 쓰면 빈 공간 낭비
- 연속적인 메모리 할당이 필요한게 오히려 메모리 공간을 많이 사용하게 될 수 있다.
데이터 개수가 확실하게 정해져 있을 때, 데이터의 삭제와 삽입이 적고 검색이 빈번할 때 사용한다.

LinkedList

데이터를 순차적으로 저장하는 선형 자료구조
불연속적 메모리 공간에 저장
각 노드들은 데이터와 다음 노드를 가리키는 포인터로 이루어져 노드를 연결하여 만든 리스트
크기가 고정되어 있지 않고 데이터를 추가 크기 제한에서 자유롭지만 인덱스 접근이 불가능하다.
삽입, 삭제 O(1)이지만 자리 탐색 시간 O(n)필요하여 결과적으로 O(n), 탐색 O(n)
장점
- 포인터로 연결되어 있어서 포인터가 가리키는 노드만 변경해주면 되므로 삽입과 삭제가 용이하다.
- 크기가 정해져 있지 않고 동적으로 생성되며 연속적인 메모리 할당이 필요하지 않다.
- 사용한 메모리 재사용이 가능하다.
단점
- 원소를 탐색할 때 임의 접근이 불가능하여 데이터 검색할 때 느리다. (이중 연결 리스트, 원형 연결 리스트 로 개선)
- 포인터로 인하여 저장 공간의 낭비가 발생하다.
크키가 정해져 있지 않을 때나 삽입과 삭제가 자주 일어나며 검색을 자주 하지 않을 때 사용한다.

HashTable

(Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조
빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문
해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용하여 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
데이터 저장 삭제 조회 평균 시간복잡도 O(1)
HashTable 구조
- Key, Hash Function, Hash, Value, 저장소(Bucket, Slot)로 구성
- Key
  - 고유한 값
  - 저장 공간의 효율성을 위해 Hash Function에 입력하여 Hash로 변경 후 저장
  - Key는 길이가 다양하기 때문에 그대로 저장하면 다양한 길이만큼 저장소 구성이 필요
- Hash Function
  - Key를 Hash로 바꿔주는 역할
  - 해시 충돌(서로 다른 Key가 같은 Hash가 되는 경우)이 발생할 확률을 최대한 줄이는 함수를 만드는 것이 중요
- Hash
  - Hash Function의 결과
  - 저장소에서 Value와 매칭되어 저장
- Value
  - 저장소에 최종적으로 저장되는 값
  - 키와 매칭되어 저장, 삭제, 검색, 접근 가능
HashTable 동작 과정
- Key -> Hash Function -> Hash Function 결과 = Hash
- Hash를 배열의 Index로 사용
- 해당 Index에 Value 저장
- HashTable 크기가 10이라면 A라는 Key의 Value를 찾을 때 hashFunction("A") % 10 연산을 통해 인덱스 값 계산하여 Value 조회
해시 충돌을 해결하는 방법
- 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing)
- 분리 연결법
  - 동일한 버킷의 데이터에 대해 리스트 같은 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장
  - 장점 : 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며 손쉽게 삭제할 수 있다
  - 단전 : 데이터의 수가 많아지면 동일한 버킷에 체이닝되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소
- 개방 주소법
  - 비어있는 해시 테이블 공간을 활용하는 방법.
  - Linear Probing은 순차적으로 탐색하여 비어있는 버킷을 찾는 방식
  - Quadratic Probing은 2차 함수 이용하여 탐색하는 방식
  - Double Hashing Probing은 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식.
- Open Address vs Separate Chaining
  - 개방 주소법은 연속된 공간에 저장하기 때문에 분리 연결법에 비해 캐시 효율이 높다. 따라서 데이터의 개수가 충분히 적다면 개방 주소법이 성능이 더 좋다. 그리고 테이블의 확장도 더 늦출 수 있다
  - 개방 주소법은 분리 연결법보다 느리다.
시간복잡도 O(1)이지만 데이터 충돌이 발생한 경우 O(n)까지 증가할 수 있다. 충돌을 방지하는 방법들은 공간을 많이 사용한다는 치명적인 단점, 만약 테이블이 꽉 차있는 경우라면 테이블을 확장해주어야 하는데, 이는 심각한 성능 저하
해시 테이블에서 자주 사용하게 되는 데이터를 캐시에 적용하면 효율을 높일 수 있다.
해시맵과 해시테이블의 차이
- 해시테이블
  - 동기화를 지원함, 따라서 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황
  - key-value 값으로 null 미허용
  - 보조 hash function과 seperating chaining을 사용해서 비교적 충돌 덜 발생
- 해시맵
  - 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해시맵을 사용
  - key-value 값으로 null

Stack

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO 형식의 선형 자료 구조
장점 : 구조가 단순해서 구현이 쉽고 데이터 저장/읽기 속도가 빠르다.
단점 : 데이터 최대 개수를 미리 정해야한다, 저장 공간의 낭비가 발생할 수 있음, 맨 위의 원소만 접근 가능함
스택(Stack)의 연산
- pop(): 스택에서 가장 위에 있는 항목을 제거한다.
- push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
- peek(): 스택의 가장 위에 있는 항목을 반환한다.
- isEmpty(): 스택이 비어 있을 때에 true를 반환한다.
사용사례
- 재귀 알고리즘
- 웹 브라우저 방문기록 (뒤로가기)
- 실행 취소 (undo)
- 역순 문자열 만들기
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
  - Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
- 후위 표기법 계산
재귀 알고리즘이나 역추적에 사용

Queue

한 쪽 끝에서 자료를 넣으면 반대쪽 끝에서 자료를 뺄 수 있는 FIFO 형식의 선형 자료 구조
장점 : 데이터의 삽입/삭제가 빠르다.
단점 : 중간에 위치한 데이터로의 접근이 어렵다.
큐(Queue)의 연산
- add(item): item을 리스트의 끝부분에 추가한다.
- remove(): 리스트의 첫 번째 항목을 제거한다.
- peek(): 큐에서 가장 위에 있는 항목을 반환한다.
- isEmpty(): 큐가 비어 있을 때에 true를 반환한다.
사용 사례
- 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
- 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
- 노드를 접근한 순서대로 처리할 수 있다.
- 캐시(Cache) 구현
- 우선순위가 같은 작업 예약 (인쇄 대기열)
- 선입선출이 필요한 대기열 (티켓 카운터)
- 콜센터 고객 대기시간
- 프린터의 출력 처리
- 윈도우 시스템의 메시지 처리기
- 프로세스 관리
데이터를 입력된 순서대로 처리해야 할 때나 너비 우선 탐색을 구현할 때 사용한다.

Graph (MST-kruskal, Prim)

노드와 노드를 연결하는 간선을 하나로 모아 놓은 자료 구조 비선형 자료구조
네트워크 모델
방향이 없는 무방향 그래프, 간선에 방향성이 존재하는 방향 그래프
간선에 비용이나 가중치가 할당된 가중치 그래프
무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 연결 그래프, 반대는 비연결 그래프
그래프에 속해 있는 모든 정점이 서로 연결되어 있는 완전 그래프
그래프의 구현 방법
- 인접 리스트와 인접 행렬 방법
- 인접 리스트
  - 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우에 사용한다.
  - 장점은 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있고 그래프에 존재하는 모든 간선의 수는 O(N+E) 안에 알 수 있다.
  - 단점은 간선의 존재 여부를 알려면 정점의 차수만큼의 시간이 필요하다.
- 인접 행렬
  - 그래프에 간선이 많이 존재하는 밀집 그래프의 경우 사용한다.
  - 두 정점을 연결하는 간선의 존재 여부를 O(1)안에 즉시 알 수 있다.
  - 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야 한다는 단점.
그래프 탐색 방식은 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

Tree (Binary Tree, Full Binary Tree, Complete Binary Tree, BST)

그래프의 한 종류
방향성있는 비순환 그래프의 한 종류 비선형 자료구조
사이클이 존재할 수 없는 하나의 연결 그래프
트리는 하나의 루트 노드를 가지고 루트 노드는 0개 이상의 자식 노드를 갖고 있다. 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 반복적으로 정의
트리의 구성요소
- Node : 트리를 구성하고 있는 각각의 요소
- Edge : 트리를 구성하기 위해 노드와 노드를 연결하는 선
- Root Node : 트리 구조에서 최상위에 있는 노드
- Terminal Node(=Leaf Node) : 하위에 다른 노드가 연결되어 있지 않은 노드
- Internal Node : 단말 노드를 제외한 모든 노드로 루트 노드를 포함
계층 모델
루트에서 어떤 노드로 가는 경로는 유일하다
한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
순회는 전위(Preorder), 중위(Inorder), 후위(Postorder) 3가지
트리 종류
- 이진 트리, 이진 탐색 트리, 균형 트리, 이진 힙 등의 종류가 있다.
- 이진 트리
  - 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.
  - 나뉘어진 두 서브 트리도 모두 이진 트리
  - 공집합도 이진 트리로 포함.
- 완전 이진 트리
  - 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리
  - 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
  - 배열을 사용해 효율적으로 표현 가능
- 전 이진 트리
  - 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
- 포화 이진 트리
  - 전 이진 트리이면서 완전 이진 트리
- 이진 탐색 트리(BST)
  - 이진 탐색 트리의 노드에 저장된 키는 유일, 부모의 키가 왼쪽 자식보다 크고 오른쪽 자식 노드보다 작다.
  - 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
  - 이진 탐색 트리의 탐색 연산은 O(log n)
  - 이진 탐색 트리는 Skewed Tree(편향 트리)가 될 수 있다. 한 쪽으로만 노드가 추가되는 경우 발생하는 이럴 경우 탐색의 Worst Case는 O(n)이 된다.
- 균형 이진 탐색 트리
  - AVL 트리(스스로 균형 잡는 트리),
  - 레드- 블랙 트리
  - B 트리(모든 리프 노드들이 같은 레벨을 가짐)
  - B+ 트리(모든 리프 노드가 연결리스트 형태)
  - 오른쪽 서브 트리의 높이와 왼쪽 서브 트리의 높이 차이가 1 이하

Heap(힙)

트리 기반 자료구조로 힙 속성을 만족하는 거의 완전한 트리
힙 속성이란 최대힙일 경우 부모 노드는 반드시 자식 노드보다 값이 커야 한다는 법칙같은거.
- Binary Heap(이진 힙)
  - 이진 트리 형태의 힙
  - 완전 이진 트리

Trie

n-차 트리의 변종
각 노드에 문자를 저장하는 자료구조
트리를 아래쪽으로 순회하면 단어 하나 나옴
접두사를 빠르게 찾아보기 위한 흔한 방식으로 모든 언어를 트라이에 저장해놓는 방식이 있다.
유효한 단어 집합을 이용하는 많은 문제들은 트라이를 통해 최적화 가능

MST(최소 신장 트리)

그래프 내의 모든 정점을 포함하는 신장 트리
사이클을 포함하면 안됨
통신 네트워크 구축에 사용
스패닝 트리중에서 사용된 간선들의 가중치 합이 최소인 트리, 도로 건설, 전기 회로, 통신, 배관에 사용, 구현 방법으로는 크루스칼과 프림이 있다.
크루스칼 알고리즘은 greedy를 이용 가장 낮은 가중치를 선택, 사이클을 형성하는 간선은 제외
프림 알고리즘은 시작 정점에서부터 출발하여 단계적으로 확장, 단계별로 만들어진 트리에 인접한 정점들 중에서 최소 간선을 선택