개발자 전공 면접 - 4. 자료구조

==🗂️ 자료구조 핵심 요약==

• 힙은 최대값 또는 최소값을 빠르게 찾아주는 완전 이진 트리로, 우선순위 큐 구현에 적합한 자료구조입니다.

• 이진 탐색 트리는 정렬된 데이터의 효율적인 검색, 삽입, 삭제를 가능하게 하지만, 트리가 한쪽으로 편향될 경우 성능 저하가 발생할 수 있습니다.

• 해시 테이블은 키를 해시 함수에 매핑하여 데이터를 $O(1)$에 가깝게 조회, 삽입, 삭제하는 자료구조로, 충돌 해결 기법이 핵심적인 역할을 합니다.

힙 (Heap) 완벽 해부 핸드북

1. 힙이 만들어진 이유

힙은 최대값 또는 최소값을 매우 빠르게 찾아야 하는 문제에 특화된 자료구조다. 일반적인 배열이나 리스트에서 최대값이나 최소값을 찾으려면 모든 원소를 순회해야 하므로 $O(n)$의 시간 복잡도가 소요된다. 하지만 힙은 이 과정을 $O(1)$의 시간 복잡도로 해결할 수 있어, 실시간으로 우선순위가 높은 데이터를 처리해야 하는 ‘우선순위 큐(Priority Queue)’ 구현에 이상적이다. 힙은 완전 이진 트리의 특성을 활용하여 이러한 효율을 달성한다.

2. 힙의 구조와 종류

힙은 완전 이진 트리(Complete Binary Tree)의 형태를 가진다. 완전 이진 트리란 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 왼쪽부터 순서대로 채워지는 트리를 의미한다.

힙의 가장 중요한 규칙은 ‘힙 속성(Heap Property)‘이다. 이 속성은 부모 노드와 자식 노드의 값 사이의 관계를 정의하며, 이 규칙에 따라 힙은 두 가지 종류로 나뉜다.

• 최대 힙 (Max Heap): 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같다. 따라서 루트 노드에는 항상 전체 데이터 중 최댓값이 위치하게 된다.

• 최소 힙 (Min Heap): 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같다. 이 경우 루트 노드에는 항상 전체 데이터 중 최솟값이 위치한다.

3. 힙의 핵심 연산: 삽입과 삭제

힙에서 데이터의 삽입과 삭제는 항상 로그 시간, 즉 $O(\log n)$의 시간 복잡도를 가진다. 이는 트리의 높이(h)가 $O(\log n)$이기 때문이다.

가. 삽입 (Insertion)

힙에 새로운 원소를 추가하는 과정은 다음과 같다.

1. 새 원소를 트리의 맨 마지막 자리에 추가한다. 이렇게 하면 힙의 완전 이진 트리 속성은 유지된다.

2. 추가된 원소와 그 부모 노드의 값을 비교하며, 힙 속성을 만족할 때까지 위로 올라가면서(상향식) 위치를 교환한다. 이 과정을 힙 상향 재조정(Heapify-up)이라 부른다.

비유적으로 설명하면, 신입 선수가 팀에 들어왔을 때, 자신의 실력에 맞는 포지션을 찾기 위해 계속해서 선배 선수들과 실력을 비교하며 위로 올라가는 과정과 같다.

나. 삭제 (Deletion)

힙은 항상 루트 노드만 삭제할 수 있다. 만약 루트가 아닌 다른 노드를 삭제하려면, 해당 노드까지 탐색하는 데 시간이 소요되어 힙의 장점을 잃기 때문이다. 루트 노드를 삭제하는 과정은 다음과 같다.

1. 루트 노드의 값을 삭제한다.

2. 트리의 맨 마지막 노드를 루트 자리로 옮겨 놓는다.

3. 새롭게 루트가 된 노드의 값과 그 자식 노드들의 값을 비교하며, 힙 속성을 만족할 때까지 아래로 내려가면서(하향식) 위치를 교환한다. 이 과정을 힙 하향 재조정(Heapify-down)이라 부른다.

