99코딩

그래프(Graph)

요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다.

그래프의 구성

정점(Vertex)

여러 가지 특성을 가질 수 있는 객체, 노드(Node)라고도 부른다.

간선(Edge)

이러한 객체 정점들 간의 관계를 의미, 링크(Link)라고도 부른다.

그래프의 종류

무방향 그래프(Undirected Graph)

간선에 방향이 표시되지 않는 그래프

방향 그래프(Directed Graph)

간선에 방향성이 존재하는 그래프

가중치 그래프(Weighted Graph)

간선에 비용이나 가중치가 할당된 그래프

부분 그래프(Subgraph)

부분 집합으로 이루어진 그래프

그래프의 용어

인접 정점(Adjacent Vertex)

정점의 차수(Degree)

경로(Path)

경로의 길이

단순경로(Simple Path)
사이클(Cycle)

연결 그래프(Connected Graph)

비연결 그래프(Unconnected Graph)

트리(Tree)

완전 그래프(Complete Graph)

그래프의 추상 자료형

데이터

정점의 집합과 간선의 집합

연산

init(): 초기화

isEmpty(): 그래프가 비어있는지 확인

insertVertex(): 정점 삽입

insertEdge(): 간선 삽입

deleteVertex(): 정점 삭제

deleteEdge(): 간선 삭제

adjacent(v): 정점 v에 인접한 모든 정점의 집합을 반환

그래프의 구현 방법

인접 행렬을 통한 그래프의 구현

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX 256

typedef char VertexData;
int adj[MAX_VERTEX][MAX_VERTEX];
int vsize;
VertexData vdata[MAX_VERTEX];

int isEmpty() { return vsize == 0; }
int isFull() { return vsize >= MAX_VERTEX; }

void init() {
	vsize = 0;
	for (int i = 0; i < MAX_VERTEX; i++) {
		for (int j = 0; j < MAX_VERTEX; j++) {
			adj[i][j] = 0;
		}
	}
}

void insert(VertexData data) {
	if (isFull())
		printf("그래프가 가득차있습니다.\n");
	else
		vdata[vsize++] = data;
}

void insert_DirectionalEdge(int u, int v, int value) {
	adj[u][v] = value;
}

void insert_UnDirectionalEdge(int u, int v, int value) {
	adj[u][v] = adj[v][u] = value;
}

삭제 추가 예정

인접 리스트를 통한 그래프의 구현

그래프의 탐색

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

시작 정점으로부터 임의의 인접한 정점으로 최대한 깊숙히 탐색하고 다시 되돌아가며 방문하지 않은 인접한 정점으로 탐색하는 순회 방법이다.

시작 정점에서 임의의 인접한 정점으로 탐색을 진행하며 방문한 정점은 방문되었다는 표시를 남기고 아직 방문하지 않은 인접한 정점으로 탐색을 계속한다. 만약 방문하지 않은 인접한 정점이 없다면 가장 마지막에 남았던 정점으로 돌아가고 이를 시작 정점까지 반복한다.

void DFS(int v) {
	visited[v] = 1;
	for (int i = 0; i < vsize; i++) {
		if (adj[v][i] != 0 && visited[i] == 0)
			DFS(i); 
	}
}

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

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

시작 정점의 인접 정점들을 방문하며 저장하고 더 이상 인접 정점이 없을 시 저장된 정점을 삽입된 순서대로 꺼내어 그 정점과 인접한 정점들을 차례대로 방문하는 것을 반복한다.

void BFS(int v) {
	visited[v] = 1;
	init_queue();
	enqueue(v);
	while (!isEmpty()) {
		v = dequeue();
		for (int i = 0; i < vsize; i++) {
			if (adj[v][i] != 0 && visited[i] == 0) {
				visited[i] = 1;
				enqueue(i);
			}
		}
	}
}

이진탐색트리(Binary Search Tree)

효율적인 탐색을 위한 이진트리 기반의 자료구조이다.

