</note>

mississippi라는 문자열이 있다. 여기에서 ssi라는 문자열을 찾으려고 한다면 어떻게 해야 할까? 완전 탐색을 사용한다면 O(NM)의 시간 복잡도 안에서 해결할 수 있을거라고 생각한다. 앞글자가 일치하는 단어를 찾고 그 이후부터 글자가 동일한지 아닌지를 비교하면 될것이다. 하지만 이런 방법은 당연히 시간초과가 날 수 밖에 없다. 하지만 Rabin-Karp알고리즘을 사용하면 그 문제를 해결 할 수 있다. Rabin - Karp 알고리즘은 문자열 검색을 할 때 해시값을 이용하는 기법이다. 패턴 내의 문자들을 일일이 비교하는 대신에 패턴의 해시값과 비교할 문자열의 부분 문자열의 해시값만을 비교한다. 최악의 경우에 O(NM)의 시간복잡도를 가지지만, 평균적으로는 선형시간의 시간 복잡도를 가지기 때문에 효..

Binary Search(이분탐색)은 정렬된 배열 안에서 특정한 값의 위치를 찾는 알고리즘이다. 처음에 중간값을 임의의 값으로 설정하고 그 값과 찾고자 하는 값과 크고 작음을 비교해서, 만일 임의의 값이 찾고자 하는 값보다 크다면 임의의 값을 최소값으로 해서 다시한번 중간값을 탐색하고, 작다면 임의의 값을 최대값으로 해서 중간값을 탐색하게 하는 알고리즘이다. 정렬된 상태에서만 가능하다는 단점이 있지만, 정렬되어 있을 경우 이분 탐색이 선형 탐색을 할 때보다 더 나은 성능을 보장한다. (선형 탐색의 경우 O(n)의 시간 복잡도를 가지는 반면에 이분 탐색의 경우 O(log n)의 시간 복잡도를 가진다.) 일반적인 이분 탐색은 위와 같지만 경우에 따라서 임의의 값을 최대값으로 할 지 최소값으로 할 지 결정해서..

보통 해싱은 해시 함수를 통해 임의의 데이터를 고정된 길이의 데이터로 매핑하는 것이라고 한다. 데이터베이스에서 테이블에서의 빠른 탐색을 위해서 테이블 내의 각각의 튜플에 대해서 색인(Index)을 만들어서 색인 만으로 데이터를 검색하는데 이용한다. 해싱을 알고리즘 문제 풀이에 어떤 식으로 사용하는지 설명 해보려고 한다. 알고리즘에서 해싱이 사용되는 분야는 문자열이 대부분이어서(아직 공부가 부족해서 문자열밖에 접해보지 못했다.) 대부분의 설명이 문자열에 관한 내용이 될 수밖에 없을 것 같다. 사람의 시각으로 보면 당연히 문자열은 하나의 의미 덩어리이고 그냥 눈으로 보면 비교가 가능한 것이지만 컴퓨터의 관점에서 보면 문자들의 배열이기 때문에 비교하려면 하나하나 다 확인하는 수밖에 없어서 시간이 많이 걸릴 수..

SW Expert Academy에서 트리의 지름에 관련된 문제를 풀게 되었다. (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PN4CqACYDFAUq&) 이 문제를 처음 봤을 때 트리의 지름, 반지름, 중심에 관련된 문제이구나 하는 생각이 들어서 문제를 푸는데 안풀린다.. 아는 개념이라고 생각했었는데 잘 안풀려서 이번 기회에 복습해 보려고 한다. 이 문제의 풀이는 다음과 같다. 1. 모든 독립된 연결 요소들을 하나의 트리를 보고 각각의 트리에서 지름을 구한다. 2. 지름을 구하는 과정에서 구한 지름의 양끝점 u에서 v로 가는 경로를 탐색하면서 반지름을 구한다. 3. 반지름들을 이용해서 연결요소들을 연결 할 ..

