Data Structure - 자료구조 정리

6 minute read

알아두면 쓸모있는 자료구조 정리

주제별 정리

연결리스트, 양방향 연결리스트

구조체(struct) 안에 데이터와 다음 구조체를 가리키는 부분이 있는 데이터 구조. 양방향 연결 리스트는 다음 노드 정보 + 이전 노드의 정보까지 저장한다. 추가 메모리 소비가 있지만, 양방향 접근이 가능하기 때문에 안정성이 높다.

장점: 배열에 비해 원소의 삽입, 삭제가 간단하다.
- 배열은 뭐하나 추가하면 하나씩 다 뒤로 밀어야 한다. 삭제는 반대로.
- 얘는 양쪽 노드의 포인터만 바꿔주면 된다.
단점: 특정 인덱스로 즉시 접근이 불가능하고, 다음 노드를 가리키기 위해 추가 메모리 공간이 필요하다.

스택, 큐

스택: 후입선출 - 깊이 우선 탐색 활용
큐: 선입선출 - 너비 우선 탐색 활용

선택정렬, 삽입정렬

선택정렬
- 가장 작은 값을 선택해서 앞으로 보내는 정렬. $O(N^2)$의 시간 복잡도.
- 최소값 찾기 N번, 앞으로 보내기 N번
삽입정렬
- 좌우 값을 비교하며 제자리(왼쪽보다 크고 오른쪽보다 작은)를 찾아 삽입
- 이것도 $O(N^2)$

퀵정렬

분할정복이 핵심

피벗값(하나 선택)을 중심으로 왼쪽에는 작은것들만 오른쪽에는 큰것들만 오도록 정렬
피벗값 제외 왼쪽, 오른쪽 그룹 내에서 재귀적으로 반복
하나의 피벗 값이 정해질 때마다 그 값의 위치를 찾게 됨

계수정렬

각 데이터의 값을 인덱스로 삼아 값의 개수를 배열의 값으로 넣어줌. 많은 메모리를 요구하지만, 빠르게 동작한다. $O(N)$

이진트리 & 이진트리의 구현및 순회

자식노드가 최대 두개인 트리구조. 많은 variation들이 있다.

종류
- Full bt: 리프노드를 제외한 모든 노드가 두개의 자식 노드를 가짐
- Complete bt: 왼쪽부터 노드들을 하나씩 채움
- Height Balanced Tree: 좌우 자식트리 높이가 2 이내인 이진 트리
순회시(탐색)
- 부모 노드(자기 자신)을 먼저 방문 -> 전위 순회
- 왼쪽 자식을 먼저 방문 -> 중위 순회
- 오른쪽 자식을 먼저 방문 -> 후위 순회

우선순위큐

우선순위를 가진 데이터를 저장하는 큐

선형적인 형태가 아닌 트리구조로 보는 것이 합리적
삽입, 삭제, 정렬시 $O(\log N)$의 시간복잡도를 가짐
최대 힙을 이용해 구현

최대힙

부모 노드가 자식 노드보다 큰 값을 가진 이진 트리
그래서 루트노드는 트리안에서 가장 큰 값을 가지게 됨 (최소힙은 반대)
삽입
1. 대상을 완전 이진 트리를 유지할 수 있는 리프 위치에 삽입한 후
2. 부모 노드와 비교하며(대상이 더 크면 자리 바꿈) 상향식으로 최대힙을 재구성
삭제
1. 루트 노드를 삭제(혹은 추출)
2. 가장 마지막 노드를 루트 노드 위치로 옮김
3. 하향식으로 자식 노드들과 비교하며 최대힙 재구성

순차탐색과 이진탐색

순차: 앞에서부터 하나씩 검사
이진: 분할 정복, 탐색범위를 반씩 좁혀가며 탐색. 정렬되어야 사용가능

그래프의 개념과 구현

그래프는 사물을 정점(Vertex)과 간선(Edge)으로 나타낸 개념이다. 간선은 각 정점으로 이동하는 비용(거리)을 나타낼 수 있다.

인접행렬(Adjacency Matrix) 구현

2차원의 배열로 표현한다.
각 정점의 값은 행과 열의 번호가 된다.
비용은 행과 열이 만나는 2차원 배열의 값이 된다.
연결되지 않는 정점 간의 비용(값)은 무한으로 설정한다.
자기 자신과의 거리는 0으로 설정한다.
장단점
- 장: 두 정점간의 비용 확인을 빠르게 할 수 있다. $O(1)$
- 단: 모든 정점의 연결 여부를 저장하므로 공간 효율성이 떨어진다. $O(V^2)$
예시

