[그래프의 탐색에 들어가기에 앞서] 연결 리스트나 배열과 같은 선형 자료구조에서는 탐색해야 할 방향이 정해져있다. 그래서 탐색과 조회를 진행하는 것이 어렵지 않았다. 트리와 같은 비선형 자료구조는 노드의 연결 방향이 일정하지 않기 때문에 탐색을 진행하는 것이 비교적 어렵다. 그렇지만 이진 탐색 트리는 노드가 연결되는 규칙이 있었기 때문에 비교적 간단한 편이었다. 말 그대로 '탐색'을 고려해서 만들어진 트리이기 때문이다. 그런데 그래프에서의 탐색은 어떻게 해야할까? 지금까지 학습했던 자료구조들 중에서 탐색 과정이 꽤 복잡한 편이다. 적어도 연결 리스트나 배열같은 선형 자료구조도 그렇고, 이진 탐색 트리도 그랬듯 '틀'이 있었다. 정형화된 구조가 있었기 때문에 탐색을 어떻게 할 것인가를 정의할 수 있었지만 ..

[그래프에 들어가기에 앞서] 그래프 역시 자료구조이며, 비선형 자료구조에 해당한다. 그리고 트리 때와도 마찬가지로 데이터의 저장보다는 '표현'을 하는데 중점적이다. 실제로 그래프라는 자료구조를 배우게 되면 그래프보다는 그래프와 관련된 알고리즘들을 더 많이 보게 된다. 이는 자료구조에서 저장소의 측면보다는 하나의 '표현 방법'으로 더 많이 사용된다는 것을 의미한다고 볼 수 있다. 그래서 '그래프 자료구조'라는 표현보다는 '그래프 알고리즘'이라는 용어가 더 많이 쓰이게 되고 실제로도 그렇다. [그래프의 이해와 종류] 위의 문제는 '쾨니히스베르크의 다리 문제'라는 유명한 문제다. 그리고 이 문제를 풀기 위해서 오일러라는 수학자에 의해 '그래프 이론'이 사용되었다고 한다. 위의 그림을 그래프로 만들면 다음과 같..

[테이블(Table)의 이해] 이전에 공부했던 이진 탐색 트리와 AVL 트리는 탐색과 관련해서 굉장히 좋은 성능을 보였다. 이 둘은 탐색 키와의 비교 과정을 거치면서 찾는 대상에 가까워지는 방식이다. 그런데 원하는 데이터를 ‘단번에’ 찾아내는 방식이라고는 볼 수 없다. 상황에 따라서는 위의 두 자료구조의 성능은 적합하지 않을 수도 있다. 이런 상황에서 사용할 수 있는 자료구조가 테이블(Table)이다. 이진 탐색 트리와 AVL 트리는 탐색 연산이 $O(log_2n)$만큼의 시간 복잡도를 가진다. 그런데 테이블 자료구조에서 탐색 연산은 $O(1)$의 시간 복잡도를 보인다. 왜 그런지는 테이블의 탐색 원리를 알면 바로 이해가 된다. 위와 같은 ‘표’는 ‘테이블’ 자료구조라고 볼 수 있다. 물론, 모든 표가 ..

[이진 탐색 트리의 문제점과 AVL 트리] 이진 탐색 트리의 탐색 연산은 $O(log_2n)$의 시간 복잡도를 가진다. 이는 이진 트리가 가지는 특징이며 트리의 높이가 하나씩 늘어날수록 추가되는 노드의 수가 2배 증가하기 때문이다. 그런데 이진 탐색 트리는 균형이 맞지 않을수록 $O(n)$에 가까운 시간 복잡도를 가지게 된다. 이를테면 1부터 5까지 순서대로 이진 탐색 트리에 삽입한다고 가정하자. 그러면 1이 루트노드가 되고 오른쪽으로만 길게 쭉 늘어진 이진 탐색 트리가 된다. 이는 선형 자료구조와 다를 바가 없는 모양이 된다. 저장 순서를 조금만 바꿔서 3을 먼저 저장하면 균형이 괜찮게 잡히게 된다. 저장 순서만 바뀌어도 탐색의 성능에 큰 차이를 보이는 것이 이진 탐색 트리의 단점이다. 그리고 이와 같..

