솔

순차 탐색(sequential search) 혹은 선형 탐색(linear search)라고도 하는 탐색에 대해 알아봅시다. 순차 탐색은 말 그대로 앞에서부터 순차적으로 데이터를 찾는 탐색 방법입니다.  코드)#include #include int SequentialSearch(std::vector v, int target) { int N = v.size(); for (int i = 0; i v1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; std::cout  이렇게, 앞에서부터 하나씩 찾아야 하는 값과 비교하며 나아갑니다.찾는 값을 찾은 경우, 바로 그 위치를 반환합니다.   이번에는, 이진 탐색에 대해 알아보겠습니다.이진 탐색이란, 데이터를 두 조각으로 나누어서 탐색하는 것입니..

마스터 정리의 개념 앞에서 정렬이나 탐색 등을 배우며 시간 복잡도에 대해 이야기한 적이 있었죠.  마스터 정리는 big-O 를 손쉽게 구할 수 있는 정리입니다. 마스터 정리란 어떤 것인지 한번 살펴보죠. 여기서a는 나누어지는 문제의 개수를 의미하고 b는 나누어지는 문제의 크기를 의미합니다.f(n)은 나누고 나서 부가적인 과정을 의미합니다.위 식에서 알 수 있는 것은, a*T(n/b)와 f(n)중 차수가 더 큰 것이 시간 복잡도의 결과로 나타난다는 것을 볼 수 있습니다. 차수가 크면 클수록 숫자가 커질 때의 증가폭이 더 크기 때문이겠죠.  위의 식을 좀 더 정리하면 아래의 식으로 간단하게 나타낼 수도 있습니다. 마스터 정리를 이용한다면 점화식을 통하지 않더라도 바로 시간 복잡도를 구할 수 있겠죠. 공식을 ..

점근 표기법이라고 하면 와닿지 않아도 아마 시간 복잡도 혹은 O(n) 이라면 익숙하실 것 같습니다.  점근 표기법에 대해 알아봅시다.  -점근 표기법의 종류𝜪빅오 (Big-Oh)Upper Bound (상한)𝜴빅오메가 (Big-Omega)Lower Bound (하한)𝜭세타 (Theta)Tight Bound (딱 맞는)  -빅오 표기법빅오 표기법은 최악의 경우(상한)을 나타내는 표기법입니다. 이떄 상한이라는 말의 의미는, 아무리 느려도 빅오 표기법으로 표현한 것보다는 빠르다는 것입니다. 보통 어떤 알고리즘의 실행 시간이 주어졌을 때 가장 높은 차수를 사용합니다.  -빅오메가 표기법빅오메가 표기법은 최선의 경우(하한)을 나타내는 표기법입니다. 하한이라는 말의 의미는 아무리 느려도 빅 오메가로 표현한 것보..

Karatsuba Algorithm은 큰 문제를 잘게 쪼개서 하나씩 하나씩 결합하는 분할&정복 알고리즘 중에 하나입니다. 먼저, 문제를 어떻게 잘게 쪼개는지 살펴보겠습니다. 1234*5678을 예시로 살펴보죠.이런 식으로 곱해야 하는 수가 한자리 수가 될 때까지 위와 같은 방법으로 분할시킵니다. 그럼 합칠 때는 어떻게 해야할까요? 위의 과정을 볼 때, 어떤 두 수의 곱셈을 3개의 부분으로 분할시키고 있습니다. 가장 왼쪽에 위치하는 어떤 수들의 앞부분끼리 곱하고 있는 부분. (이를 a라 칭하겠습니다)중간에 위치한 각 수를 분할한 값끼리 더하고 곱셈하는 부분. (이를 b라 칭하겠습니다)가장 오른쪽에 위치한 어떤 수들의 뒷부분들끼리 곱하고 있는 부분. (이를 c라 칭하겠습니다) 원래의 식 1234*5678을 ..