이는 마치 팀의 챔피언이 은퇴했을 때, 맨 끝에 있던 선수가 일단 챔피언 자리에 임시로 올라가고, 자신의 실력에 맞는 포지션을 찾기 위해 다시 아래로 내려가는 과정과 유사하다.

4. 힙의 활용 분야

• 우선순위 큐(Priority Queue): 가장 중요한 활용처다. 시스템의 작업 스케줄링, 네트워크 패킷 처리 등 우선순위가 있는 작업들을 관리하는 데 사용된다.

• 힙 정렬(Heap Sort): 힙의 속성을 이용하여 데이터를 정렬하는 알고리즘. $O(n\log n)$의 시간 복잡도를 가지며, 안정적인 성능을 보인다.

이진 탐색 트리 (Binary Search Tree) 완벽 해부 핸드북

1. 이진 탐색 트리가 만들어진 이유

이진 탐색 트리는 데이터를 효율적으로 탐색, 삽입, 삭제하기 위해 고안된 자료구조다. 정렬된 배열에서 이진 탐색을 통해 $O(\log n)$의 빠른 탐색이 가능하지만, 삽입이나 삭제 시에는 모든 원소를 재정렬해야 하는 $O(n)$의 비효율성이 발생한다. 이진 탐색 트리는 이러한 문제를 해결하여 탐색과 삽입/삭제 모두를 효율적으로 수행하도록 설계되었다.

2. 이진 탐색 트리의 구조와 속성

이진 탐색 트리는 이진 트리(Binary Tree)의 한 종류로, 모든 노드가 다음과 같은 BST 속성(Property)을 만족한다.

• 노드의 왼쪽 서브트리에 있는 모든 값은 노드의 값보다 작다.

• 노드의 오른쪽 서브트리에 있는 모든 값은 노드의 값보다 크다.

• 각 서브트리도 이진 탐색 트리다.

이 속성 덕분에 우리는 특정 값을 찾기 위해 모든 노드를 방문할 필요 없이, 마치 수학 문제의 범위를 좁히듯 특정 방향으로만 내려가면 된다.

3. 이진 탐색 트리의 핵심 연산

이진 탐색 트리의 모든 연산은 트리의 높이에 따라 시간 복잡도가 결정된다.

• 검색 (Search): 루트 노드에서 시작하여 찾고자 하는 값과 현재 노드의 값을 비교한다. 값이 더 작으면 왼쪽으로, 더 크면 오른쪽으로 이동하며 찾는다. 평균적으로 트리의 높이(O(logn))만큼 시간이 소요된다.

• 삽입 (Insertion): 검색과 동일한 방식으로 삽입될 위치를 찾아 내려간다. 원하는 값을 찾을 수 없을 때까지 내려간 후, 마지막으로 방문한 노드의 왼쪽 또는 오른쪽에 새로운 노드를 추가한다. 평균 시간 복잡도는 $O(\log n)$이다.

• 삭제 (Deletion): 삭제할 노드를 찾은 후, 자식 노드의 개수에 따라 세 가지 경우를 고려해야 한다.

  1. 자식 노드가 없는 경우: 해당 노드를 단순히 삭제한다.

  2. 자식 노드가 하나인 경우: 해당 노드를 삭제하고, 그 자식 노드를 부모 노드에 직접 연결한다.

  3. 자식 노드가 두 개인 경우: 오른쪽 서브트리에서 가장 작은 값(또는 왼쪽 서브트리에서 가장 큰 값)을 찾아 삭제할 노드의 자리로 옮기고, 원래 있던 노드를 삭제한다. 이 방법은 트리의 구조를 최대한 보존한다.

4. 심화: 편향된 트리의 문제와 자가 균형 트리의 등장