https://sevenshards.tistory.com/7 [자료구조, C] 양방향 연결 리스트 기반 이진 트리 구현 [BinaryTree.h] /* * 비선형 자료구조 - 연결 리스트 기반 이진 트리 * 파일명: BinaryTree.h * 파일 버전: 0.2 * 작성자: Sevenshards * 작성 일자: 2023-11-23 * 이전 버전 작성 일자: 2023-11-23 * 버전 내용: 전위, 중위 sevenshards.tistory.com 기존에 구현했던 이진 트리를 이용하되, 추가된 함수들이 있으므로 코드를 추가로 수록. [BinaryTree.h] /* * 비선형 자료구조 - 연결 리스트 기반 이진 트리 * 파일명: BinaryTree.h * 파일 버전: 0.3 * 작성자: Sevenshards..

https://sevenshards.tistory.com/22 [알고리즘, C] 이진 탐색(Binary Search) 구현 [BinarySearch.c] /* * 알고리즘 - 이진 탐색(Binary Search) * 파일명: RecursiveBinarySearch.c * 파일 버전: 0.1 * 작성자: Sevenshards * 작성 일자: 2023-11-27 * 이전 버전 작성 일자: * 버전 내용: 재귀적으로 구성한 이 sevenshards.tistory.com 기존의 이진 탐색 구현에서 약간의 변경만 하면 된다. [InterpolationSearch.c] /* * 알고리즘 - 보간 탐색(Interpolation Search) * 파일명: InterpolSearch.c * 파일 버전: 0.1 * 작성자..

[BinarySearch.c] /* * 알고리즘 - 이진 탐색(Binary Search) * 파일명: RecursiveBinarySearch.c * 파일 버전: 0.1 * 작성자: Sevenshards * 작성 일자: 2023-11-27 * 이전 버전 작성 일자: * 버전 내용: 재귀적으로 구성한 이진 탐색 알고리즘 구현 * 이전 버전 내용: */ #define _CRT_SECURE_NO_WARNINGS #include int RecursiveBinarySearch(int arr[], int first, int last, int target) { int mid; // first보다 last가 커지는 경우 = 값을 찾지 못한 경우 - 재귀의 탈출 조건 첫 번째. if (first > last) return..

[QuickSort.c] /* * 알고리즘 - 퀵 정렬(Quick Sort) * 파일명: QuickSort.c * 파일 버전: 0.1 * 작성자: Sevenshards * 작성 일자: 2023-11-26 * 이전 버전 작성 일자: * 버전 내용: 간단한 퀵 정렬 구현 * 이전 버전 내용: */ #include // 데이터 이동(교환)에 사용 void Swap(int arr[], int idx1, int idx2) { int temp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = temp; } // 피벗의 중간값을 구하기 위해 정의한 함수 int MedianOfThree(int arr[], int left, int right) { // 배열로 가장 첫 번째 인덱스, ..

[MergeSort.c] /* * 알고리즘 - 병합 정렬(Merge Sort) * 파일명: MergeSort.c * 파일 버전: 0.1 * 작성자: Sevenshards * 작성 일자: 2023-11-26 * 이전 버전 작성 일자: * 버전 내용: 간단한 병합 정렬 구현 * 이전 버전 내용: */ #include #include // 병합 과정 void MergeTwoArea(int arr[], int left, int mid, int right) { int front_Idx = left; // 첫 번째 인덱스(가장 왼쪽) int rear_Idx = mid + 1; // mid(중간)의 바로 다음 -> 오른쪽의 맨 첫 번째 인덱스 int i; int* sortArr = (int*)malloc(sizeof..

https://sevenshards.tistory.com/9 [자료구조, C] 배열 기반의 힙(Heap) 구현 [Heap.h] /* * 비선형 자료구조 - 배열 기반의 힙(Heap) * 파일명: Heap.h * 파일 버전: 0.2 * 작성자: Sevenshards * 작성 일자: 2023-11-24 * 이전 버전 작성 일자: 2023-11-24 * 버전 내용: 우선 순위 판단 기준을 힙에 sevenshards.tistory.com 이전에 작성했던 힙을 이용하여 정렬을 수행. 그래서 기존에 작성했던 Heap.h, Heap.c를 이용하였다. [HeapSort.c] /* * 알고리즘 - 힙 정렬(Heap Sort) * 파일명: HeapSort.c * 파일 버전: 0.1 * 작성자: Sevenshards * 작..