그래프(Graph) 표현 그래프의 표현 방법에는 인접 행렬, 인접 리스트, 인접 배열이 존재합니다. 인접 행렬(adjacency matrix) 방법 간선 (i, j)가 존재하면 원소(i, j) = 1을 저장하며 그렇지 않으면 원소(i, j) = 0이 됩니다. 정점의 총 개수가 N이라고 할 때 인접 행렬은 N X N 행렬입니다. 무방향 그래프의 경우 대각선 행렬을 중심으로 대칭적이지만 방향 그래프의 경우 반드시 대칭적이지 않고 비대칭일 수도 있습니다. 또한 가중치가 있는 그래프의 경우 원소(i, j)는 1 대신에 가중치를 저장합니다. 인접 리스트(adjacency list) 방법 정점의 총 개수가 N이라고 할 때 각 정점에 인접한 정점들을 N개의 연결리스트로 표현한 방법입니다. i번째 리스트는 정점 i에 ..

그래프 Graph 그래프는 객체 간의 관계를 표현하는 자료구조입니다. 지도에서 지점들의 연결 상태, 도로망, 과목 선후수 관계, 전기회로의 소자 간 연결 상태, 사람들 간의 친분 관계 등을 그래프로 표현할 수 있습니다. 즉, 그래프란 현상이나 사물을 정점(vertex)과 간선(edge)로 표현한 것입니다. 그래프의 정의는 G = (V, E) 로 주어지며 V는 정점 집합, E는 간선 집합입니다. 정점(vertex) 객체를 의미하며 노드라고도 불립니다. V(G) : 그래프 G의 정점들의 집합을 의미합니다. 간선(edge) 정점들간의 관계를 의미하며 링크(link)라고도 불립니다. E(G) : 그래프 G의 간선들의 집합을 의미합니다. G1과 G2는 무방향 그래프, G3는 방향 그래프입니다. 방향성 존재 여부에..

우선순위 큐에 대하여 배워보았으니 이제 우선순위 큐를 어디에 사용하고 어떻게 응용하는 지에 대하여 알아보겠습니다. 힙 정렬(heap sort) 힙 정렬(heap sort)은 히프를 사용하는 정렬 알고리즘입니다. 먼저 정렬할 요소들을 최대 히프에 삽입하고 히프에서 하나씩 요소를 삭제하여 저장하면 정렬이 되는 방식입니다. 힙 정렬이 가장 유용한 경우는 가장 큰 값이 몇 개만 필요한 경우입니다. 힙 정렬 알고리즘 void heap_sort(element a[], int n) { int i; HeapType* h; h = create(); // 히프 생성 init(h); for (i = 0; i < n; i++) { insert_max_heap(h, a[i]); // 최대 히프로 삽입 } for (i = (n ..

우선순위 큐 (priority queue) 우선순위 큐는 우선순위를 가진 항목들을 저장하는 큐입니다. 일반적으로 큐는 선입선출(FIFO)기반의 자료구조로 알려져있는데 우선순위 큐는 우선순위가 높은 데이터가 먼저 나가게 됩니다. (ex. 구급차, 소방차가 다른 차들보다 먼저 나가는 일) 우선순위 큐의 종류에는 최소 우선순위 큐와 최대 우선순위 큐가 있으며 구현방법에는 배열, 연결리스트, 히프(heap)가 있습니다. 우선순위 큐의 구현방법 - 배열 우선 순위큐는 완전 이진 트리이므로 각 노드에 순서대로 번호를 붙일 수 있습니다. 붙여진 번호가 배열의 인덱스인 것입니다. 배열을 이용하여 트리를 구현하는 방법과 동일합니다. 배열을 이용하면 다음과 같은 규칙에 의해서 부모노드와 자식노드를 찾기가 쉽습니다. - 왼..

이진 탐색 트리 이진 트리의 핵심입니다. 탐색 트리는 탐색 작업을 효율적으로 하기 위한 자료구조입니다. 루트 노드를 기준으로 왼쪽 서브 트리의 key값은 루트 노드보다 작고 오른쪽 서브 트리의 key값은 루트 노드보다 큽니다. 따라서 이진 탐색 트리를 중위순회하면 오름차순 정렬이 됩니다. 탐색 연산 주어진 키 값이 루트 노드의 키 값과 같으면 탐색에 성공합니다. 주어진 키 값이 루트 노드의 키 값보다 작으면 왼쪽 서브트리를 탐색합니다. 주어진 키 값이 루트 노드의 키 값보다 크면 오른쪽 서브트리를 탐색합니다. 이진탐색트리에서의 탐색을 구현하는 방법으로는 순환적 방법과 반복적 방법이 있습니다. 순환적인 탐색 함수 TreeNode *search(TreeNode *node, int key) { if ( nod..

NULL 링크에 중위 후속자 (inorder successor)를 저장시켜 놓은 이진 트리입니다. 중위 후속자란 중위 순회의 순서에서 그 다음에 이어질 차례의 노드입니다. 중위 후속자로 인해 순환 호출 없이도 중위 순회가 간편하다는 장점이 있습니다. 스레드 이진 트리 구조체 typedef struct TreeNode { int data; struct TreeNode *left, *right; int is_thread; //만약 오른쪽 링크가 스레드이면 TRUE } TreeNode; 중위 후속자를 찾는 함수 TreeNode *find_successor(TreeNode *p) { // q는 p의 오른쪽 포인터 TreeNode *q = p->right; // 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른..