솔

8.1 Lower Bounds for Searching Only by Comparisons of Keys 이 섹션에서는 키 비교만을 사용하여 배열에서 특정 키를 검색할 때 소모되는 최악의 경우 비교 횟수의 하한을 다룹니다.특히, Binary Search와 Sequential Search의 의사결정 트리(Decision Tree)를 사용하여 검색 과정의 효율성을 분석합니다. 의사결정 트리 (Decision Tree) • 정의:의사결정 트리는 키 를 배열에서 검색하는 과정에서 발생하는 모든 비교를 나타냅니다. • 각 내부 노드는 키 비교를 나타냅니다. • 각 리프 노드는 검색 결과를 나타냅니다 (성공적으로 검색된 위치 또는 실패). • 예시: • Figure 8.1: 정렬된 배열에서 이진 탐색(Binary ..

7.1 Computational Complexity 계산 복잡도란?  • **계산 복잡도(Computational Complexity)**는 특정 문제를 해결할 수 있는 모든 가능한 알고리즘의 효율성을 분석하는 학문이다. • 주로 다음 두 가지를 분석한다:  1. 시간 복잡도(Time Complexity): 알고리즘이 실행되는 데 필요한 시간. 2. 공간 복잡도(Space Complexity): 알고리즘이 사용하는 메모리 양. 여기서 중요한 것은 알고리즘을 개별적으로 분석하는 것이 아니라 문제 자체의 본질적인 복잡도를 분석한다는 점이다.예를 들어, 행렬 곱셈 문제에서는 최선의 알고리즘이라도 Θ(n²) 이상의 시간 복잡도를 가지며,이를 문제의 **하한(Lower Bound)**이라고 한다. 정렬 문제의 계..

큰 수의 곱셈을 분할해서 푸는문제.

1. Write an algorithm that finds the largest number in a list (an array) of n numbers.int fintLargest(std::vector& v){ int largest = v[0]; for(int i=1; i largest) largest = v[i]; }} 2. Write an algorithm that finds the m smallest numbers in a list of n numbers.std::vector findSmallThanM(std::vector& v, int m){ std::sort(v.begin(), v,end()); std::vector result(v.begin(), v.begin()+m); retur..

앞에서 AVL Tree와 RedBlackTree에 대해 알아보았는데요. 이번에는 두 트리를 비교해보겠습니다. https://sol248.tistory.com/61 AVL TreeAVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데sol248.tistory.com https://sol248.tistory.com/64 RedBlackTree (레드-블랙 트리)레드블랙 트리는 스스로 균형을 잡는 이진트리 라는 점에서  앞에서 살펴본 AVL과 비슷합니다.https://sol248.tistory.com/..

버킷 정렬이란?bucket은 바구니를 의미합니다. 말 그래도 버킷 정렬은 바구니에 데이터를 담는 형태를 닮았다 하여 이름 붙여졌습니다.위 그림과 같이 숫자를 카테로리별로 나눠 바구니에 담은 뒤,그 바구니 안을 정렬해주는 방식입니다. 바구니 안을 정렬할 때는 앞에서 배웠던 정렬 방식 중 아무거나 사용하셔도 상관 없습니다. 저는 삽입 정렬을 이용해서 버킷 정렬을 구현해보았습니다.  코드)디버깅, 실행할 때 보기 편하도록 버킷을 출력해주는 함수를 추가해주었습니다.#include #include void Print(std::vector& v) { for (auto& a : v) { std::cout >& v) { for (int i = 0; i & v) { for (int i = 0; i = 0 &&..

https://sol248.tistory.com/50 MergeSort (병합 정렬)이번에는 병합 정렬에 대해 알아보겠습니다. 병합 정렬은 이전에 살펴봤던 Karatsuba algorithm 과 비슷하게, 데이터의 크기를 작게 쪼갠 후합치면서 정렬하는 방식입니다. Karatsuba algorithm이 궁금하sol248.tistory.comhttps://sol248.tistory.com/51 QuickSort (퀵정렬)이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬sol248.tistory.com  앞서 살펴본 퀵정렬과 병합정렬을 비교해보겠습니다. 먼저, 퀵정렬은 난수를 사..

https://sol248.tistory.com/51 QuickSort (퀵정렬)이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬sol248.tistory.com퀵정렬은 중복된 값이 많을수록 느리다는 단점이 있기 때문에 앞에서는 중복된 값이 없다는 가정을 하고 진행했습니다. 이것을 극복할 수 있는 방법이 3-way partitioning 입니다. 앞에서는 pivot 값보다 작은것과 큰 것 두 묶음으로 나누었지만, 여기서는key 값보다 작은 값,key 값과 같은 값,key 값보다 큰 값이렇게 3가지로 나눕니다. 구현 자체는 어렵지 않습니다. 코드) void Quick3way(..

이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬은 pivot 값을 중심으로 배열을 두 개로 나눕니다. 이떄 pivot 값은 어떤 값이 되어도 상관 없습니다. (pivot 값에 따라 시간 복잡도가 달라집니다) -퀵정렬 코드(난수x)int Partition(int* arr, int low, int high, int n) { int pivot = arr[size_t(floorf((high - low) / 2.0f)) + low]; int i = low; int j = high; while (true) { while (arr[i] pivot) j--; if (..

이번에는 병합 정렬에 대해 알아보겠습니다. 병합 정렬은 이전에 살펴봤던 Karatsuba algorithm 과 비슷하게, 데이터의 크기를 작게 쪼갠 후합치면서 정렬하는 방식입니다. Karatsuba algorithm이 궁금하신 분들은 아래 글 참고 부탁드립니다. https://sol248.tistory.com/46 Karatsuba AlgorithmKaratsuba Algorithm은 큰 문제를 잘게 쪼개서 하나씩 하나씩 결합하는 분할&정복 알고리즘 중에 하나입니다. 먼저, 문제를 어떻게 잘게 쪼개는지 살펴보겠습니다. 1234*5678을 예시로 살펴보죠.이런sol248.tistory.com   다음 사진은 병합 정렬의 작동 방식입니다.  작동 방식 자체는 간단하죠? 그럼 이제 코드를 한번 살펴보겠습니다...