-	1	2	3
1	0	$\inf$	3
2	$\inf$	0	1
3	3	1	0

인접리스트(adjacency List) 구현

각 정점에 가중치와 다음 연결 노드의 정보를 저장해 표현한다.
장단점
- 장: 연결된 간선의 정보만 저장하므로 공간 효율성이 높다. $O(E)$
- 단: 두 정점이 연결되었는지 확인하는 시간이 인접행렬에 비해 더 걸린다. $O(V)$

방향, 무방향, 가중치, 비가중치

무방향 그래프는 위에서처럼 모든 간선이 방향성을 가지지 않는 그래프를 말한다.비가중치 그래프는 모든 간선의 값이 없는 그래프로, 위의 인접 행렬예시로 표현하면 다음과 같다.

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

방향 가중치 그래프는 모든 간선이 방향과 가중치를 가지는 그래프이며, 인접리스트로 표현하기에 적합하다.
- 각 정점에 다음 연결 노드 정보(방향성)와 가중치를 저장

깊이우선탐색

그래프 구조에서 빠르게 모든 노드를 탐색할 때, 스택구조를 이용해서 탐색하는 방법

시작 노드를 선택한다.
선택한 노드와 연결된 노드 1개를 스택에 집어넣고 방문 처리한다.
방문할 인접 노드가 없는 경우, 스택의 최상단 노드(가장 최근에 들어간 노드)를 추출한다.
2-3번을 반복한다.

너비우선탐색

그래프 구조에서 빠르게 모든 노드를 탐색할 때, 큐를 이용해서 탐색하는 방법

시작노드를 선택한다.
선택한 노드와 연결된 노드를 모두 큐에 삽입하고 방문 처리한다.
인접 노드가 모두 방문된 노드를 큐에서 추출한다.
2-3번을 반복한다.

이진탐색트리

이진 탐색이 항상 동작하도록 구성한 트리 구조
- 왼쪽 노드 값 < 부모 노드 값 < 오른쪽 노드 값이 되도록 트리를 구성한다.
- 최대힙과 비슷하게 삽입/삭제시 이진 탐색이 항상 동작하도록 트리를 재구성한다.

AVL트리

균형이 갖춰진 이진트리를 의미한다. 두 자식의 높이 차인 균형 인수값이 1 이하이면 이진트리라고 한다. AVL트리의 각 노드는 균형 인수를 계산을 위해 자신의 높이 값을 가진다. 새로운 값이 삽입되어 균형이 흐트러진 경우에는 회전을 통해 완전 이진트리에 가까운 형태를 유지토록 한다. 처음 고안한 사람의 이름을 붙여 AVL트리라 한다.

균형이 깨지는 경우는 4가지가 있는데, 앞의 L, R은 부모 노드 기준으로 균형이 깨진 자식 노드 위치를 의미하고, 뒤의 L, R은 그 자식 노드의 어디에 새로운 노드가 삽입되었는지를 말한다.

LL형식 - 왼쪽 자식 노드의 왼쪽에 새 노드가 삽입되어 균형이 깨짐
RR형식 - LL 반대
LR형식 - 왼쪽 자식 노드의 오른쪽 노드에 새 노드 삽입되어 균형이 깨짐
RL형식 - LR 반대

위처럼 균형이 깨진 경우에 회전을 통해 균형을 바로 잡는다.

그림 없으면 이해하기 힘들다.

LL 회전
1. 부모 노드의 왼쪽 자식 위치에 기존 왼쪽 자식의 오른쪽 노드를 연결한다.
2. 기존 부모 노드를 왼쪽 자식의 오른쪽 자식 노드 위치에 연결한다.
RR 회전
1. LL의 반대, 부모 노드의 오른쪽 자식 위치에 기존 오른쪽 자식의 왼쪽 노드를 연결
2. 기존 부모 노드를 오른쪽 자식의 왼쪽 노드 위치에 연결한다.
LR 회전
1. 먼저 RR 회전을 실행한다.
2. 이후 LL 회전을 한다.
RL 회전
1. LR 반대

해시

특정 값을 찾기 위한 키를 만드는데 해시를 이용할 수 있다. 최대한 빠른 속도로 데이터를 관리하기 위한 DB 등에서 사용되며, 메모리 소모가 비교적 크다. 같은 값을 넣으면 항상 같은 값이 나오는 함수의 성질을 이용하서 데이터를 다루는 방식이다. 다만, 서로 다른 값의 키가 중복되는 해시 충돌이 발생하는 경우가 있는데, 이처럼 해시 충돌의 확률이 높을 수록 검색 비용이 증가하게 되고, 이런 확률을 감소시키기 위해 아래와 같은 방법을 사용한다.

