신입부터의 기록

KMP 하나의 패턴 문자열을 다른 문자열에서 효율적으로 검색하는데 사용됩니다. 주어진 패턴 문자열에서 일치하지 않는 문자를 기반으로 불필요한 비교를 최소화합니다. KMP 알고리즘은 접두사와 접미사의 개념을 활용하여, 불일치가 발생한 위치를 이용해 다음 검색 위치를 결정합니다. 시간 복잡도는 O(N+M), 여기서 N은 텍스트 문자열의 길이, M은 패턴 문자열의 길이입니다. 검사하던 패턴에서 이미 검사한 부분은 건너뛴다는 내용같긴 한데 다른 블로그의 설명들이 많이 부실하다. 해당 내용에 대한 이해를 기반으로 쓴건지 복사해서 쓰는건지.. https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220917078260&categoryNo=299&parentCategor..

Best Worst Memory 선택정렬 n^2 n^2 1 버블정렬 n n^2 1 삽입정렬 n n^2 1 합병정렬 n log n n log n n 힙정렬 n log n 1 퀵정렬 n log n n log n 1 아래 설명은 정렬할 데이터를 vector로 가정하고 설명한다. 1. 선택정렬 처음부터 끝까지 순회하며 현재 위치에 들어갈 값을 찾아 넣는 방식 void sort(vector& v) { for (int i = 0; i v[j]) { min_index = j; } } int temp = v[i]; v[i] = v[min_inde..

엔트로피 인코딩(entropy encoding)은 정보 공학 주제 중 하나로, 데이터 압축에 있어 출현 빈도에 따라 데이터 압축률이 달라진다는 이론이다. 허프만 코딩은 텍스트 압축을 위해 사용되는 방법으로, 데이터에서 출현빈도가 높은 문자는 적은 비트의 코드로 변환하고, 출현 빈도가 낮은 문자는 많은 비트로 변환하여 표현함으로써 전체 데이터를 표현하는데 필요한 비트 수를 줄이는 방식이다. "AAAAAAABBCCCDEEEEFFFFFFG"를 허프만 코딩으로 압축하려고 한다면 글자의 출현 빈도를 다음과 같이 정리할 수 있다. 출현 빈도가 적은 순서대로 이진 트리를 구성하고, 해당 트리 루트 노드에 문자 출현 빈도를 더해 설정한다. 이와 같이 모든 데이터에 대해 반복한다. (매 회차 내림차순 정렬 필요) 마지막..

#include #include template class JISingleTon_CallOnce { public: static _Class& get_instance() { std::call_once(&flag_, [&ptr]() { ptr_ = std::make_unique(); }); return *instance; } JISingleTon_CallOnce = default; virtual ~JISingleTon_CallOnce() = default; JISingleTon_CallOnce(const JISingleTon_CallOnce&) = delete; JISingleTon_CallOnce& operator=(const JISingleTon_CallOnce&) = delete; JISingleTon..