Algorithms (9) 썸네일형 리스트형 Suffix Array (접미사 배열) 접미사 배열 접미사 배열이란, 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 의미합니다. 즉 아래 예시처럼 문자열 "banana"의 모든 접미사들을 정렬한 배열이라고 할 수 있습니다. 0 banana 5 a 1 anana Sort the Suffixes 3 ana 2 nana ----------------> 1 anana 3 ana alphabetically 0 banana 4 na 4 na 5 a 2 nana 접미사 배열 구하기 접미사 배열을 구현하는 알고리즘에는, Naive 알고리즘과 Manber-Myers 알고리즘이 있습니다. Naive 알고리즘 접미사 배열을 만드는 가장 쉬운 방법으로, 단순히 비교 정렬 알고리즘을 이용해서 구현하는 방식입니다. 문자열의 길이가 n이라고 할 때, 접미사는 n.. 해시 함수 (Hash Table) Hash Function 해시 함수(hash function) 또는 해시 알고리즘(hash algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이때, 이 고정된 길이는 해시 함수마다 다릅니다. 하지만 동일한 해시 함수는 동일한 길이의 데이터를 출력합니다. 아래 그림과 같이, data를 hash function에 입력하면, 이 함수는 고정된 길이의 값을 출력합니다. 해시 함수에 의해 얻어지는 값을 해시 값(Hash value) 이라고 합니다. 해시 함수의 특징 해시 값은 항상 고정된 길이의 값을 가집니다.(위 설명 참고) 같은 입력값이면 해시 값은 항상 동일합니다. 다른 입력값일 때, 1bit만 다르더라도 해시 값은 크게 달라질 수 있습니다. 다른 입력값일 때, 같은 .. C언어 - Quick sort 구현 Pivot 선택을 위한 Partition 첫 번째 방법 int hoarePartition(int* a, int low, int high) { int p = a[low]; int i = low; int j = high; while (i C언어 - 문자열 탐색, 비교 구현해보기 이번 포스팅은 C++를 사용하지 않고 (라이브러리 없이) C언어를 이용하여 직접 문자열 관련 함수들을 구현해 보았습니다. strlen: 문자열 길이 C++의 str.size() 혹은 str.length() C언어 첫 번째 방법 (포인터) int strlen(const char* str) { int len = 0; while (*str != '\0') { ++len; ++str; } return len; } int main() { printf("%d\n", strlen("Hello")); // 5 } 두 번째 방법 (배열) int strlen(const char* str) { int len = 0; while (str[len] != '\0') { ++len; } return len; } strcpy: 문자.. 비트 연산 활용 N번째 비트 조회 변수 target의 N번째 비트가 1인지 여부: AND 연산을 수행합니다. 해당 연산이 0이면 비트가 없는 것이고, 1이면 비트가 있는 것입니다. target & (1 그리디 알고리즘 (Greedy)과 다이나믹 프로그래밍 (DP) 그리디 여러 경우 중 하나를 선택할 때마다 그 순간에 최적인 해를 선택해 나가는 근시안적인 방법이다. 특징 각 선택 시점의 결정이 지역적으로 최적이고, 그 결정들이 모여 만든 답이 최적해라는 보장이 있어야 사용가능하다. 이미 선택한 결정은 번복하지 않기 때문에 대부분의 단순하며 제한적인 문제들에 적용된다. 두 가지 필수 요소 Greedy choice property: 탐욕적 선택 속성 탐욕적 선택이 최적해로 갈 수 있음을 보이고 탐욕적 선택이 항상 안전하다는 것을 확인해야 한다 2. Optimal substructure property: 최적 부분 구조 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남아야 한다. ==> 원 문제의 최적 해 = 탐욕적 선택 + 하위 문제의 최적 해 DP ‘귀납법’을 만.. Euler's Phi (오일러 파이 함수) 개념 및 정의 오일러 파이 함수의 정의는 아래와 같습니다. 즉, 이를 해석해 보면 양의 정수 n의 오일러 파이 함수는, 1부터 n까지의 정수 가운데 n과 서로소인 것들의 개수 입니다. 성질 1. 두 정수 m과 n이 서로소인 경우 n의 서로소 개수 곱과 m의 서로소 개수 곱은 n*m의 서로소 개수입니다. 2. 정수 p가 소수인 경우 소수 p의 서로소는 1을 제외한 모든 수입니다. 3. 소수 p의 거듭제곱인 경우 1~3을 종합한 결론 위 성질들을 통해 소인수를 이용한 오일러 파이 함수를 아래와 같이 구할 수 있습니다. 그리고 아래 함수를 오일러 곱 공식이라고 합니다. 예를 들어, 20의 소인수는 2와 5 이므로, ∅(20) 은 20(1-1/2)(1-1/5) = 8로 구할 할 수 있습니다. 증명 오일러 곱 공.. KMP 알고리즘 문자열 검색 알고리즘으로 많이 등장하는 KMP 알고리즘에 대해서 알아보겠습니다. KMP는 Knuth Morris Partt의 줄임말로 이 알고리즘을 발견한 사람 이름을 딴 것입니다. 어떤 문자열 A에 문자열 B가 있는지 확인하려면 단순하게 A 문자열(길이 N)과 B 문자열(길이 M)을 하나하나 비교한다면, 시간 복잡도는 O(NM)가 될 것입니다. KMP 알고리즘은 이 시간 복잡도 보다 더 효율적으로 줄여 O(N+M) 만에 문자열을 검색할 수 있는 방법입니다. 어떻게 획기적으로 시간 복잡도를 줄일 수 있었는지 KMP에 대해서 알아보겠습니다. 먼저, KMP 알고리즘을 알기 전에 미리 알아야 할 사전 지식을 살펴보겠습니다. 사전지식 접두사(Prefix)와 접미사(Suffix) 우선 접두사와 접미사가 무엇인지 .. 이전 1 2 다음