이진탐색트리의 특징

 - 모든 트리는 유일한 키를 갖는다.

 - 왼쪽 서브 트리 키들은 루트 키보다 작다.

 - 오른쪽 서브 트리의 키들은 루트의 키보다 크다.

 - 왼쪽과 오른쪽 서브 트리도 이진탐색트리이다.

이진탐색트리의 추상자료형

연산

init(): 초기화

insert(): 새로운 원소 추가

delete(): 기존 원소 삭제

search(): 탐색

이진탐색트리의 연산

이진탐색트리의 탐색

키 값으로 key를 가지는 노드를 탐색하려 할 때 key와 루트 노드의 키값을 비교하며 결과는 아래 세 가지 중 하나다.

key가 루트 노드의 키값과 같으면 루트 노드가 찾는 노드이므로 탐색은 성공으로 끝난다.

key가 루트 노드의 키값보다 작으면 찾는 노드는 왼쪽 서브트리에 있으므로 루트의 왼쪽 자식을 기준으로 탐색을 다시 수행한다.

key가 루트 노드의 키값보다 크면 찾는 노드는 오른쪽 서브트리에 있으므로 루트의 오른쪽 자식을 기준으로 탐색을 다시 수행한다.

이진탐색트리의 삽입

이진탐색트리에서는 같은 키 값을 갖는 노드가 없어야하고 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치가 되기 때문에 먼저 탐색을 수행해야한다. 

이진탐색트리의 삭제

탐색(Search)

테이블(Table)에서 원하는 탐색키(Search Key)를 가진 레코드(Record)를 찾는 작업

맵(Map)/사전(Dictionary)

자료를 저장하고 탐색키를 이용해 원하는 자료를 빠르게 찾을 수 있도록하는 탐색을 위한 자료구조

엔트리(Entry)라 칭해지는 키(Key) - 값(Value)쌍의 집합으로 이루어져 있으며 중복을 허용하지 않는다.

Map의 추상자료형

데이터

엔트리의 집합

연산

search(key): key를 가진 엔트리를 찾아 리턴

insert(entry): 엔트리를 맵에 삽입

delete(key): key를 가진 엔트리를 삭제

순차 탐색(Sequential Search)

데이터 배열의 처음부터 끝까지 하나씩 검사하여 원하는 데이터를 찾는 방법

정렬되지 않은 배열에서도 탐색키를 찾을 수 있으나 비효율적인 방법이다.

시간 복잡도: O(n)

이진 탐색(Binary Search)

데이터 배열의 중앙에 있는 값을 조사해서 찾고자 하는 항목이 왼쪽에 있는지 오른쪽에 있는지 판단하고 탐색 범위를 반으로 줄이는 것을 반복하여 데이터를 찾는 방법

비교를 수행할 때마다 탐색 범위가 절반으로 줄어들어 매우 효율적이나 반드시 데이터가 정렬되어 있어야한다.

시간 복잡도: O(logn)

색인 순차 탐색(Indexed Sequential Search)

인덱스 테이블을 사용하여 탐색의 효율을 높이는 방법

보간 탐색(Interpolation Search)

탐색키가 존재할 위치를 예측하여 탐색하는 방법

우선순위 큐(Priority Queue)

선입선출(FIFO)인 큐와 달리 모든 데이터가 우선순위를 가지고, 들어온 순서와 관계없이 우선순위가 높은 데이터가 먼저 출력되는 자료구조이며 삭제 연산에서 어떤 요소가 먼저 삭제되느냐에 따라 최소 우선순위 큐, 최대 우선순위 큐로 나누어진다.

최대/최소 우선순위 큐의 추상자료형

데이터

우선순위를 가진 요소들의 집합

연산

init(): 초기화

insert(): 항목 추가

delete(): 가장 우선순위가 높은/낮은 요소를 삭제 및 반환

find(): 가장 우선순위가 높은/낮은 요소를 반환

isEmpty(): 우선순위 큐가 비어있는지 확인

isFull(): 우선순위 큐가 가득찼는지 확인

우선순위 큐의 구현 방법

 - 배열을 통한 구현

 - 연결 리스트를 통한 구현

 - 힙을 통한 구현

힙(Heap)

