-

피보나치 탐색(Fibonacci Search)은 정렬된 배열에서 특정 값을 찾는 데 사용하는 탐색 알고리즘입니다.이 알고리즘은 이진 탐색(Binary Search)와 유사하지만,피보나치 수열을 이용해 비교할 인덱스를 정하는 점에서 차이가 있습니다.피보나치 탐색은 특히 메모리 계층 구조가 있는 시스템에서 효율적으로 동작합니다.  동작 원리 피보나치 수열 생성탐색 범위 내에서 사용할 피보나치 수를 계산합니다.피보나치 수열은 다음과 같은 점화식으로 정의됩니다.( F(0) = 0 )( F(1) = 1 )( F(n) = F(n-1) + F(n-2) ) (n ≥ 2)초기 설정탐색 범위의 크기를 ( N )이라 할 때, ( N )보다 큰 가장 작은 피보나치 수 ( F(k) )를 찾습니다.초기 값 설정( F(m) = F..

지수 탐색(Exponential Search)은 정렬된 배열에서 효율적으로 원하는 값을 찾기 위한 알고리즘 중 하나입니다.지수 탐색은 이진 탐색(Binary Search)을 확장한 것으로,먼저 지수를 사용해 검색 범위를 좁히고,이후 이진 탐색을 사용해 값을 찾습니다.이 방법은 O(log n) 시간 복잡도를 가지며,특히 요소가 배열의 앞쪽에 있을 때 더 빠르게 찾을 수 있습니다. 동작 원리 지수 범위 설정검색하려는 값이 배열에 존재하는 범위를 지수적으로 확장하여 찾습니다.이진 탐색 적용지수로 찾은 범위 내에서 이진 탐색을 수행합니다.#include #include // std::binary_search// 이진 탐색 함수int binarySearch(int arr[], int left, int right..

보간 탐색(Interpolation Search)은 선형적으로 분포된 정렬된 배열에서 특정 값을 찾는 알고리즘입니다.보간 탐색은 이진 탐색과 유사하지만, 이진 탐색이 배열의 중간 요소를 기준으로 검색 범위를 줄이는 반면,보간 탐색은 검색 값이 어디에 있을지 추정하여 더 효율적으로 검색 범위를 줄입니다.이는 이진 탐색보다 평균적인 경우에 더 빠를 수 있지만, 최악의 경우 O(n)이 될 수 있습니다.보간 탐색의 시간 복잡도는 일반적으로 O(log(log(n)))입니다.  동작 원리 배열이 정렬되어 있다는 가정 하에, 찾고자 하는 값의 위치를 추정하여 검색 범위를 줄입니다.보간 공식을 사용하여 위치를 계산합니다'pos = low + ((x - arr[low]) * (high - low) / (arr[high]..

점프 탐색(Jump Search)은 정렬된 배열에서 원하는 값을 찾기 위해 사용되는 알고리즘입니다.이 알고리즘은 배열의 요소를 하나씩 검사하지 않고,일정한 "블록" 단위로 건너뛰며 검사하여 효율적으로 탐색합니다.점프 탐색의 시간 복잡도는 O(√n)이며,이 알고리즘은 이진 탐색(Binary Search)과 비슷한 상황에서 유용하게 사용될 수 있습니다.  동작 원리 배열의 크기를 n이라고 할 때, √n 크기의 블록으로 나눕니다.현재 블록의 마지막 요소가 탐색하려는 값보다 작으면 다음 블록으로 이동합니다.현재 블록의 마지막 요소가 탐색하려는 값보다 크거나 같으면 해당 블록 내에서 선형 탐색을 수행합니다.#include #include int jumpSearch(int arr[], int n, int x) { ..

넓이 우선 탐색(BFS)은 그래프 탐색 알고리즘 중 하나로,시작 정점에서부터 시작하여 인접한 정점들을 먼저 탐색한 후,점차 멀리 있는 정점들을 탐색하는 방식입니다.BFS는 주로 큐(Queue) 자료구조를 이용하여 구현되며,그래프의 모든 정점을 방문하는 데 사용됩니다.  특징 시작 정점에서 가장 가까운 정점부터 탐색합니다.최단 경로를 찾을 때 유용합니다.큐(Queue) 자료구조를 사용하여 구현됩니다.동작 원리 시작 정점을 큐에 삽입하고 방문 표시를 합니다.큐에서 정점을 하나 꺼내어 해당 정점의 모든 인접 정점을 큐에 삽입하고,방문 표시를 합니다.큐가 빌 때까지 2번 과정을 반복합니다.#include #include using namespace std;const int MAX_VERTICES = 6;void..

깊이 우선 탐색(Depth-First Search, DFS)은 그래프 탐색 알고리즘 중 하나로,시작 노드에서 출발하여 한 방향으로 갈 수 있는 끝까지 탐색한 후,다른 방향으로 탐색하는 방식입니다.스택을 사용하여 구현할 수 있으며, 재귀 호출을 통해 쉽게 구현할 수 있습니다.  탐색 방법 설명 시작 노드 선택탐색을 시작할 노드를 선택합니다.노드 방문현재 노드를 방문하고, 방문했음을 표시합니다.인접 노드 탐색방문한 노드와 인접한 노드들을 차례로 방문하지 않은 노드가 있다면,그 노드를 새로운 시작 노드로 선택하여 다시 방문합니다.반복더 이상 방문할 노드가 없을 때까지 2번과 3번 과정을 반복합니다. #include #define MAX 100using namespace std;// 그래프 클래스 정의class..

이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘입니다.이진 탐색은 탐색 범위를 절반으로 줄여가며 값을 찾기 때문에 시간 복잡도가 O(log n)입니다.  원리초기화배열의 시작 인덱스('low')와 끝 인덱스('high')를 설정합니다.중간값 계산중간 인덱스('mid')를 계산합니다.비교 및 이동중간값이 찾고자 하는 값과 같다면 탐색을 종료합니다.중간값이 찾고자 하는 값보다 크다면 'high'를 'mid - 1'로 설정합니다.중간값이 찾고자 하는 값보다 작다면 'low'를 'mid + 1'로 설정합니다.반복값을 찾거나 탐색 범위가 사라질 때까지 2번과 3번 단계를 반복합니다.#include int binarySearch(int arr[], int size, int ..

선형 탐색은 가장 기본적인 탐색 알고리즘 중 하나로,배열이나 리스트의 첫 번째 요소부터 시작하여 차례대로 모든 요소를 탐색하는 방법입니다.원하는 값을 찾을 때까지 각 요소를 순차적으로 비교하며,값을 찾으면 탐색을 종료하고 해당 요소의 인덱스를 반환합니다.만약 끝까지 탐색했음에도 값을 찾지 못하면 보통 -1을 반환하여 값을 찾지 못했음을 알립니다.  특징정렬되지 않은 배열에서도 작동합니다.데이터의 위치에 상관없이 탐색 시간이 일정합니다.구현이 간단하지만, 데이터가 많을 경우 비효율적일 수 있습니다.예제 #include using namespace std;// 선형 탐색 함수int linearSearch(int arr[], int size, int target) { for (int i = 0; i   ..

원형 이중 연결 리스트(Circular Doubly Linked List)는 각 노드가 두 개의 포인터를 가지고,하나는 다음 노드를 가리키고 다른 하나는 이전 노드를 가리킵니다.이 리스트는 마지막 노드가 첫 번째 노드를 가리키고,첫 번째 노드가 마지막 노드를 가리키는 구조를 가지고 있어 리스트의 처음과 끝을 쉽게 순환할 수 있습니다.  #include class Node {public: int data; Node* next; Node* prev; Node(int value) : data(value), next(nullptr), prev(nullptr) {}};class CircularDoublyLinkedList {private: Node* head;public: Circ..

원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키도록 연결된 연결 리스트입니다.이는 리스트의 끝에서 다시 처음으로 순환할 수 있게 하여 특정 유형의 문제에 유용합니다.원형 연결 리스트는 단일 연결 리스트와 달리,끝이 명확하지 않으므로 반복 작업에서 유용할 수 있습니다.  #include struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {}};class CircularLinkedList {private: Node* head;public: CircularLinkedList() : head(nullptr) {} // 노드 추가 void append(int data) { ..