카데인 알고리즘은 배열의 최대 부분 합을 O(n)의 시간복잡도로 구하는 알고리즘입니다. 개념을 간단하게 설명하자면, i번째 인덕세를 오른쪽 끝으로 하는 부분 배열들의 최대 부분 합을 M[i]라고 하면, M[i + 1]은 M[i] + arr[i + 1]이거나 arr[i + 1]중 더 큰 값입니다. M[i + 1] = max(M[i] + arr[i + 1], arr[i + 1])인 이유는 i를 오른쪽 끝으로 하는 부분 배열 중 최대 부분 합이 음수이면 굳이 더하지 않고 그냥 i+1 번재 인덱스부터 새로 더하는 것이 이득이기 때문입니다. 참고: https://r4bb1t.tistory.com/10

Huffman Coding이란 고정 길이 코드 vs 접두어 코드 고정 길이 코드는 대표적으로 아스키 코드가 있습니다. 아스키 코드는 항상 8bit의 길이를 가지고 있습니다. 다루기에는 간단하지만, 저장 공간 활용에 있어서 제한이 있습니다. 이를 해결하기 위해서 가변 길이 코드가 존재합니다. 가변 길이 코드 중에서도 접두어 코드는 앞서 나온 문자가 다음에 나올 문자의 접두어가 되면 안 되는 특징을 가진 코드입니다. 예를 들어 다음은 접두어 코드가 아닌 경우 입니다. a: 01 b: 101 c: 010 위 코드에서 01은 010의 접두어이기 때문에 접두어 코드가 아닙니다. 반면 다음은 접두어 코드의 예입니다. a: 01 b: 10 c: 111 이 접두어 코드를 아스키코드로 한다면 총 24bit의 저장 공간을..

Tim sort란 Tim sort란 2002년 소프트웨어 엔지니어 Tim Peters에 의해 만들어진 정렬 알고리즘입니다. Tim sort는 Insertion sort와 Merge sort를 결합하여 만든 정렬 알고리즘입니다. Tim Sort 알고리즘의 최선 시간 복잡도는 O(n), 평균은 O(nlogn), 최악의 경우는 O(nlogn)입니다. Tim sort는 안정적인 두 정렬 방법을 결합했기에 안정적이며, 추가 메모리는 사용하지만 기존의 Merge sort에 비해 적은 추가 메모리를 사용하여 다른 정렬 알고리즘의 단점을 취대한 극복한 알고리즘입니다. 참조 지역성 원리 Tim sort의 기본 원리에 앞서 참조 지역성의 원리를 설명하는 이유는 알고리즘의 실제 동작 시간에 영향을 미치는 요소이고 Tim s..

아호 코라식 알고리즘이란 아호 코라식 알고리즘은 문자열 S와 여러 개의 문자열 T가 주어졌을 때, T에 있는 문자열 중 하나와 S가 매칭이 되는지를 계산할 수 있는 알고리즘 입니다. 아호 코라식 알고리즘은 KMP에서 사용하는 Failure Function을 Trie에 확장시킨 알고리즘입니다. 아래의 예시를 통해 알아보겠습니다. 앞에서 말했듯이 아호 코라식 알고리즘은 트라이 구조를 이용해 동작합니다. 우선 기본 문자열들을 he, she, his, hers으로 설정하고 위의 그림과 같이 트라이를 만들어 줍니다. 그리고 S = "cdhisxy"일 때 어떤 문자열들이 들어있는지 확인해봅니다. 우선 앞에 존재하는 cd의 경우에는 일치하는 문자열이 없으니 스킵하겠습니다. 위의 세 그림을 확인해 보면 'his'라는 ..

트라이란 트라이란 문자열 검색을 빠르게 할 수 있는 자료구조 입니다. 문자열을 특정 키 값으로 변환해서 그 값으로 찾는 방법인 해시 테이블을 대체하기 위해 트라이를 사용할 수 있습니다. 불완전한 해시 테이블의 최악 검색 속도는 모든 데이터를 다 확인하는 것이지만 트라이를 사용하게 되면 문자열 길이 만큼의 속도가 걸리기 때문에 훨씬 더 빠르게 적용이 될 수 있습니다. 보통 트라이를 사용할 때 고려해야할 점은 단어의 길이와 파생되는 Child 노드의 개수입니다. 영어 사전을 예로 들자면, 영어는 알파벳이 26가지이기 때문에 Child 노드는 26개를 가지고 있을 수 있습니다. 전화번호 목록 같은 경우도 0부터 9가지 10가지의 수를 가지고 있을 수 있습니다. 이처럼 적은 Child 노드를 가지고 있는 데이터..

1. 가장 단순한 문자열 검색 가장 단순한 문자열 검색은 문자열의 시작부터 마지막까지 하나씩 주어진 패턴이 존재하는지 확인하는 방법입니다. 예를 들어 텍스트 “ABCABABCDE”에서 패턴 “ABC”가 어디서 등장하는지 찾아봅니다. 패턴 “ABC”를 시작부터 한 자리씩 옮기면서 같은지 비교합니다. 위의 그림과 같은 과정을 보면 “ABCABABCDE”에서 패턴 “ABC”는 두 번 등장함을 알 수 있습니다. (녹색 네모로 표시된 그림이 일치하는 경우) 이 과정의 시간 복잡도는 텍스트의 길이를 N, 패턴의 길이를 M이라 할 때, 각 텍스트의 인덱스에 대해 패턴이 일치하는지 비교하므로 O(NM)입니다. 2. KMP 알고리즘이란 KMP 알고리즘을 이해하기 위한 사전 지식 우선 KMP 알고리즘을 이해하기 위해 먼저..