Social Developer

어제보다 한 걸음 더

CS/Data Structure

본 포스팅은 jisikTank 스터디에 참여하며 정리한 문서입니다. jisikTank CS지식 Git Repository B-Tree & B+ Tree 이진 트리는 하나의 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면(skewed Tree) 검색 효율이 선형검색 급으로 떨어진다. 하지만 이진 트리 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있기 때문에 계속 개선시키기 위한 노력이 이루어지고 있다. Balanced Tree 삽입과 삭제시 필요하면 스스로 균형을 유지함 AVL Tree, 2-3(-4) Tree, Red-Black Tree, B-Tree... 항상 log(N)의 검색 성능! B Tree 하나의 노드에 여러가지가 배치되는 트리구조 ..

2021. 4. 20.

CS/Data Structure

본 포스팅은 jisikTank 스터디에 참여하며 정리한 문서입니다. jisikTank CS지식 Git Repository 해시(Hash) 유튜버 A가 업로드한 영상을 다른 유튜버가 같은 파일을 올리려고 하면 오류 메세지 and 유튜버 A에게 알림이 뜬다?! 어떻게 하는 걸까..? -> Hash Table 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것 해시 함수를 구현하여 데이터를 해시 값으로 매핑한다. Hash Function(key: 숫자, 파일데이터, 문자열..) -> HashCode -> Index -> Value 배열 공간을 고정된 크기 만큼 만들어 두고, 해시 코드를 배열의 크기 만큼 나머지 연산을 통해 배열에 나눠 담는다. 해시코드 자체가 배열의 ..

2021. 4. 20.

CS/Data Structure

본 포스팅은 jisikTank 스터디에 참여하며 정리한 문서입니다. jisikTank CS지식 Git Repository 이진탐색트리(Binary Search Tree) 이진 탐색(Binary Search) + 연결리스트(LinkedList) 이진 탐색 탐색에 소요되는 시간복잡도 $$ O(log_2N) $$ 연결리스트 삽입, 삭제의 시간복잡도 O(1) but 탐색하는 시간 복잡도 O(N) 이 2가지를 합해 장점을 모두 얻는 것이 이진탐색트리이다. 이진탐색트리의 특징 각 노드의 자식이 2개 이하(이진 트리) 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼 중위순회(in-order) 방식(왼쪽 - 루트 - 오른쪽) 구조 -> 정렬된 순서를 읽을 수 있음 중복값 노드는 존재하지 않음 중복이 ..

2021. 4. 20.