문자열을 n번 ,m번 입력받아서 겹치는 문자열과 그 개수를 출력하는 문제입니다. 단순하게 문자열을 입력받아서 하나하나씩 비교하게 되면 시간이 너무 오래걸려 시간 초과가 날 것입니다. 그렇다면 어떻게 해야할까요?? 해시를 기반으로 하는 탐색을 이용하면 됩니다. 해시는 고유값을 가지기에  데이터의 삽입, 삭제, 탐색 모두 평균적으로 O(1) 입니다. 이번에는 unordered_set 을 이용해보겠습니다. #include #include #include #include #include using namespace std;int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int n = 0, m = 0; cin >> n >> m; unordere..

COMPUTER ORGANIZATION AND DESIGN RISC-V EDITIONTHE HARDWARE SOFTWARE INTERFACE DAVID A. PATTERSON & JOHN L. HENNESSY 컴퓨터구조 과목에서 이 책을 사용한다고 하여 공부를 시작해보겠습니다.

이진 탐색이란, 정렬되어있는 데이터가 주어졌을 떄 사용 가능한 정렬 방식입니다. 이러한 배열이 주어졌을 때, 7이라는 숫자를 이진 탐색으로 찾는 과정을 살펴봅시다.가장 첫번쨰 인덱스 (0번) 과 가장 마지막 인덱스(9번)의 평균 4 ((0+9)/2) 번 인덱스를 봅니다. 찾고자하는 7은 5보다 크기 때문에, 왼쪽 절반을 다 탐색 범위에서 없앱니다.  그리고, 새로운 탐색 범위의 중간값을 살펴봅니다.7은 8보다 작기 때문에 8을 기준으로 오른쪽 부분도 없앱니다.또, 새로운 범위의 중간값을 봅니다.6보다 7이 더 크기 때문에 6을 탐색범위에서 없앱니다.이제, 탐색이 끝났습니다. 만약 찾을 수 없는 숫자를 탐색하고자 한다면, 위와 같이 숫자가 1개 남아도 탐색이 완료되지 않겠죠.  이것까지 고려해서 코드를 짜..

순차 탐색이란, 배열이 주어졌을 때, 앞에서부터 순차적으로 찾는 탐색입니다. 이런 배열이 주어졌을 때, 9를 찾으려면 어떻게 해야할까요? 우리가 눈으로 보기에 그냥 바로 9가 보이겠지만 컴퓨터는 그렇게 할 수 없습니다. 배열의 크기가 100만개, 1000만개 이렇게 기하급수적으로 커지면 우리의 눈으로도 한번에 찾을 수 없겠죠.  순차 탐색의 과정을 살펴보겠습니다.이렇게, 첫 번째 칸부터 9인지 아닌지 판단하며 나아갑니다. 결국 9번째 칸까지 도달하고서야 9라는 숫자를 찾을 수 있겠죠. 이를 프로그래밍 언어로 어떻게 구현할 수 있을까요?  코드)int SequentialSearch(int* arr, int size, int n) { int i; for (i = 0; i  순차 탐색 함수입니다.배열, 배..

삽입 정렬이란, 배열이 주어졌을 때, 앞에서부터 값을 골라 적절한 자리에 넣는 정렬 방식이다.  코드)#include void InsertionSort(int* arr, int size);void Print(int* arr, int size);int main(void) { int arr[] = {8, 1, 1, 3, 2, 5, 1, 2, 1, 1}; int size = sizeof(arr) / sizeof(arr[0]); InsertionSort(arr, size); return 0;}void InsertionSort(int* arr, int size) { for (int i = 1; i 0 && arr[j - 1] > key; j--) { arr[j] = arr[j - 1]; ..

버블정렬은 많은 사람들이 알 것이라 생각한다. 배열이 주어졌을 때, 앞에서부터 하나하나 비교해서 정렬하는 방식이다. 하나하나 비교해야하기 때문에 시간이 오래 걸린다는 단점이 있지만, (O(n^2)) 정렬해야 할 것이 별로 없을 때는 빠르다는 특징이 있다.  코드)#include void BubbleSort(int* arr, int size);void PrintArr(int* arr, int size);int main(void) { { int arr[] = {5, 1, 4, 2, 3}; int size = sizeof(arr) / sizeof(int); BubbleSort(arr, size); } return 0;}void BubbleSort(int* arr, int..