이진 탐색 트리는 모든 원소가 이미 정렬된 상태로 삽입될 경우, 한쪽으로만 노드가 추가되어 선형 구조(Linked List)처럼 변형될 수 있다. 이 경우 트리의 높이가 $O(n)$이 되므로, 모든 연산의 시간 복잡도가 $O(n)$으로 악화되어 이진 탐색 트리의 장점을 잃게 된다. 이러한 현상을 편향(Skewed)이라 부른다.

이 문제를 해결하기 위해 등장한 것이 바로 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)다. 이는 삽입이나 삭제 연산이 발생할 때마다 자동으로 트리의 균형을 잡아줘서 트리의 높이를 항상 $O(\log n)$으로 유지한다. 대표적인 자가 균형 트리로는 AVL 트리와 레드-블랙 트리가 있으며, 이들은 트리의 높이를 관리하여 최악의 경우에도 항상 효율적인 성능을 보장한다.

해시 테이블 (Hash Table) 완벽 해부 핸드북

1. 해시 테이블이 만들어진 이유

해시 테이블은 데이터 검색의 시간 복잡도를 $O(1)$로 만들기 위해 고안된 자료구조다. 배열, 리스트, 심지어 트리와 같은 다른 자료구조들이 검색에 최소 O(logn) 이상의 시간이 소요되는 것에 비해, 해시 테이블은 키(key)를 통해 원하는 값(value)에 즉시 접근할 수 있다. 이는 키를 이용하여 데이터가 저장된 위치(주소)를 계산해 내는 독특한 방식을 사용하기 때문이다.

2. 해시 테이블의 구조와 구성 요소

해시 테이블은 크게 해시 함수, 해시 값, 그리고 버킷이라는 세 가지 핵심 요소로 구성된다.

• 해시 함수 (Hash Function): 임의의 길이의 데이터를 고정된 길이의 데이터로 변환하는 함수. 해시 테이블에서 이 함수는 키를 받아 해시 값을 생성하는 역할을 한다. 좋은 해시 함수는 키를 고르게 분산시켜 충돌을 최소화해야 한다.

• 해시 값 (Hash Value): 해시 함수의 결과로 나오는 값. 이 값은 테이블 내의 버킷을 식별하는 데 사용되는 인덱스 역할을 한다.

• 버킷 (Bucket): 실제 데이터가 저장되는 공간. 일반적으로 배열로 구현되며, 각 버킷은 고유한 해시 값에 대응된다.

비유적으로, 해시 테이블은 서랍장과 같다. 해시 함수는 수십 권의 책(키)을 장르별 번호(해시 값)로 분류하는 역할을 하고, 버킷은 각 번호에 해당하는 서랍이다. 책을 찾을 때는 장르 번호만 알면 곧바로 해당 서랍을 열 수 있어 시간을 절약할 수 있다.

3. 해시 테이블의 핵심 연산

해시 테이블의 모든 연산은 평균적으로 $O(1)$의 시간 복잡도를 가진다.

• 삽입 (Insertion): 키를 해시 함수에 넣어 해시 값을 얻고, 그 해시 값에 해당하는 버킷에 값을 저장한다.

• 검색 (Search): 검색하려는 키를 해시 함수에 넣어 해시 값을 얻고, 해당 버킷으로 즉시 이동하여 값을 가져온다.

• 삭제 (Deletion): 검색과 동일한 방식으로 버킷을 찾은 후, 그 안에 있는 값을 제거한다.

4. 심화: 해시 충돌(Collision)과 해결 기법

해시 테이블에서 가장 중요한 도전 과제는 충돌(Collision)이다. 충돌은 다른 키들이 해시 함수를 거쳐 동일한 해시 값, 즉 동일한 버킷을 가리킬 때 발생한다. 예를 들어, 두 개의 다른 책이 같은 장르 번호를 가지는 상황이다.

이러한 충돌을 해결하기 위해 두 가지 주요 기법이 사용된다.

