신나게 공부하자

Bit Vector 0≤i≤N0 \le i \le N0≤i≤N 이라 하자. i번째 원소에 1 을 저장하거나 이미 1인지 검사하는 문제를 생각해봅시다. int *A = new int[N](); // 0으로 초기화 if(A[i]==1) printf("이미 1") else A[i] = 1 int가 4 byte이므로 총 4N byte가 필요할 것입니다. 공간을 줄일려면 크기가 N인 bool 배열을 생성하면 됩니다. bool *A = new bool[N](); // false로 초기화 A[i] = True; bool은 크기가 1byte만 가지므로 총 N byte가 필요합니다. 하지만 크기를 더 줄일 수 있는데요, 1, 0 두 개만 저장하면 되므로 1byte가 아니라 1bit가 필요합니다. int는 대부분의 컴파일..

Suffix Array suffix array란 string의 suffix로 이루어진 sorted array 이다. 예시를 통해 이해하도록 하자. "camel" 이란 string이 suffix는 다음과 같다. Index suffix string 0 camel 1 amel 2 mel 3 el 4 l 이것을 순서대로 정렬하면, Index suffix string 1 amel 0 camel 3 el 4 l 2 mel 따라서 suffix array는 {1,0,3,4,2} 가 된다. suffix string을 저장할 필요 없이 index만 저장하면 된다. Code naive하게 만들기 typedef struct Suffix{ string s; int idx; }Suffix; bool Compare(Suffix a..

Binary Indexed Tree(BIT) N을 배열의 size라 하자. 배열에서 i 번째 원소부터 j 번째 (i