240216_비선형_자료구조_김현욱

[Hyeon-Uk]

1. 최대힙에 대해서 설명해주세요

최대힙은 모든 노드들이 자신의 자식을 루트로 하는 서브트리의 노드들보다 우선순위가 높거나 같은 트리를 의미합니다.

구조는 보통 ARRAY를 이용하여 구현하고, 삽입과 삭제 모두 트리의 높이인 O(LogN) 이 걸리며, 최댓값을 찾는것은 루트노드를 출력하면 되기 때문에 O(1)이 걸립니다.

2. Map과 Set의 차이를 설명해주세요

답 : Map은 Key, Value 형식으로 자료를 저장하는 자료구조입니다. key는 중복되면 안됩니다. Set은 유니크하게 데이터 값을 저장하는 자료구조입니다. 중복되는 데이터는 1개만 저장이 되며, 들어온 순서를 보장하지 않는 자료구조입니다.

3. Hash table의 collision 해결방법에 대해 설명해주세요

1. 분리 체인법 : 같은 인덱스를 가지는 데이터가 여러개인 경우, 해당 인덱스에 LinkedList로 데이터들을 연결하는 방식입니다. 2. 개방 주소법 : 충돌이 생기게 된다면, 비어있는 인덱스를 찾아 데이터를 저장하는 방법을 의미합니다. - 선형 조사법 : 충돌이 생기면, 인덱스에서 +1씩 하며 비어있는 인덱스를 찾는 방법입니다. - 이차 조사법 : 제곱수로 조사하는 방법입니다. - 이중 해싱법 : 이차 해시 함수를 이용해서 인덱스를 다시 발급받는 방법입니다.