기법	작동 방식	장점	단점
체이닝 (Chaining)	각 버킷에 링크드 리스트를 할당하여, 충돌이 발생하면 해당 리스트의 끝에 새로운 원소를 연결한다.	구현이 간단하고 테이블 크기 조절에 유연하다.	리스트가 길어지면 탐색 시간이 증가한다.
개방 주소법 (Open Addressing)	충돌이 발생하면 테이블 내의 비어 있는 다른 버킷을 찾아 데이터를 저장한다. 비어 있는 버킷을 찾는 방식에 따라 선형 탐사, 이차 탐사, 이중 해싱 등이 있다.	추가적인 메모리 할당이 필요 없고 캐시 효율이 높다.	특정 위치에 데이터가 몰리는 클러스터링 현상이 발생할 수 있다.

충돌 해결은 해시 테이블의 성능에 직접적인 영향을 미치므로, 어떤 기법을 선택하고 어떻게 구현하는지가 매우 중요하다.

총정리: 자료구조 비교

자료구조	특징	평균 시간 복잡도 (삽입, 삭제, 검색)	주요 활용
힙 (Heap)	완전 이진 트리 형태, 최대/최소값을 $O(1)$에 접근	O(logn), O(logn), O(n)	우선순위 큐, 힙 정렬
이진 탐색 트리	정렬된 이진 트리, 왼쪽<부모<오른쪽 속성	O(logn), O(logn), O(logn)	사전, 집합, 데이터 정렬 및 탐색
해시 테이블	해시 함수를 이용해 키-값 매핑, $O(1)$에 가까운 빠른 접근	O(1), O(1), O(1)	캐시, 데이터베이스 인덱스, 딕셔너리

1. 힙(Heap)

1.1. 🌳 정의

• ==최대/최소 값==을 빠르게 찾기 위한 ==이진 트리 자료구조==
• ==최소 힙==: 부모 노드는 자식 노드보다 값이 ==작아야 함==
• ==최대 힙==: 부모 노드는 자식 노드보다 값이 ==커야 함==

1.2. ⏱️ 시간 복잡도

• 삽입: O(log n)
• 삭제: O(log n)

1.3. ➕ 삽입

• 새로운 원소를 트리의 ==맨 아래==에 추가
• 부모 노드와 비교 후, 조건에 따라 ==위치 변경 (힙 속성 유지)==

1.4. ➖ 삭제

• 루트 노드 (최대/최소 값) 삭제
• ==마지막 노드==를 루트 노드 위치로 이동
• 자식 노드와 비교 후, 조건에 따라 ==위치 변경 (힙 속성 유지)==

2. 이진 탐색 트리(Binary Search Tree)

2.1. 🔍 정의

• 왼쪽 자식 노드는 부모 노드보다 값이 ==작고==, 오른쪽 자식 노드는 부모 노드보다 값이 ==큰 이진 트리==

2.2. ⏱️ 시간 복잡도

• 삽입: O(log n) ~ O(n) (편향된 경우)
• 검색: O(log n) ~ O(n) (편향된 경우)
• 삭제: O(log n) ~ O(n) (편향된 경우)

2.3. ⚖️ 문제점: 편향 트리

• 트리가 한쪽으로 치우쳐져 균형이 깨지는 현상
• 시간 복잡도가 O(n) 으로 증가

2.4. ✨ 해결책: 자가 균형 트리

• 삽입/삭제 시 자동으로 트리의 균형을 유지하는 트리
  • 종류: ==AVL 트리==, ==Red-Black 트리==

3. 해시(Hash)

3.1. 🔑 정의

• ==해시 함수==를 사용하여 데이터를 저장하고 검색하는 자료구조
• ==해시 함수==: Key를 Hash 값으로 변환
• ==해시 값==: 데이터가 저장될 위치 (Bucket)

3.2. ⏱️ 시간 복잡도

• 삽입: O(1)
• 삭제: O(1)
• 검색: O(1)

3.3. 💥 해시 충돌

• 서로 다른 Key가 동일한 Hash 값을 가지는 경우

3.4. 🛡️ 충돌 해결 기법

