1.
BST에 대해 설명해 주세요.
•
BST(Binary Search Tree)는 이진 트리 구조로, 각 노드는 최대 두 개의 자식을 가집니다. 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큽니다. 이 구조를 통해 데이터를 효율적으로 검색할 수 있으며, 평균 시간 복잡도는 O(log n)입니다. 하지만 트리가 불균형해지면 성능이 O(n)으로 저하될 수 있습니다.
2.
Hash table는 어떤 자료구조인가요?
•
Hash table은 키-값 쌍을 저장하는 자료구조로, 해시 함수를 사용해 데이터를 빠르게 검색합니다. 평균 시간 복잡도는 O(1)이지만, 해시 충돌이 발생할 수 있습니다.
3.
Hash table에서 collision이 발생하면 어떻게 되나요? 해결방법엔 뭐가 있을까요?
•
Collision: 서로 다른 키가 동일한 해시 값을 가질 때 발생합니다.
•
해결 방법:
◦
체이닝: 연결 리스트를 사용해 동일한 해시 값의 데이터를 연결합니다.
◦
오픈 어드레싱: 빈 슬롯을 탐색해 데이터를 저장합니다.