Fenwik Tree(Binary Index Tree)는 구간합을 구할때 많이 사용되는 자료구조이다. 처음 배울 때 분명히 이해 했는데 매번 다시 볼때마다 새로워서 계속 코드를 보면서 공부해야할것 같다. Fenwik Tree를 구현하려면 어떤 수 N을 이진수로 만들었을 때 마지막 1의 위치를 구할 수 있어야 한다 L[i]배열의 값을 직접적으로 사용하지는 않지만 Fenwik Tree를 이해하기 위해서는 이해하고 있어야 할 듯 하다. 따라서 L[i]값을 수식으로 구하면 (i & -i)가 된다. (L[i] = (i & - i)) 그리고 배열 A[1] ~ A[N]에 N개의 수가 들어있다고 할 때 Tree[i]에는 A[i - L[i + 1]] ~ A[i]까지의 합이 저장되게 하면 된다. Fenwik Tree를 U..

문제를 풀다가 문자열 한 줄을 받아야 하는 일이 간혹 생긴다. 이때 scanf("%s", in); 과 같은 형태로 입력을 받을 경우 공백 문자에서 끊겨벼려서 한 줄을 전부 입력받을 수 없게 된다. cin.getline을 사용하는 방법도 있고(C++), gets, fgets를 사용하는 방법(C)이 인터넷에 많이 굴러다니는데 나의 경우에는 문제를 풀 때 scanf말고 다른게 들어가면 헷갈리기 시작해서 잘 안쓰는 편이다.(사실 그냥 위에거 아무거나 쓰면 된다. 그런데 굳이 scanf를 사용해서 한 줄을 입력받기 위해서는 %와 s사이에 정규식을 집어넣어 주면 된다. 간단한거라 외워두면 편할듯 하다. scanf("%[^\n]s", in); 인데 [^\n]이라는 정규식은 그냥 \n(개행 문자)가 나오기 전까지 입력..

STL을 배제하고 문제를 풀어보면서 가장 힘들었던게 vector를 못쓴다는 점이었다. 그래서 이번기회에 vector를 구현해봤다. 평소에 안쓰던 문법을 많이 사용해본것같다. - 2021.04.03 수정 (카라츠바 알고리즘 구현을 위해 생성자 추가) #include #include template class _vector{ private: T* _elements; int _size, _cap; void init(int cap) { _size = 0; _cap = cap; _elements = (T*) malloc(sizeof(T) * _cap); } public: _vector(){ init(32); } _vector(int cap, int init_value) { init(cap); for (int i ..

이번에 시험보면서 구현해 보는데 애를 먹어서 다시 한번 구현해 보게 되었다. 이게 꽉차면 동적으로 재할당 되면서 늘어나게 하고 싶어서 벡터를 재할당 하듯이 구현해 봤다. 이러면 매번 재사용 할 때 메모리를 덜 잡아먹지 않을까? 하는 바람으로.. template void _swap(T& e1, T& e2){ T tmp = e1; e1 = e2; e2 = tmp; } template class _priority_queue{ private: T* pq; int _size, cap; public: _priority_queue():_size(0), cap(2){ pq = new T[cap]; }; ~_priority_queue(){ delete[] pq; } void resize(int ncap){ cap = n..

그냥 공부하면서 queue를 구현 해 보게 되었는데 처음에는 작은 사이즈로 queue를 선언하고 크기가 커지면 동적으로 계속해서 늘리게 하려고 했으나 어디서 문제가 생겼는지는 아직 모르겠는데 계속 오류가 발생한다. 그래서 queue의 최대 용량을 정해두고 circular queue를 구현해 보게 되었다. const int NMAX = 100005; template struct _queue{ T* q; int _front, _rear, _size, cap; _queue():_front(0), _rear(0), _size(0), cap(NMAX){ q = new T[cap]; } ~_queue(){delete[] q;} int size(){return _size;} int full(){return _size..

template class _stack{ private: T* ele; int _top, cap; public: _stack():_top(0), cap(2){ ele = new T[cap]; } ~_stack(){ delete[] ele; } void resize(int ncap){ cap = ncap; T* tmp = new T[cap]; for(int i = 0; i < _top; i++) tmp[i] = ele[i]; delete[] ele; ele = tmp; } int full(){return _top == cap;} int empty(){return _top == 0;} int size(){return _top;} void push(T e){ if(full()) resize(cap * 2); ..