자료구조 정리

2021년 09월 19일

제작기간	2021년 9월 16일 ~ 9월 29일
태그	CS

📚서적소개: C언어로 설명하는 자료구조 프로그래밍
🔖참고: 알고리즘 정리

1. 자료구조를 위한 C 배열과 포인터 이해

배열은 <index, value> 형태의 튜플의 모임으로 표현 가능
배열 원소를 연속하여 저장하면 index에 관계 없이 접근 시간이 동일
dynamic variable은 프로그램 실행도중 필요에 의해 생성, 소멸

2. linear list / ordered list

sequential representation

ordered list의 logical order와 실제 메모리 저장 순서를 일치시키는 것

linked list

nonsequential mapping된 ordered list
node = data field + link field
모든 노드를 순차적으로 접근해 가면서 처리해야하기 때문에 접근 시간이 최악의 경우 O(n)
노드의 링크를 유지해야하기 때문에 메모리 사용량이 늘어남
추가와 삭제가 많은 경우에 용이
singlely linked list
- 직후 노드에 대한 링크만 포함
doublely linked list
- 직전 노드에 대한 링크 또한 포함
- 앞뒤 노드를 탐색해야하는 경우에 용이
circular linked list
- 마지막 노드의 링크가 첫 번쨰 노드를 가리킴
available space list
- 반복되는 malloc과 free 작업으로 인한 처리 시간 증가를 방지하기 위함
- 삭제된 노드들을 재사용하기 위해 별도의 linked list로 구성해 두는 것

+ 응용

sparse matrix (희소 행렬)
- <row num, column num, value> 형태의 Tuple로 구현
- 최소 1/3 이상이 0이어야 메모리 절약이 가능
polynomial 표현
- 각 항의 계수를 차수에 따라 ordered list로 표현할 수 있음

3. Stack

top: 가장 최근에 추가된 원소
LIFO 구조
원소 이동이 발생하지 않기 때문에, sequential하게 구현하는 것이 좋음 (linear stack)
미리 확보한 메모리 용량을 가득 채우면 stack full 상태가 됨
system stack, CPU interrupt, DFS에서 사용

+ 응용

expression 변환
- prefix(전위식), infix(중위식), postfix(후위식) 사이의 변환
recursive fuction 변환 (재귀함수)
- 피보나치, 하노이 타워…

4. Queue

rear: 진입 방향
FIFO 구조
sequential queue
- linear의 경우, rear == N-1를 queue full로 판단
- moving queue는 rear가 우측 끝에 다다랐을 때, 앞의 빈 공간으로 이동하여 공간을 확보함
- circular queue, front == rear인 경우 공집합 혹은 full, 판단을 위한 flag 필요
linked queue
- 추가 연산은 항상 rear, 삭제연산은 항상 front

+ 응용

FIFO 계열의 전산 시스템, 예약 등
palindrome 문제에서 응용 가능

5. 트리와 이진트리

tree

1개 이상의 node들의 유한 집합
root를 제외한 나머지 노드들은 n개의 서로 다른 부분집합(subtree)으로 분할 가능
용어
- sibling ndoes: 부모가 같음
- leaf node (terminal node): 자식이 없음
- descents(모든 하위 노드), ancestors(모든 조상 노드)
- degree(차수), level(링크 개수)
표현
- 노드들의 차수를 미리 선언하고 메모리를 확보하느냐에 따라 가변노드, 고정도느 표현으로 구분함

binary tree

0개 이상의 node들의 유한집합
루트를 제외한 나머지 노드들은 left subtree와 right subtree로 분할 가능
complete binary tree
- 최하위 node를 제외하고 모두 최대개수의 node를 포함
skewed binary tree
- 한쪽 방향의 child node로만 구성됨
strictly binary tree
- leaf node를 제외하고 모두 차수가 2인 이진트리
Knuth binary tree
- strictly가 아닌 binary tree

