Nagie's DevStory

이진 탐색(Binary Search)은 탐색 범위를 반으로 나누어 원하는 값을 찾아내는 알고리즘이다. 주로 정렬된 배열 또는 리스트에서 사용되며, 원하는 값과 중간 위치의 값을 비교해 탐색 범위를 계속해서 반으로 나누어 가면서 목푯값을 찾아낸다. 분할 정복(divide and conquer) 기법을 기반으로 하며, 각 단계에서 탐색 범위를 반으로 줄여나가기 때문에 효율적인 알고리즘 중 하나이다. template bool binary_search(const std::vector& data, T target) { int lower = 0; int upper = data.size() - 1; while (lower

선형 탐색(Linear Search)은 배열이나 리스트와 같은 자료 구조에서 특정 원소를 찾기 위해 처음부터 끝까지 순차적으로 탐색하는 알고리즘을 말하며, 검색할 요소들이 정렬되어 있지 않은 경우에도 적용할 수 있다. template bool linear_search(const std::vector& data, T target) { for (const T& element : data) { if (element == target) { return true; } } return false; } 특징 1. 순차적 탐색 : 시작부터 끝까지 각 원소를 비교하면서 찾고자 하는 값을 찾을 때까지 진행한다. 2. 시간 복잡도 : 최악의 경우, 탐색하려는 원소가 배열의 맨 끝에 있거나 원소가 존재하지 않는 경우 전체 배..

퀵 정렬(Quick Sort)은 토니 호어가 1960년에 개발한 평균적으로 빠른 속도를 가지는 정렬 알고리즘으로 분할 정복(Divide and Conquer) 방법을 사용하며, 배열을 피벗 기준으로 작은 요소들과 큰 요소들로 나누어 각각을 정렬 후 최종적으로 정렬된 부분을 합치는 방식을 사용한다. template int partition(std::vector& data, int left, int right) { T pivot = data[left]; int i = left + 1; int j = right; while (true) { while (data[i] left) { j--; } if (i < j) { std::swap(data[i], data[j]); } else { break; } } std:..

병합 정렬(Merge Sort)은 1945년 존 폰 노이만이 제안한 분할 정복(Divide and Conquer) 알고리즘의 일종으로, 정렬되지 않은 리스트를 반으로 나눈 후 각 부분을 재귀적으로 정렬하고, 정렬된 부분을 병합하여 전체 리스트를 정렬하는 방식을 취한다. 이 과정은 리스트의 길이가 1이 되거나 비어있을 때까지 반복되며, 안정적이면서 효율적인 정렬 방법으로 널리 사용된다. template void merge(std::vector& data, int left, int mid, int right) { int size = right - left + 1; std::vector buff(size); int i = left, j = mid + 1, k = 0; while (i

삽입 정렬(Insertion Sort)은 현재 위치에서 그 보다 앞(혹은 더 작은 값)의 원소들과 비교하여 자신이 들어갈 위치를 찾아 삽입하는 방식으로 동작하며, 정렬되지 않은 부분의 원소를 하나씩 정렬된 부분으로 삽입하면서 정렬이 완료된다. template void insertion_sort(std::vector& data) { //최악 O(n^2) int n = data.size(); for (int i = 1; i = 0 && data[j] > key) { data[j + 1] = data[j]; j--; } data[j + 1] = key; } } 특징 1. 안정성 : 동일한 키 값을 가진 원소 간..