1. RB 트리 (Red-Back Tree)1.1 개념레드-블랙 트리는, 자가 균형 이진 탐색 트리(self-balancing binary search tree)의 한 종류이다.이진 탐색 트리의 단점인 최악의 경우 탐색 시간이 O(n)으로 늘어나는 문제를 해결하기 위해 고안되었다. 특정 규칙들을 만족하도록 하여 트리의 균형을 유지하고, 이를 통해 삽입, 삭제, 검색 등의 연산을 평균적으로 O(log n) 시간 복잡도로 수행할 수 있습니다. 1.2 특징RB 트리의 특징으로는 아래와 같은 점이 있다.RB 트리는 루트 노드가 항상 검은색이다. ( 재배치하는 과정에서 루트 노드가 빨간색일 수는 있지만, 재배치가 끝나면 항상 검은색 노드를 유지 )루트 노드와 리프 노드는 항상 동일한 색상이다.아래와 같은 상황에 ..

소수판별 알고리즘 1 (시간복잡도 O(N) 알고리즘)bool isPrime(int n) { for(int i=2; i 가장 가볍게 구현할 수 있는 알고리즘으로 2부터 N-1까지의 수 중 나누어떨어지는 수가 있다면 소수가 아니고, 없다면 소수가 된다.소수판별 알고리즘2 (시간복잡도 O(logN) 알고리즘)bool isPrime2(int n) { for(int i=2; i*i 위의 소수판별 알고리즘에서 수학적 규칙을 활용하여 시간복잡도를 O(logN)으로 줄인 것인데 약수를 구할때, N의 제곱근을 중심으로 좌측에 있는 수들은 우측에 있는 수와 짝을 이룬다는 특성을 활용하여 N의 제곱근 이상의 i값은 for문의 범위에 포함하지 않는 것이다.소수판별 알고리즘3 (시간복잡도 O(Nlog(logN)) - 에라토스테..