traversal(순회) 연산

preorder traversal
- root 방문 후, left subtree를 우선적으로 preorder traversal
inorder traversal
- left subtree를 inorder traversal한 후, root 방문 후, right subtree를 inorder traversal
postfix traversal
- left subtree, right subtree 순서로 postfix traversal한 후, root 방문
level order traversal
- level에 따라 왼쪽노드에서 오른쪽 노드로 순차 순회

+ 응용

binary search tree
- root보다 작은 값은 left subtree에 포함되도록 구성하는 binary tree
- 탐색 시간을 절약할 수 있음
- 추가, 삭제 연산을 반복하다보면 skewed binary tree가 될 수도 있음
- binary search tree의 균형을 유지하기 위한 연구들: AVL tree, red-black tree
heap
- complete binary tree 구조
- 각 ndoe의 key가 child보다 같거나 큼
- max heap/min heap
- sequential한 표현이 일반적
m-way search tree
- 최대 m-1개의 키 값, 최대 m개의 서브트리

6. 그래프

graph

1개 이상의 vertex들의 집합과 정점을 연결하는 edge(tuple로 표현)들의 집합
multigraph: 두 정점을 여러 edge로 연결한 그래프
- 이를 simple graph로 나타내기 위해서 dummy vertex를 추가하기도 함
subgraph: 그래프의 일부분
undirected graph: 무방향 그래프
- 반대는 directed graph(digraph)
- directed 경우에는 꺽새로 튜플 표현
null graph: 간선이 없음
complete graph: 간선의 개수가 최대임
weighted graph/network: 가중그래프. cost가 존재
vertex (v, w)
- v, w는 해당 edge에 incident된다고 함
- w는 v의 adjacent vertex임
- isolated vertex: adjacent vertex가 없음
- connected/biconnected: 두 vertex 사이 경로가 1개 존재/2개 이상 존재
- articulation point(연결점): 해당 점이 없으면 G가 2개의 부분그래프로 분리됨
weekly/strongly connected graph: 방향 그래프에서 임의의 두 점에 대해 경로가 한 쪽만 있는 경우/두 경로 모두 있는 경우

표현 방법

인접행렬(adjacency matrix)
- n차 정방행렬로 표현
- 무방향 그래프인 경우 대칭행렬이 됨
- 간선이 적으면 희소행렬이 됨 (메모리 낭비)
인접리스트(adjacency list)
- 연결리스트로 표현
- inverse adjacency list: 해당 점을 종점으로 하는 연결리스트 (방향리스트에 한함)
- 메모리는 아끼지만 많은 처리시간 소요

연산

그래프의 순회(traversal)연산

깊이우선탐색 (depth first search)
- 인접하면서 아직 방문하지 않은 한 정점을 선택
- 선택할 점이 없으면 직전의 점으로 돌아감
- stack으로 관리
너비우선탐색 (breadth first search)
- 인접하며너 아직 방문하지 않은 모든 점을 방문
- queue로 관리

Spanning tree(신장트리)

최소 개수의 edge를 이용해 G의 모든 점들을 연결
항상 n-1개의 edge로 구성
DFS/BFS 신장트리로 구분

이중연결성(biconnectedness) 검사

한 정점에 대한 G의 이중연결성은 아래와 같이 구함
DFS 순회연산 응용
- 순회연산을 통해 DFS 신장 트리 구성
- 해당 트리에 포함되는 간선집합, 비포함되는 간선집합으로 분할
신장트리에서 루트정점이 2개 이상의 subtree를 가지는 경우, 루트정점은 연결점
임의의 정점이 연결점인 경우, 그 정점으로 시작하는 DFS 신장트리에서 루트는 반드시 2개 이상의 subtree로 구성

최소비용신장트리 (Minimum cost spanning tree)

무방향
모든 정점을 포함하면서 사이클은 X
n-1개의 간선

