JEEGOO의 개발 노트

#개념 해시 함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말한다. 이러한 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값이라고 한다. 이 값은 해시 코드, 해시 섬(sum), 체크섬 등으로도 불린다. 대표적으로 해시 테이블, 해시 셋 등에서 유용하게 사용된다. 위 자료구조들은 인덱스에 해시값을 사용하는 자료 구조로, 정렬을 하지 않고도 빠른 검색, 빠른 삽입이 가능하다. 해시를 사용하다 보면 동일한 해시 코드가 얻어지는 경우가 있는데 이를 해시 충돌이라 하며 해시 함수의 알고리즘이 뛰어날수록 충돌 확률이 낮다. 해시 충돌의 대표적인 대안으로써 다음과 같은 방법들이 있다. @Chaining 해시 충돌이 일어날 경우 해당 해시 코드로 최초 저장된 데이터를 시작..

# 개념 이진 탐색 트리이며 자가 균형 이진 탐색 트리이다. 이진 탐색 트리는 값이 편향적으로 구성되는 경우가 있다. 예를 들어 7, 6, 5, 4, 3, 2, 1 순서로 값을 넣으면 한쪽으로 치우진 트리가 만들어진다. 즉, 이진 탐색 트리의 시간 복잡도는 최악의 경우(위 예시) O(트리의 높이=h)만큼의 시간 복잡도를 가진다. 레드-블랙 트리는 위 단점을 색상을 이용한 정렬로 해결하며 O(logN)의 시간 복잡도를 가진다. 또한 균형을 유지하기 위해서 다음의 조건을 만족해야 한다. 노드는 레드 혹은 블랙 중 하나이다. 루트 노드는 블랙이다. 모든 리프 노드(NIL)들은 블랙이다. 레드 노드의 자식 노드들은 항상 블랙이다. (즉, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있으며 레드 노드는 연속적으..

# 개념 이진 트리이다. 각 노드에 하나의 키를 저장한다. 노드 n의 왼쪽 서브 트리에는 n의 값보다 같거나 작은 노드들이 있다. 노드 n의 오른쪽 서브 트리에는 n의 값보다 같거나 큰 노드들이 있다. @검색 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다. 검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다. 불일치하고 검색하고자 하는 값이 루트노드의 값보다 작을 경우 왼쪽 서브트리에서 재귀적으로 검색한다. 불일치하고 검색하고자 하는 값이 루트노드의 값과 같거나 큰 경우 오른쪽 서브트리에서 재귀적으로 검색한다. @삽입 삽입을 하기 전, 검색을 수행한다. 트리를 검색한 후 키와 일치..

# 개념 순환 또는 재귀함수. Recursive 메서드는 자기 자신을 호출한다. Resursive 메서드는 Base Case와 Recursive Case를 가져야 한다. -Base Case : Recursion을 벗어나는 경우 -Recursive Case : 자기 자신을 호출하는 경우. 최종적으로 Base Case로 수렴해야 한다. # 예제 n까지의 합계 구하기 const sum = n => { if (n { if(n == 0) return 1; else return n * factorial(n-1); } 피보나치 수 구하기 const fibonacci = n => { if(n < 2) return n; else return fibonacci(n-1) + fibonacci(n-2); } 최대공약수(GDC..