완전이진트리이며 여러 개의 값들 중에서 가장 큰/작은 값을 빠르게 찾을 수 있도록 만들어진 자료구조이다.

힙의 특징

 - 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작은 이진트리이다.

 - 중복된 값을 허용한다.

 - 주로 배열을 기반으로 구현한다.

 - 프로그램의 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스는 사용하지 않는다.

힙의 종류

최대 힙(Max Heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리

최소 힙(Min Haep)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

힙의 연산

힙의  삽입

힙은 삽입 시 새로운 노드를 힙의 마지막 노드의 다음 위치에 삽입한다. 하지만 이것만 하면 힙의 성질이 만족되지 않으므로 부모 노드와 비교 및 교환을 통해 힙의 성질을 만족시켜 주는 업 힙(Up-Heap)이라는 과정이 필요하다.

힙의 삭제

힙에서의 삭제 연산은 루트 노드를 삭제하는 것이며 최대 힙의 경우 루트가 최댓값이므로 루트 노드를 삭제 후 힙 트리를 재구성하는 과정이 필요하다. 이 때 말단을 루트로 올려 순차적으로 비교 및 교환을 하는 다운 힙(Down-Heap)이라는 과정을 사용한다.

정렬(Sotring)

 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것으로 순서에는 오름차순(Ascending Order)과

내림차순(Descending Order)이 있다.

 데이터를 정렬해야 하는 이유는 탐색의 효율성을 위해서이다.

레코드(Record)

정렬 시켜야 할 대상, 즉 데이터

키(Key)

특정한 레코드를 식별해주는 역할을 하는 필드

정렬 알고리즘의 분류

정렬이 수행되는 장소에 따라 내부 정렬과 외부 정렬로 구분된다.

정렬 장소에 따른 분류

내부 정렬(Internal Sorting)

정렬하기 전에 모든 데이터가 메인 메모리에 올라와 있는 정렬

외부 정렬(External Sorting)

외부 기억 장치에 대부분의 데이터가 있고 일부만 메모리에 올려놓은 상태에서 정렬을 수행하는 정렬, 대용량 자료의 정렬에 적합

구현 복잡도와 효율성에 따른 분류

단순하나 비효율적인 정렬: 삽입 정렬, 선택 정렬, 버블 정렬 등복잡하나 효율적인 정렬: 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬 등

정렬의 종류

선택 정렬(Selection Sort)

전체 숫자들 중 가장 작은 숫자를 반복해서 선택하여 앞으로 옮기는 방법을 사용하는 정렬 알고리즘

시간 복잡도: O(n^2)

삽입 정렬(Insertion Sort)

정렬이 안 된 부분에서 하나를 뽑아 정렬된 부분의 적절한 위치에 삽입하는 과정을 반복하는 정렬 알고리즘

시간 복잡도: O(n^2)

버블 정렬(Bubble Sort)

인접한 두 개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환하는 비교-교환 방식의 정렬 알고리즘

시간 복잡도: O(n^2)

트리(Tree)

계층적 관계를 표현하는 자료구조이다.

트리의 활용

 - 기업 조직도

 - DBMS

 - 디렉터리 구조

트리 관련 용어

노드(Node): 트리의 구성요소

간선(Edge): 노드와 노드를 연결하는 연결선

루트 노드(Root Node): 트리 구조에서 최상위에 존재하는 노드

단말 노드(Terminal Node): 아래로 또 다른 노드가 연결되어 있지 않은 노드

내부 노드(Internal Node): 단말 노드를 제외한 모든 노드

트리의 종류

이진트리(Binary Tree): 모든 노드가 최대 2개의 서브 노드를 가지는 트리

서브트리(Sub Tree): 기존 트리에서 하위의 트리구조

포화 이진 트리(Full Binary Tree): 트리의 각 레벨에 노드가 가득 차있는 이진트리

완전 이진 트리(Complete Binary Tree): 트리의 마지막 레벨을 제외한 모든 레벨이 가득 차있는 이진트리

이진 탐색 트리(Binary Search Tree):  효율적인 탐색을 위한 이진트리 기반의 자료구조

이진 트리의 추상 자료형

데이터

연산

init(): 초기화

isEmpty(): 비어있는지 확인

createTree(): 이진 트리 생성

getRoot(): 이진 트리의 루트 노드 반환

getCount(): 이진트리의 노드 개수 반환

getLeafCount(): 이친트리의 단말 노드 개수 반환

getHeight(): 이진 트리의 높이 반환

덱(Deque: double-ended queue)

큐의 front와 rear 모두에서 삽입과 삭제가 가능한 큐이다.

덱의 특징

 - front와 rear에서 모두 삽입과 삭제가 가능하나 중간에 삽입하거나 삭제하는 것은 허용하지 않는다.

덱의 추상 자료형

데이터

연산

init(): 덱의 초기화

add_front(): front에 요소 삽입

delete_front(): front에서 요소 삭제 및 반환

get_front(): front의 요소 반환

add_rear(): rear에 요소 삽입

delete_rear(): rear에서 요소 삭제 및 반환

get_rear(): rear에 요소 반환

isFull(): 덱이 가득찼는지 확인

isEmpty(): 덱이 비어있는지 확인

size(): 요소의 개수 반환

큐(Queue)

스택과 달리 선입선출의 구조를 가지는 자료구조이다.

큐의 특징

 - 먼저 집어 넣은 데이터가 먼저 나오는 선입선출(FIFO: First In First Out)의 구조를 가진다.

 - front 부분에서 삭제 연산, rear 부분에서 삽입 연산이 이루어진다.

선형 큐와 원형 큐

 - 선형 큐: 1차원 배열로 구성된 큐. front는 큐의 첫 번째 요소를 가리키고 rear는 큐의 마지막 요소를 가리킨다.

 - 원형 큐: 선형 큐의 문제점을 보완하기 위한 자료구조. front와 rear의 값이 배열의 끝에 도달하면 다음에 증가되는 값은 0이 된다.

큐의 활용

 - 먼저 들어온 순서대로 처리되어야 하는 작업 등 광범위하게 사용

 - 속도나 시간의 차이를 극복하기 위한 임시 기억 장치로 사용 = 버퍼(buffer)

큐의 추상 자료형

데이터

연산

init(): 큐의 초기화

isEmpty(): 큐가 비어있는지 확인

isFull(): 큐가 가득찾는지 확인

Enqueue(): 큐에 데이터를 저장

Dequeue(): 큐의 마지막 원소 삭제

Peek(): 저장 순서가 가장 앞선 데이터 반환 

size(): 요소의 개수 반환

c에서 연결 리스트를 기반으로 한 큐의 구현입니다.

#include <stdio.h>
#include <stdlib.h>

typedef int Data;

typedef struct LinkedNode {
	Data data;
	struct LinkedNode* link;
} Node;

Node* front = NULL;
Node* rear = NULL;

void init() {
	front = NULL;
	rear = NULL;
}

int isEmpty() {
	return front == NULL;
}

void Enqueue(Data data) {
	Node* p = (Node*)malloc(sizeof(Node));
	p->data = data;
	p->link = NULL;
	if (isEmpty()) front = rear = p;
	else {
		rear->link = p;
		rear = p;
	}
}

int Dequeue() {
	Node* p;
	Data data;

	p = front;
	data = p->data;
	front = front->link;

	if (front == NULL) rear = NULL;

	free(p);

	return data;
}

int peek() {
	return front->data;
}

int size() {
	Node* p;
	int count = 0;
	for (p = front; p != NULL; p = p->link) count++;

	return count;
}

int main() {
	init();
	printf("isEmpty : %d\n\n", isEmpty());

	for (int i = 0; i < 5; i++) {
		Enqueue(i);
		printf("Enqueue : %d\n", i);
	}

	printf("\nisEmpty : %d\n", isEmpty());
	
	printf("\nsize : %d\n", size());
	printf("peek : %d\n\n", peek());

	for (int i = 0; i < 2; i++) {
		printf("Dequeue : %d\n", Dequeue());
	}

	printf("\nsize : %d\n", size());
	printf("peek : %d\n", peek());

	return 0;
}