Kruskal
- 간선을 오름차순으로 정리
- 최소의 가중값을 가진 간선을 선택
- 최소의 가중값을 선택하고 사이클이 없는 경우에만 트리에 추가
- n-1개의 경우 종료
Prim (우선순위 우선탐색)
- 임의의 시작점에서 시작
- 최소의 가중값을 가진 간선을 선택해 추가

최단경로문제 (Shortest path)

가중방향그래프 G를 대상
다익스트라 (Dikstra)
- 우선순위 큐를 이용해 구현할 수 있음
- greedy algorithm
Dellman-Ford
- 음의 가중값을 가지고 있을 때도 사용 가능
- k개의 간선들을 포함한 최단경로 정보를 이용함

7. 해시테이블

Hashing

신속한 저장과 탐색을 목적으로 함
각 객체가 가지고 있는 unique한 key값을 이용해 저장위치를 계산
table의 크기와 객체의 크기
1. table의 크기 > 객체의 크기
  - 비효율적
2. table의 크기 = 객체의 크기 (1:1대응)
  - 대응 규칙 설계의 어려움
3. table의 크기 < 객체의 크기
  - 충돌 해결이 필요
hashing: 저장 주소를 계산하는 과정
hash function: 주소계산 규칙
collision: 해당 위치에 다른 원소가 이미 저장되어 있음
synonym: 같은 저장위치로 대응되는 key들

Hash Function

division, multiplication, mid-square method
folding: 주소공간 자릿수 만큼씩 분할하여 대응한 결과를 주소로 결정

Collision Solution

bucket: 해시테이블의 각 블록
slot: 한 키를 저장하는 단위 영역
overflow: 해시테이블에서 버킷을 초과하여 충돌이 발생하는 경우
load factor(적재율): 0에 가까울 수록 메모리 사용율 저하, 1에 가까울 수록 오버플로우 발생률 증가

개방주소법 (open addressing method)
- 해당 주소에 저장할 수 없으면 비어있는 다른 bucket에 저장
- 선형조사, 이차조사, double hashing 방법 등이 있음
폐쇄주소법 (closed addressing method)
- 키 값을 미리 저장된 오버플로우 영역에 저장
- chaining of synonyms를 유지 (연결리스트)

8. 정렬

internal sorting: 메모리에 모두 적재하여 정렬
external sorting: 메모리에 부분적으로 적재하여 정렬

Internal sorting

Selection Sort: 가장 작은 원소를 선택해서 배열의 가장 앞 쪽의 원소와 교환
Bubble/Exchange Sort: 인접한 두 원소를 비교해서 대소에 맞게 교환하는 작업 순차진행
Insertion Sort: 정렬 순서를 고려해서 적절한 위치에 삽입
Shell Sort: 증분값을 이용하여 부분리스트로 나누고, 정렬을 진행. 증분값은 반복될 수록 감소하여 결국 1이 됨
Quick Sort
- 임의의 수를 기준으로 대소비교하여 정렬
- 검사 중, 기준이 되는 수보다 큰 경우와 작은 경우를 만나 작은 수는 좌, 큰 수는 우가 되게 교환
Merge Sort: 2등분된 부분리스트를 정렬하며 병합하는 과정을 가짐
Heap Sort: 히프를 유지하며 정렬하는 방법
Radix Sort: 키 값들을 미리 순서가 정해진 여러 그룹들로 분배할 수 있는 경우에 사용

9. 탐색 (Searching)

Sequential search
- 순서대로 탐색. 최악의 경우, O(n)의 시간이 걸림
Binary search
- 정렬된 리스트에만 사용
- 두 부분리스트로 분할하여, 키를 포함할 가능성이 있는 부분리스트를 선택하는 방식
Index search
- 관리할 데이터의 양이 많은 경우에 사용
- 데이터를 일정크기의 블록단위로 분할된 디스크 공간에 저장
- 각 블록의 시작주소로 접근