[최소 비용 신장 트리에 들어가기에 앞서] 책에서도 나온 말이지만 그래프로 시작했는데 결국 또 트리 이야기가 나왔다. 그런데 사실 트리 역시 그래프의 한 유형이다. 이는 곧 이어서 보게 될 '사이클이 없는 그래프'를 보면 바로 이해가 될 것이다. [사이클을 형성하지 않는 그래프 == 신장 트리] 이 그래프에서 정점 B에서 D로 가는 방법을 나열해보면 다음과 같다. B-A-D / B-C-D / B-A-C-D / B-C-A-D 이처럼 두 개의 정점을 잇는 간선을 순서대로 나열한 것을 가리켜 '경로(Path)'라고 한다. 그리고 동일한 간선을 중복하여 포함하지 않는 경로를 '단순 경로(Simple Path)'라고 한다. B-A-C-B-A-D 와 같은 경로는 B-A를 잇는 간선이 두 번 포함되므로 단순 경로가 ..

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

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 * 작..

[InsertionSort.c] /* * 알고리즘 - 삽입 정렬(Insertion Sort) * 파일명: InsertionSort.c * 파일 버전: 0.1 * 작성자: Sevenshards * 작성 일자: 2023-11-26 * 이전 버전 작성 일자: * 버전 내용: 간단한 삽입 정렬 구현 * 이전 버전 내용: */ #include void InsertionSort(int arr[], int n) { int i, j; int insertData; for (i = 1; i 첫 번째 요소는 데이터가 정렬이 되었다고 보기 때문 { insertData = arr[i]; // 정렬 대상을 별도로 저장 for (j = i - 1; j ..

[SelectionSort.c] /* * 알고리즘 - 선택 정렬(Selection Sort) * 파일명: SelectionSort.c * 파일 버전: 0.1 * 작성자: Sevenshards * 작성 일자: 2023-11-26 * 이전 버전 작성 일자: * 버전 내용: 간단한 선택 정렬 구현 * 이전 버전 내용: */ #include void SelectionSort(int arr[], int n) { int i, j; int maxIdx; // 우선 순위가 가장 높은 인덱스 값 int temp; for (i = 0; i < n - 1; i++) { maxIdx = i; // 인덱스 값은 i로. 맨 처음이라면 0부터 for (j = i + 1; j < n; j++) { if (arr[j] < arr[ma..

[BubbleSort.c] /* * 알고리즘 - 버블 정렬(Bubble Sort) * 파일명: BubbleSort.c * 파일 버전: 0.1 * 작성자: Sevenshards * 작성 일자: 2023-11-26 * 이전 버전 작성 일자: * 버전 내용: 간단한 버블 정렬 구현 * 이전 버전 내용: */ #include void BubbleSort(int arr[], int n) { int i, j; // 반복문에 쓰일 변수 i, j int temp; // 변수 swap에 사용할 임시 변수 for (i = 0; i < n - 1; i++) // 데이터가 n개라면 n-1만큼의 반복을 수행하여 정렬 진행 { for (j = 0; j < (n - i) - 1; j++) // 교환이 이뤄지는 부분. 정렬되어 가면..