키 중복(collision) 방지
- probing(선형, 이차 조사법)
  - 동일키가 나오면 +1 위치에 저장 (선형조사법)
  - 동일키가 나오면 +제곱수 위치에 저장 (이차 조사법)
- chaining
  - 동일키가 나오면 연결리스트를 사용해서 (키-값3-값2-값1 식으로) 연결해서 저장

프림알고리즘

최소신장트리를 구하기 위한 알고리즘

최소신장트리 (Minimum Spanning Tree)

신장 트리(Spanning Tree)란 그래프의 모든 정점을 포함하며, 모든 정점이 연결되어 있으며, 트리의 속성을 만족하는 그래프를 말한다. 최소신장트리는 가능한 신장트리 중 간선들의 가중치 값이 최소인 그래프를 말한다.

프림알고리즘으로 최소신장트리 구하기

그래프의 정점 중 하나를 선택한다
해당 정점에 연결된 간선 중 가중치가 가장 작은 간선을 찾는다.
그 간선과 연결된 정점을 선택한다.
모든 정점이 선택될 때까지 1-3을 반복한다.

간선에 대한 정보는 우선순위큐(최소힙)를 이용해 구현할 수 있다.

다익스트라의 최단경로

프림알고리즘과 비슷하게, 그래프 각 변의 비용의 합이 최소가 되는 트리를 찾는다.

그래프의 정점 중 하나를 선택한다.
최초 정점에서 선택된 정점을 거친 다른 정점까지의 거리를 계산한다.
알고 있던 거리보다(최초에는 INF) 짧은 경우, 갱신한다.
모든 노드를 방문할때까지 선택된 정점에서 가장 가까운 노드로 옮겨서 2-3을 반복한다.

세그먼트트리

자식 노드들의 값의 합이 부모 노드의 값이 되는 트리. 구간합을 선형적으로 계산하는 것보다 효율적으로 계산할 수 있다. 노드 중 하나의 값을 수정할 경우, 연결된 상위 노드의 값도 모두 갱신해야 한다.

인덱스트리

세그먼트트리와 비슷하게 구간합을 구하기 위한 방법이다. 세그먼트 트리보다 메모리 효율성이 좋다.

각 인덱스의 마지막 비트값이 인덱스가 저장하고 있는 값의 개수를 의미한다.
- 1 -> 1개 저장, 2 -> (1-2)2개 저장, 3 -> 1개 저장, 4 -> (1-4) 4개저장, …
- 따라서 각 인덱스의 마지막 비트값을 구해야한다.
  - a & -a (이진수)를 하면 마지막 비트값이 나온다
1부터 N까지의 구간합
- N부터 시작해서 마지막 비트만큼 구간을 앞으로 이동하며 합을 구한다.
- 13 (1개 저장) -> 12 (4개저장) -> 8 (8개저장)
- 인덱스 트리를 수정할때는 세그먼트트리와 같이 해당 인덱스와 함께 마지막 비트만큼 뒤로 이동하며 수정해줘야한다.

KMP 문자열매칭

접두사와 접미사를 이용해 빠르게 문자열 매칭을 수행한다. lps배열이라는 이름으로 각 인덱스마다 접두사와 접미사의 일치하는 개수를 표로 만든 것을 사용한다.

길이	문자열	최대일치길이
1	a	0
2	ab	0
3	aba	1
4	abac	0
5	abacd	0
6	abacda	1
7	abacdab	2

lps를 이용해서 대상 문자열에서 pattern을 비교하다가 불일치가 발생한 경우, 단순 문자열처럼 한칸만 이동해서 처음부터 비교하는 것이 아니라, 접두사가 일치하는 부분으로 건너뛰어서 과정을 단축시킬 수 있다.

라빈 카프 문자열 매칭

특정 문자열에 대한 해시 값을 구한다. 충돌이 있을 수 있다.
각 문자의 아스키 코드 값에 2의 제곱 수를 차례대로 곱해서 더함
- $a * 2^6 + b * 2^5 + … + g * 2^0$
패턴을 문자열에서 찾기 위해서는 반복작업을 하는데, 문자열은 이어져있다는 특징을 사용해서 빠르게 계산이 가능하다
- $\text{다음 해시값} = 2 * (\text{현재 해시값} - \text{맨 앞 문자 값}) + \text{새 문자 값}$
해시 값이 같은 경우(충돌시)에만 문자열을 재검사한다.
- 재검사: 실제 문자열 하나씩 비교