3.4.1. 개방 주소법 (Open Addressing)

• 비어있는 다른 해시 값 (Bucket)에 데이터를 저장

3.4.2. 체이닝 (Chaining)

• 각 Bucket을 ==연결 리스트==로 구현하여 여러 데이터를 저장

대본

[음악] 안녕하세요 개발자 창고입니다 자료도 시작하겠습니다 팁 입니다 네이비 인데요 스티븐 5 최대값 최소값을 빠르게 찾기 위한 이진 트리의 요 이게 무슨 말이냐고 하면은 자 우선 이진 트리 니까 이런식으로 이런식 이런식으로 구성되어 있겠죠 근데 여기서 하나의 규칙이 있는데 그 규칙이 뭐냐면 자 최소희 b 라고 가정을 할게요 자 최소 입은 부모는 짜식 자식보다 자 가야되요 자 그럼 부모는 부모는 자식보다 작으니까 여기가 더 작을 되죠 여기보다는 그 다음에 여기 보단 여기에서 잡을 테죠 그러니까 여기가 항상 최소 값이 되요 그래서 이 최소값은 최소희 룰 경우에는 부모는 자식보다 짧고 요 최대 힙을 경우에는 부모는 자식보다 커야 되요 자 그리고 여기서 이렇게 자료구조와 이루어 져서 최대값 최소값을 빠르게 찾는 이진 트리가 힙이 되겠죠 자궁 여기서 10 에 새롭게 원소 를 추가한다 그럼 어떻게 될까요 자 그러면은 이 어떻게 추가를 하냐면 어 맨 위에 다수 가는게 아니고 en 부모의 추구하는 게 아니고 여기 밑에다가 새롭게 만들어요 그리고 이 부모랑 이 오일을 필요해요 자 그래서 많이 이게 다 이게 더 작다 값이 그럼 여기 올려요 그리고 이거라고 그럼 또 비교 해요 그래서 이걸 안하면 또 올려요 이런식으로 더 이상 필요 안되도 될수 있을만큼 계속 비교를 해 나갈 자 그럼 이렇게 높이가 얼마나 되겠죠 2 루피가 이 높이의 만큼은 시간 복잡도 흘리고 이렇게 이징 크리 있고 여기가 이렇게 두개씩 2개씩 있는거는 여기는 높이 가로 그앤 이에요 그래서 집에 삽입은 로그의 4시가 목적도 가는거 자 그럼 삭제를 어떻게 아냐 자 힙은 이 중간값 들잖아요 중 각 것들을 알수 있는 방법이 없어요 깊 은 항상 이 최상위에 있는 이 값들은 r2 것만 알 수 있어요 이건 말 그래서 삭제를 한다는 의미는 이 값을 삭제 안 되는 거거든요 자 이 값은 삭제하면 그냥 학생을 어떻게 되죠 그럼 여기 같은 빙 값이 내 5리 잖아요 그래서 바로 소스를 못하고 2 맨 첫번째 라언 끝에 있는거라 의지를 바꿔요 의 여기를 삭제 버려요 여기는 큰 깟 이 최소 최소 pb 의 경우 여기는 큰 값이 여기 들어왔죠 지금 여기가 최소 값이 아니잖아요 왜냐하면 지금 최소값은 삭제를 해 버렸으니까 여기랑 여기 두개라 비교를 해서 이제 내리고 여기를 내리고 또 밑에 비교해서 내리고 이런식으로 원래 자리로 찾아가게 되는 거죠 이것도 마찬가지로 로브 m 만큼은 시간 복잡도를 가져요 자 그래서 힘을 정리하자면 자 변 조건이 티비 뭐예요 라고 물어본다면 저는 힙을 이렇게 말할 거에요 4 힙은 최대가 보건 최소값을 빠르게 찾기 위한 이진 트리 입니다 최소희 분 흐미 경우에는 부모는 자식보다 작구요 최 힙의 경우에는 부모는 자식보다 커야 됩니다 왜 시간 복잡도 는 힘의 삽입과 삭제 1 로브의 이만큼의 시간 복잡도를 같습니다 라고 대답할 것 같아요 자 다음은 이진 탐색 트리 할게요 자 이진 탐색 트리 는 어 아까 힙 이랑 자리 구조는 비슷해요 어떤 식으로 이루어져 있냐며 는 이런 식으로 일어 이렇게 이진 트리의 똑같이 근데 이 규칙이 조금 다르죠 왼쪽 자식은 부모 다 잡고 오른쪽 자식을 부모로 다 허 역 대 를 내면 연기가 오면 요 여기는 이가 들어가야 되고 여기는 뭐 7이 들어왔죠 그 여기는 1 3 5 이런 식의 규칙이 맞아야 되요 그래서 왼쪽은 부모보다 짝 뽀 오른쪽은 후 몸보다 큰 이럴 뒤치기 만들어 줘야 되요 자 그러면 어 내가 새로 삽입을 하고 검색을 하고 숙제 그 시간 복잡도가 어떻게 알려줄게요 자 내가 예를 들어서 6을 삽 입하고 싶어요 그럼 어떻게 되냐면 병의 선부터 오보 다육이 크 져 그럼 일로 간 다음에 7보다 여기 작 쩍 흐름이 여기에 유기 이렇게 살 땐 그래서 2 어디 시즌 탐색 q 도 마찬가지로 이 높이만큼 삽입이 시간 복잡도 흘려요 검색도 마찬가지요 6은 찾으려면 5부 또 작 사 를 찾아 볼게요 모두 또 언제 께서 5보다 짧아요 그래요 짝 쩍 그러면은 이 2와 비교를 해 살을 해서 사각 이보다 크 져 그럼 일로 가서 여기서 이제 찾는 거죠 이만큼 취해 대회가 높인 만큼 걸리고요 삭제도 뭐 이런 비슷한 옆에 올게요 그럼 제가 이렇게 높이라고 한 이유가 볼까요 이 로브 애니라고 하지 않고 필요한 이유는 이 시간 복잡도가 로브 n 에서 앤 만큼 될 수 있어요 자 왜냐면은 자 내가 만약에 여기서 영을 새로운 출발 게 어 0이면 별로 하 죠 여기도 딜러가 줘 여기도 일로 아 줘 그래서 병인 일로 들어가죠 - 를 넣어 볼게요 1 거겠죠 이런식으로 e 증 탐색 트리 는 이렇게 한 쪽으로 편향되어 1 수가 있어요 이렇게 한쪽으로 치우쳐 있다는 걸 표현돼 있다 고 보라구요 그래서 이렇게 평양 될 수 할수가 있어요 자 근데 이렇게 평양 되면 무슨 문제가 생긴 야 면은 최대 시간 복잡도가 이런식으로 돼 가지고 2 m 만큼 의 시간 복잡도가 되요 그래서 시간 복잡도 는 로브 n 에서 m 만큼의 치가 목적도 가 되는 거에요 자 그래서 이렇게 편향된 현상을 막기 위해서 이렇게 삽입 될 때마다 잘 동적으로 이렇게 이런것을 준 안해주는 이렇게 만들어 주는 트리가 인데요 그 이름은 자가 등의 어플이에요 그래서 자가 균이 엎드리는 다음 거에 설명할 게 어 이 아무튼 진짜 그래서 이진 탐색 피를 정리하자면 면접관이 물어봐요 이진 탐색 트리의 뭐냐고 어 그럼 저는 왼쪽 짜지는 부모보다 작고 오른쪽 잘익은 보다 큰 이진 트리 니까 이진 탐색 트리 입니다 인 탐색 피리는 사회 검색 삭제 가 오늘 트리 높이 로벤 에서 앤 만큼은 시간 복잡도를 같습니다 그래서 트리가 페어 되지 않기 위해서 자가 기병들이 를 사용 합니다 라고 대답하게 써요 그러면 적당히 자연스럽게 말하고 물어볼까요 뭐 그럼 자연과학의 녀 트리는 뭐예요 라고 물어보면 은 자 이제 다음을 공지 대답을 하면 되겠죠 자자 흔들면 트리는 어 아까 말했던 것처럼 트리가 안쪽으로 폐 안 되는 것을 봐서 이렇게 삽입을 하면 은 원래 이렇게 돼 있던건데 이거를 쪽으로 옮겨 주어 이거를 이걸 이쪽으로 옮겨 주고 이것을 이쪽으로 옮겨 줄 이거를 이쪽으로 오게 해주는 이런 어 트 리 를 전체적으로 개업 재배지 시켜주는 틀린데요 크게 a v 앱이 이고 레드 레드 블랙 이라는 트리가 있어요 이거는 그렇게 깊게 찰나 보는건 너무 전 깊게 들어간다 고 생각하구요 그래 이름 정도만 에어 주시면 될 것 같아요 그래서 어 자가 균형 틀린 여 가 뭐냐고 물어보면 저는 이진 탐색 트리 는 시간 복잡도가 트리의 높이에 따라 결정되므로 평형 될 경우 효율이 떨어집니다 그래서 페어 들지 않게 삽입과 삭제를 개선한 이진 평택 트리를 잘하고 역할이라고 합니다 장로 되는 avada 와 레드 블랙 트리가 있습니다 라고 말하겠어요 자 그러면 다음은 해시 할게요 자해 씨는 회 씨의 맵핑 에서 데이터를 저장하는 자료 구조 라고 제가 우선은 저건 왔는데요 어 예를 들어 볼게요 제가 어 3 4 5 라는 데이터를 리스트에 이렇게 저장을 했다고 저 께요 자 그러면은 뭐 이게 총 데이터가 앤 개라고 썼을 때 내가 이 검색을 할 때 되니까 5가 어디 있는지를 찾을 때 얼만큼의 시간 복잡도가 될까요 자 우선 삶을 찾고 아니죠 4 확인해 보고 아 니 죠 오늘 확인한 다음에 그 때 맞죠 이런식으로 리스트는 탐색할 때 5m 만큼 시간 복도가 되어서 아주 성능이 떨어지는 자 6주 고요 그래서 애쉬는 검색에 특화된 자료구조 해요 자 어떻게 되겠냐 며 는 해 씨는 우선은 가 이런 해시 벗기 시 라는 것을 저장을 해 놔요 가지고 있어요 그래서 내가 어떤 걸 찾을 때 이렇게 바로 찾을 수 있도록 이런 해시 벗기 슬프게 만들어 내요 그리고 내가 이해 c 버킷을 찾을 때 먼로 찾느냐 그도 이름을 해쉬 라고 해요 그래서 그 여옥이 를 예를 문은 0 1 이이가 각각의 해시 값이 라고 해 볼게요 그 이렇게 이바 분이 이를 가보니 를 씹어 킷이 라구요 그러니까 데이터가 들어가는 것을 자 그럼 이제 내가 이상 4 5를 여기에다 넣어놓는 거에요 자 어떤 시그널 그냥 저는 3 이것들을 3 으로 나눠서 나머지가 나머지 값을 기준으로 저장을 할 꺼예요 작품명 이렇게 먹게 되죠 3 은 여기에 저장이 되고 일은 여기에 저장이 되고 오는 여기에 저장 되죠 이런식으로 이렇게 저장 될 거에요 자 그럼 나는 어떻게 검색을 하면 되냐면 요 언 애가 5 를 찾고 싶어요 오늘 딴 5를 3으로 나누면 인해 금일 가서 찾으면 뭐가 있는 거에요 이런식으로 찾으면 시간 복잡도 어떻게 되어 자 우선 찾는곳 바로 일이죠 답 검색 1위에 5 일이에요 그리고 삽입 자 내가 6을 늘 거에요 유 불 널려 오면은 3으로 나눈 다음에 3으로 나눈 후 나머지가 0이니까 바로 에서 여기 대입을 넣으면 되죠 이것도 시간 복잡도 왜 일이에요 삭제와 창 화제도 왜 일이에요 이런식으로 구성되어 있는게 최씨 구요 이때 이 때 각각 넣어 책을 잠깐 맛있어요 말씀드리면 이 때의 이거 어케 이 키 해쉬 로 바꿔주는 2회씩 앞 뜰로 바꿔주는 것을 해 10번 션 이라고 해요 그리고 이 퍼 키세 2 이넘 버드 뭘까 이 대표하는 것들을 해시 라구요 해쉬 펑션 을 결과로 나온 것이 해시 값이 요괴 식각 그리 해씨 펑션 에 들어가는 이 숫자들을 히 라고 해요 그리고 이렇게 들어가는 데이터들을 이제 벨류 라구요 베이 you're 밸류 들이 이 버킷에 저장 되는 거죠 자기 가셨죠 자 그럼 은 이제 면접관이 plc 가 뭐에요 라고 물어보면 어떻게 대답하면 저는 제 회 씨는 회 씰 맵핑 하여 데이터를 저장하는 자료 구조 입니다 에키 는 회식 펑션 을 통해서 최씨를 종영된 다음에 벨리 우와 맵핑 되어서 버킷에 저장되게 됩니다 시간 복잡도 는 삽입 삭제 조회가 모두 5회 일에 시간 복잡도를 했습니다 라고 대답하게 써요 4 그러면 다음 회 씨의 충돌 회피 기법 1 기법을 해 볼게요 자 아까와 비슷한 상황이 있다고 가정해 볼게요 자 3 4 5 6을 입구는 저장을 한다 고 해 볼게요 자 똑같이 10번 션은 3으로 나눈 나머지 자금 어떻게 될까요 회 15 큰 크게 영어 개 예 2 가 있겠네요 자 그럼 우선 삼원장 할게요 3 여기 전략이 줘 자당 4 여기서 작업이죠 음 6 은 어디 저랑 되요 3으로 나눈 나머지가 0이 라 나요 여기 저장 되었는데 지금 상 있어요 이렇게 내 말 c 에 저장하려고 하는데 이미 있을 때 이게 여기 이렇게 충돌이 발생 하잖아요 층 부르 그래서 충돌 회피 기법 이에요 그래서 이렇게 헬시 벗기 슬 이미 데이터가 있을 때 그걸 어떻게 처리 아냐 가 회 c 충돌 회피 기법 이에요 그래서 크게 주 가지마 모르겠는데요 첫번째 오프너 드레싱은 다른 해시 값을 줄 압니까 이 0이 아니고 비어있는 이번에 이제 6을 저장한 이게 오프너 드레싱 이에요 다음 체인인 뭐냐면요 채 이닝 은 이렇게 3 하나만 조장하는 게 아니구요 2 링크드 리스트 로 깔 링크드 리스트는 어떤게 이렇게 연결되어 있는 리스트를 마라 거든요 그래서 여기에다가 6번을 10개의 주렁 스러운 다른거죠 그렇게 해서 충돌을 뿅 법은 오프너 드레싱과 체인이 있어요 4 그래서 정리를 하자면 면접관이 충돌 회피 기법이 뭐예요 라고 그러면 저는 내 충돌을 피기 법은 어 회 c 에서 이제 하나의 버킷을 여러 개의 데이터가 들어갈 때 그 충돌을 회피하는 방법으로 오프너 드레싱과 책임이 있습니다 오프너 드레싱은 다른 해시 값을 저장하는 보이고요 체인링 은 펫이 테이블이 원소 하나를 닦는 게 아니라 링크드 리스트를 담는 방법 입니다 라고 4 이렇게 자료구조를 마쳤구요 그러면 감사합니 나 이상 개발자 찾아보겠습니다