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

[테이블(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..