배열(Array)에 대해 설명해주세요.
배열은 같은 종류의 데이터 타입을 가진 원소들을 연속적인 주소상에 저장하는 데이터 구조입니다. 연속된 메모리 주소를 가지고 있기 때문에 캐싱이 좋다는 장점을 가지고 있습니다.
같은 종류의 데이터 타입만 가능한 이유는 무엇인가요?
데이터 타입에 따라 가지는 사이즈가 다른데, 배열의 경우 연속적인 주소상에 데이터를 저장하게되고, 이때 더 큰 데이터 타입의 데이터가 들어온다면 문제가 발생하기 때문에 같은 종류의 데이터 타입을 가집니다.
삽입, 삭제, 탐색 연산을 할때의 시간복잡도에 대해 설명해주세요.
삽입과 삭제의 경우 O(n)의 시간복잡도를 가집니다. 삽입의 경우 삽입 하는 공간을 확보하기 위하여 삽입 위치 뒤의 모든 원소를 옮겨야하고, 삭제를 할 경우 삭제한 위치 뒤의 모든 원소를 옮김으로써 빈 자리를 채워야하기 때문입니다.
반면 탐색의 경우 i번째 원소에 접근하기 위해서 첫 번째 원소의 주소 + 자료형의 크기 * i의 주소로 접근하면 되기 때문에 O(1)의 시간복잡도를 가집니다.
연결리스트(Linked List)에 대해 설명해주세요.
링크드 리스트는 다음 노드를 가리키는 포인터 값을 저장하고 있는 노드들의 집합입니다. 연속적인 주소상에 데이터를 저장하지 않고, 논리적인 주소로 데이터를 저장합니다.
배열과 링크드리스트의 차이점은 무엇인가요?
배열과 링크드리스트 모두 선형 데이터를 저장하는데 사용할 수 있지만 큰 차이가 있습니다.
배열은 크기가 고정되어 있기 때문에 미리 요소의 수에 대해 할당을 받아야 합니다. 그렇기 때문에 새로운 요소를 삽입하는 것에 비용이 많이 들게 됩니다. 그렇지만 특정 요소에 접근하는 비용은 적습니다.
반면 링크드리스트는 동적인 크기를 가지고 있기 때문에 삽입과 삭제가 용이합니다. 그렇지만 임의의 요소에 접근하는 것이 불가능하고, 각 노드에 대한 포인터를 저장하는 만큼 메모리 비용이 발생하게 됩니다.
삽입, 삭제, 탐색 연산을 할때의 시간복잡도에 대해 설명해주세요.
탐색의 경우 원하는 노드를 찾을때는 첫번째 노드부터 순차적으로 접근해야하기 때문에 O(n)의 시간복잡도를 가집니다. 그렇지만 삽입과 삭제 연산의 경우 O(1)의 시간복잡도를 가집니다. 삽입의 경우 이전 노드의 포인터를 삽입할 노드를 가리키게 하고, 삽입할 노드의 포인터를 그 다음 노드를 가리키게 하고, 삭제의 경우 이전 노드의 포인터를 삭제할 노드의 그 다음 노드를 가리키게 할 수 있습니다.
링크드 리스트를 이용해서 구현할 수 있는 다른 자료구조는 무엇이 있나요?
스택, 큐, 양방향 링크드 리스트들을 구현할 수 있을 것 같습니다.
Array & ArrayList & LinkedList에 대해 설명해주세요.
Array는 선언할 때 크기와 데이터 타입을 지정하는 자료구조 입니다. 메모리 공간에 할당할 사이즈를 미리 정해놓게 됩니다. 그렇기 때문에 데이터를 추가하거나 삭제할 때 매우 비효율 적이며, 새로운 크기의 Array를 선언해 요소를 옮기는 과정이 필요하기 때문에 O(n)의 시간복잡도를 가집니다. 그렇지만 index가 존재하기 때문에 특정 요소에 빠르게 접근 할수 있고, O(1)의 시간 복잡도를 가집니다.
ArrayList는 Array와 같이 크기를 정하지 않기 때문에 데이터를 추가하거나 삭제하는데 한계가 없기 때문에 O(1)의 시간 복잡도를 가집니다. 그렇지만 중간 요소를 삭제하거나, 중간에 삽입할 때에는 각 요소의 위치를 변경하는 과정이 필요하기 때문에 O(n)의 시간 복잡도를 가집니다.
LinkedList는 다음 노드를 가리키는 포인터 값을 저장하고 있는 노드들의 집합입니다. 때문에 데이터의 중간에 삽입 및 삭제를 하더라도 이전 노드와 다음 노드의 포인터를 수정하면 되기때문에 O(1)의 시간 복잡도를 가집니다. 그렇지만 LinkedList의 특정 요소에 접근하고자 한다면 처음 노드부터 순차적으로 검색해야 하기 때문에 O(n)의 시간 복잡도를 가집니다.
스택 & 큐에 대해 설명해주세요.
스택
스택은 입력과 출력이 한 곳으로 제한되어 있는 구조로 Last In First Out, 후입선출, 가장 나중에 들어온 것이 가장 먼저 나오는 구조를 가지고 있습니다.
보통 원소를 넣는 연산을 Push, 원소를 빼는 연산을 pop이라 부릅니다.
스택의 사용 사례는 무엇이 있나요?
보통 함수의 콜스택, 웹 브라우저의 방문 기록(뒤로가기), 실행 취소, 후위 표기법을 계산할때 사용됩니다.
큐
큐는 입력과 출력을 양쪽 끝으로 제한한 구조로 First In First Out, 선입선출, 가장 먼저 들어온 것이 가장 먼저 나오는 구조를 가지고 있습니다.
보통 원소를 넣는 연산은 enqueue, 빼는 연산을 dequeue라 부르며, 들어오는 곳을 front, 나가는 곳을 rear라고 합니다.
큐의 사용 사례는 무엇이 있나요?
보통 대기열이 존재하는 버퍼, BFS를 구현할 때 큐가 사용됩니다.
스택 2개로 큐를 만드는 방법에 대해 설명해주세요.
하나의 스택은 삽입을 위해 사용하고, 다른 스택은 삭제 및 탐색을 위해 사용합니다.
원소 1, 2, 3 을 차례대로 넣고 1, 2, 3 의 순서대로 빼내고 싶다면, 먼저 첫번째 스택에 1, 2, 3을 넣습니다. 이후에 첫번째 스택에서 pop을 하면 3, 2, 1의 순서대로 나오는데, 그 순서대로 다시 두번째 스택에 넣습니다.
이후 두번째 스택에서 다시 pop을 하면 큐와 같이 1, 2, 3의 순서로 나오게 됩니다.
삽입과 같은 경우 O(1)의 시간복잡도를 갖지만, 삭제와 같은 경우 최악의 경우 스택을 전부 비우고, 다시 다른 스택에 push한 후 pop을 해야하므로 O(n)의 시간복잡도를 갖습니다.
큐 2개로 스택을 만드는 방법에 대해 설명해주세요.
첫번째 방법
하나의 큐는 메인 큐로 사용하고, 다른 큐는 임시로 데이터를 저장하기 위해 사용합니다.
원소 1, 2, 3을 차례대로 넣고 3, 2, 1의 순서대로 빼고 싶다면, 먼저 첫번째 큐에 1, 2, 3을 넣습니다. 이후에 첫번째 큐에서 원소가 하나 남을때까지 dequeue를 해 임시큐에 enqueue하고, 하나의 원소가 남는다면 dequeue해 result에 저장합니다. 이때 3이 result에 저장됩니다.
이후 임시큐에서 다시 메인큐로 남은 1, 2를 enqueue하고, 다시 이전과 같이 하나의 원소가 남을때까지 임시큐로 원소를 이동시키고, 하나의 원소가 남든다면 그 원소를 result에 추가합니다. 이때 2가 result에 저장되고, 원소는 3, 2, 1의 순서로 나오게 됩니다.
삽입과 같은 경우 O(1)의 시간복잡도를 갖지만, 삭제외 경우 최악의 경우 원소가 하나 남을때까지 메인 큐의 모든 원소를 비워야 하기 때문에 O(n)의 시간복잡도를 갖습니다.
두번째 방법
똑같이 하나의 큐는 메인 큐로 사용하고, 다른 큐는 임시로 데이터를 저장하기 위해 사용합니다.
원소 1, 2, 3을 차례대로 넣고 3, 2, 1의 순서대로 빼고 싶다면, 메인 큐에 원소가 입력될 때, 기존 메인 큐에 존재하는 아이템들을 순서대로 서브큐에 담습니다. 이후 메인 큐에 원소가 입력되고, 서브 큐에 있던 아이템을 순서대로 메인큐에 다시 담는 과정을 반복합니다.
이런 경우 삽입을 할때 메인큐에서 서브큐로 모든 원소를 이동하고, 다시 메인큐로 이동하는 과정이 필요하기 때문에 O(n)의 시간복잡도를 갖지만, 삭제의 경우 O(1)의 시간복잡도를 갖습니다.
시간 복잡도를 유지하면서, 배열로 스택과 큐를 구현할 수 있을까요?
스택과 같은 경우, 배열의 끝에서 push와 pop 작업을 수행함으로써 구현할 수 있습니다.
큐의 경우, front와 rear라는 변수를 0으로 선언합니다. 이후 삽입의 경우 배열에 원소를 push한 뒤 rear를 1 증가, 삭제의 경우 첫번째 원소를 삭제한 뒤 front를 1 증가시킴으로써 구현할 수 있습니다.
다만 이렇게 될 경우 배열이 비어있음에도 불구하고 front와 rear이 같아지면서 배열에 정상적으로 원소를 추가하지 못하는 상황이 올 수 있습니다.
하지만 배열의 크기가 변경되야 하는 경우라면, 데이터를 새로운 배열로 복사해야하므로 비효율적일 수 있습니다.
Prefix, Infix, Postfix에 대해 설명하고, 이를 스택을 활용해 계산하는 방법에 대해 설명해주세요.
prefix, infix, postfix는 수식을 표기하는 기법입니다.
prefix
전위 표기법이라 불리며 연산자가 피연산자의 앞에 위치하는 방식입니다.
수식을 뒤에서부터 읽으며, 피연산자를 만나면 스택에 push, 연산자를 만나면 스택에서 두개의 피연산자를 pop하여 계산한후 그 결과를 다시 스택에 push 합니다.
infix
중위 표기법이라 불리며 연산자가 피연산자의 사이에 위치하는 방식입니다.
infix를 스택을 이용해 postfix로 변환할 수 있습니다.
피연산자가 나오면 바로 출력, 연산자가 나오면 스택의 맨위에 있는 연산자와 우선순위를 비교합니다.
- 맨위의 연산자가 현재 연산자보다 우선순위가 높거나 같으면 스택 맨 위의 연산자가 현재 연산자보다 우선순위가 작을 때까지 pop하여 출력합니다.
- 만약 현재 연산자가 우선순위가 더 높으면 스택에 push
닫는 괄호가 나오면 열린 괄호가 나올 때까지 스택에서 pop하여 출력합니다.
수식을 모두 읽은 후 스택에 남아 있는 연산자를 모두 pop하여 출력합니다.
postfix
후위 표기법이라 불리며 연산자가 피연산자의 뒤에 위치하는 방식입니다.
수식을 앞에서부터 읽으며 피연산자를 만나면 스택에 push합니다.
연산자를 만나면 스택에서 두개의 피연산자를 pop하여 계산한 후, 그 결과를 다시 스택에 push합니다.
Deque를 구현하는 방법에 대해 설명해주세요.
deque는 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, 배열과 링크드리스트를 통해 구현할 수 있습니다.
배열의 경우 덱의 양쪽 끝에서 삽입 삭제를 하기 위해 인덱스를 이용한 원소 이동이 필요하며, 삽입/삭제 연산이 O(n)의 시간 복잡도를 가집니다.
링크드 리스트의 경우 양쪽 끝을 가리키는 두개의 포인터 (head, tail)을 설정하고, 해당 위치에서 삽입과 삭제를 수행함으로써 O(1)의 시간 복잡도를 가집니다. 그렇지만 각 노드에 포인터가 추가되므로 메모리 사용량이 늘어납니다.
힙에 대해 설명해주세요.
완전 이진 트리의 일종으로, 우선 순위 큐를 위하여 만들어진 자료 구조입니다.
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 구조입니다.
max heap과 min heap이 있는데, max heap은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 형태이고,
min heap은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리 형태입니다.
일종의 반정렬 상태를 유지하기 때문에 max heap을 예로 들자면 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도의 정렬을 유지합니다.
시간 복잡도를 기준으로 설명해주세요.
최댓값, 최솟값을 도출 하는데 걸리는 시간복잡도는 root의 원소를 pop 하기 때문에 O(1) 입니다. 그렇지만 heap 자료 구조를 유지하기 위해 Heapify 과정이 필요하고, 이 경우 O(logN)의 시간복잡도를 가집니다.
Heapify는 왜 O(logN)인가요?
현재 노드와 자식 노드 간의 값을 비교하고, 자식이 더 크면 두 노드를 교환하는 과정을 반복합니다. 이 과정이 O(1)의 시간복잡도를 가지는데, Heap의 높이는 logN이기 때문에 모든 높이에서의 비교를 진행하면 O(logN)의 시간복잡도를 갖게 됩니다.
완전 이진 트리란 무엇인가요?
이진 트리란 자식 노드가 두개 이하인 트리를 말하는데, 완전 이진 트리란 상 > 하 좌 > 우 순으로 데이터가 차있는 이진 트리를 뜻합니다. 이는 배열로 구현이 가능합니다.
힙을 배열로 구현한다고 가정하면 어떻게 값을 저장할 수 있을까요?
힙의 루트 노드를 배열의 인덱스 1로 시작하며, 각 배열에 힙 노드들을 레벨 순서대로 저장할 수 있습니다.
부모 인덱스는 자식 노드의 인덱스를 2로 나눈 몫, 왼쪽 자식 인덱스라면 부모 인덱스 * 2, 오른쪽 자식 인덱스는 부모 인덱스 * 2 + 1 로 함으로써 구현할 수 있습니다.
힙의 삽입 삭제 방식에 대해 설명하고, 왜 이진 탐색 트리와 달리 편향이 발생하지 않는지 설명해주세요.
편향이란 트리가 왼쪽이나 오른쪽으로 치우친 형태를 가진 것을 말합니다. 이러한 트리는 탐색, 삽입, 삭제 등의 연산이 비효율적으로 동작할 수 있습니다.
삽입의 경우 힙의 마지막 노드에 값을 추가하고, 부모 노드와 현재 노드의 값을 비교하며 swap하는 과정을 통해 Heapify를 진행합니다.
삭제의 경우도 마찬가지로 힙에서 루트 노드를 삭제한 후, 마지막 노드를 루트로 옮기고 루트 노드와 자식 노드의 값을 비교하며 최대힙이라 가정했을 때, 두 자식 모두 부모 노드보다 값이 크다면, 자식 노드 중 더 큰 값과 swap하는 과정을 통해 (최소힙이라면 더 작은 값과 swap) Heapify를 진행합니다.
힙은 완전 이진 트리의 형태를 유지하는데, 이는 노드가 왼쪽부터 오른쪽으로 차례대로 채워진 형태를 의미합니다. 때문에 새로운 요소가 삽입되거나 삭제되더라도 편향이 발생하지 않습니다.
힙 정렬의 시간 복잡도는 어떻게 되나요? Stable한가요?
힙 정렬은 n개의 원소를 정렬할 때 최소, 혹은 최대의 원소를 추출하고, 다시 heapify 하는 과정을 반복하면서 O(nlogn)의 시간 복잡도를 가집니다.
Stable이란 동일한 키 값을 가진 요소들이 상대적 순서를 유지하는 특성을 말하는데, 같은 값을 가진 요소들이 상대적 위치를 유지하지 않기 때문에 안정적인 정렬 방법이 아닙니다.
이유가 뭔가요?
오름차순으로 정렬을 시도할 때, max heap을 통해 루트 노드로 가장 큰 원소를 추출한 뒤 맨 끝으로 이동시키는 과정을 수행합니다.
그 과정에서 값이 같은 요소들이 존재한다면, 원래 가지고 있던 순서대로 추출되지만, 먼저 추출될수록 뒤로가는 형태이기 때문에 추후에 정렬된 형태를 본다면 기존의 상대적 순서가 뒤집어진 형태로 정렬되게 됩니다.
트리 (Tree)에 대해 설명해주세요.
트리란 Node와 Edge로 이루어진 계층 구조를 표현할 수 있는 자료구조를 뜻합니다.
다양한 트리가 존재하는데, 이진 트리, 이진 탐색트리 등이 있습니다.
트리의 순회 방법에 대해 알고 계신가요?
트리의 순회 방법에는 전위 순회, 중위 순회, 후위 순회가 있습니다.
전위 순회란, 각 루트를 순차적으로 먼저 방문하는 방식으로, 루트 → 왼쪽 자식 → 오른쪽 자식의 순서로 방문합니다.
중위 순회란, 왼쪽 자식 → 루트 → 오른쪽 자식 순으로 방문합니다.
후위 순회는 왼쪽 자식 → 오른쪽 자식 → 루트 순으로 방문합니다.
이 외에도 계층 방식이란 것이 존재하는데 이는 루트부터 계층별로 방문하는 방식을 뜻합니다.
이진 트리는 무엇인가요?
자식 노드가 두개 이하인 트리를 말하며, 포화 이진 트리, 완전 이진 트리, 정 이진 트리가 존재합니다.
포화 이진 트리는 모든 레벨에 대해 노드가 꽉 차있는 이진 트리를 말하며,
완전 이진 트리는 상 → 하, 좌 → 우 순으로 데이터가 차있는 이진 트리를 말하고, 배열로 구현이 가능하다는 특징을 가지고 있습니다.
정 이진 트리는 자식 노드가 0개 또는 2개인 이진 트리를 말합니다.
그래프와 트리의 차이는 무엇인가요?
트리는 그래프의 일종으로, 그래프는 정점과 간선의 집합으로 이루어진 구조를 말합니다. 싸이클을 생성하지 않고 계층 관계를 갖는 구조를 트리라 일컫습니다.
이진 탐색 트리에 대해 설명해주세요.
이진 탐색 트리는 이진 트리의 일종으로, 중복된 노드가 없고, 모든 노드가 자신의 값이 왼쪽 자식의 값보다 크고, 오른쪽 자식의 값보다 작다는 조건을 갖는 트리를 말합니다.
중복된 노드가 없어야 하는 이유는 무엇인가요?
이진 탐색 트리는 효율적인 탐색을 위해 만들어진 자료구조인데, 중복이 많다면 트리 구조를 사용할 시 검색 속도가 느려져 트리를 사용하는 효용성이 떨어지기 때문입니다.
이러한 경우에는 차라리 트리에 노드마다 중복된 갯수를 가지는 count라는 변수를 두는 것이 효율적입니다.
이진 탐색 트리에서 중위 순회를 한다면, 이는 어떤 의미를 갖고 있을까요?
중위 순회는 왼쪽 자식의 값, 본인의 값, 오른쪽 자식의 값 순으로 탐색을 진행하게 됩니다. 그런데 이진 트리또한 본인의 값이 왼쪽 자식의 값보다 크고, 오른쪽 자식의 값보다 작다는 조건을 만족하기 때문에, 중위 순회를 하게 된다면 오름차순으로 정렬된 데이터를 갖게 됩니다.
이진 탐색 트리에서 삽입, 삭제, 탐색 연산의 시간복잡도가 어떻게 되나요? 왜 그런 시간 복잡도가 도출되나요?
삽입, 삭제, 탐색 모두 트리의 높이에 따른 시간 복잡도를 갖게 됩니다. 만약 편향되지 않은 균형 잡힌 트리라면 O(logN)의 시간 복잡도를 갖지만, 편향되는 경우 O(N)이 되게 됩니다.
이진 탐색 트리의 한계점은 무엇이 있을까요?
편향될 수 있고, 편향시 모든 연산이 O(N)이 됨으로써 비효율적이게 됩니다. 그래서 트리의 균형 여부가 중요한데, 이러한 균형을 맞춘 구조가 AVL Tree 입니다.
어떨 때 편향이 발생하나요?
이미 정렬되어진 데이터를 삽입할때 편향이 발생합니다.
AVL 트리에 대해 설명해주세요
왼쪽 노드의 높이, 오른쪽 노드의 높이의 차이가 1 이하인 트리를 말하며, 삽입, 삭제, 탐색 모두 O(logN)의 시간복잡도를 가집니다. 삽입이나 삭제시 경로상 모든 노드들의 균형 인수를 업데이트, 회전 연산을 통해 균형을 맞추게 됩니다.
Red Black 트리에 대해 설명해주세요
균형 이진 탐색 트리의 일종으로, 각 노드는 Red, Black 색상을 가지게 됩니다. 노드의 색깔이 Red라면 두 자식의 색깔은 Black이어야 합니다. 각 노드로부터 리프 노드까지의 단순 경로는 모두 같은 수의 black 노드를 포함하게 됩니다. 이를 해당 노드의 black-height라고 합니다.
루트 노드부터 leaf 노드까지의 최소 경로와 최대 경로의 크기 비율이 2 이하일때, 균형된 상태라고 합니다.
이진 탐색 트리의 삽입, 삭제는 어떤식으로 이루어지나요?
삽입의 경우, 루트 노드와 비교하여 작으면 왼쪽, 크면 오른쪽 자식 노드를 탐색합니다. 이 과정을 반복하며 노드를 추가할 위치를 찾게 되면, 해당 위치에 값을 삽입합니다.
삭제의 경우 루트 노드와 비교하여 작으면 왼쪽, 크면 오른쪽 자식 노드를 탐색하는 것은 같습니다, 이후 삭제할 노드를 찾았을 때 해당 노드가 자식이 없는 leaf 노드라면 그냥 삭제하고, 자식이 1개인 노드라면 지워진 노드에 자식을 올립니다. 만약 자식이 2개라면 삭제할 노드와 가장 근사한 값을 가진 노드를 올립니다.
해시 (Hash)에 대해 설명해주세요.
해시자료 구조는, 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것을 말합니다. 해시 함수를 통해 키 값을 변환하고, 이를 인덱스로 사용할 수 있는 구조입니다.
삽입, 삭제, 탐색 연산의 시간 복잡도가 어떻게 되나요?
대부분의 삽입, 삭제, 탐색의 연산의 경우 O(1)의 시간 복잡도를 가집니다. 그러나 만약 충돌이 일어나면 최악의 경우 O(N)의 시간 복잡도를 가집니다.
왜 충돌이 일어날 경우 O(N)의 시간 복잡도를 가지나요?
개방 주소법을 통해 해시 충돌 현상을 다루고자 한다고 가정해보겠습니다. 해시 충돌이 일어나게 된다면 충돌 난 인덱스에 저장하지 않고 다른 인덱스에 저장하기 위해 인덱스를 변경하게 계속 변경하게 되는데, 이때 최악의 경우 테이블을 다 돌게 되기 때문에 O(N)의 시간복잡도를 가지게 됩니다. (N은 테이블의 크기)
해시 충돌 현상에 대해 설명해주세요.
해시 함수는 다른 값임에도 불구하고 동일한 인덱스로 변환될 수 있는데, 이러한 현상을 해시 충돌이라고 합니다.
해시 충돌을 어떤 방식으로 해결하나요?
크게 개방 주소법과 분리 연결법으로 나뉩니다. 개방 주소법의 경우 충돌 난 인덱스에 저장하지 않고 다른 인덱스에 저장하는 방법인데, 선형 탐사법, 제곱 탐사법, 이중 해싱이 있습니다.
선형 탐사법은 충돌이 발생했을 때 정해진 칸 만큼 인덱스를 증가시켜 저장하는 방법입니다. 이렇게 저장을 하게 됨녀 특정 해시값 주변이 모두 채워져 있는 현상이 발생할 수 있다는 단점이 있습니다. 이러한 현상을 일차 군집화라고 합니다.
제곱 탐사법은 인덱스를 증가시키는 방식이 고정폭이 아닌 제곱으로 늘어나는 방식으로 하여 저장하는 방법입니다. 이렇게 저장을 하게되면 선형 탐사법보다 데이터의 밀집도가 낮아지게 됩니다. 하지만 이또한 해시 값으로 1이 많이 발생하게 된다면, 충돌이 계속 발생하게 됩니다. 이러한 현상을 이차 군집화라고 합니다.
이중 해싱은 해시 함수를 이중으로 사용하는 것으로, 하나는 최초 해시를 얻을 때 사용하고, 다른 하나는 충돌이 일어났을 경우 탐사 이동폭을 얻기 위해 사용하는 방식입니다. 이렇게 한다면 일차 군집화와 이차 군집화 현상을 해결할 수 있습니다.
분리 연결법(체이닝)은 충돌이 난 인덱스에 연결 리스트와 같이 자료구조로 연결하여 저장하는 방법을 말합니다. 이러한 방식으로 저장하게 된다면 제한 없이 계속 데이터를 연결 할 수는 있지만 메모리 문제가 발생할 수 있습니다.
개방 주소법으로 해시 충돌을 해결했을 때, 이렇게 저장된 원소를 삭제하려면 어떻게 해야하나요?
단순히 버킷에서 값을 삭제하게 된다면 이후에 탐색이 불가능해질 수 있습니다. 때문에 버킷을 세 종류로 나누어서 탐색을 해야합니다. 한번도 사용하지 않은 버킷, 이전에 사용되었지만 지금은 사용되지 않는 버킷, 현재 사용중인 버킷으로 나누고, 버킷을 삭제하고 나서, 해당 버킷을 지금은 사용하지 않는 버킷으로 바꿉니다.
어떻게 하면 충돌이 최대한 적은 해시 함수를 설계할 수 있을까요?
해시 함수의 출력 범위를 해시 버킷의 크기와 비슷하게 만들어야 합니다.
또한 해시 함수에 사용하는 수는 최대한 소수를 사용하는 것이 좋습니다. (두 수 사이의 공약수를 최대한 줄이는 것이 좋다.)
본인이 사용하는 언어는 어떤 방식으로 해시 충돌을 처리하나요?
엔진에 따라 차이는 존재하지만 V8엔진의 경우 개방 주소법을 사용하고, 그 중 선형 탐사 방식을 사용하는 것으로 알고 있습니다.
트라이 (Trie)에 대해 설명해주세요.
문자열을 작은 캐릭터로 쪼개, 순차적으로 트리 자료구조에 저장하는 방식입니다.
정수형에서 이진 탐색 트리를 이용하지만 시간 복잡도가 O(logN)이지만, 문자열에 적용한다면, 문자열의 최대 길이가 M일때 O(M*logN)이 되게 됩니다. 하지만 트라이를 사용하게 되면 O(M)으로 문자열 검색이 가능합니다.
장단점이 뭐가 있을까요?
문자열을 빠르게 검색할 수 있고, 공통 접두사가 많은 경우 메모리 상으로도 효율적으로 관리할 수 있다는 장점이 있습니다. 그렇지만 공통 접두사가 적은 상황에는 많은 메모리가 소모될 수 있고, 복잡한 조건으로 검색한다면 구현이 어려워지게 됩니다.
실제로 구현한다면, 각 노드에 어떤 변수가 들어가게 될까요? 실제 사용하는 언어를 기준으로 말씀해주세요.
캐릭터 값을 저장하는 string 타입의 변수, 그리고 자식 노드들을 가리키는 dictionary 타입의 변수, 그리고 해당 노드가 마지막 글자인지의 여부를 저장하는 boolean 타입의 변수를 둘 것 같습니다.
삽입, 삭제, 탐색 연산의 시간 복잡도가 어떻게 되나요?
문자열의 길이가 N이라고 할 때, 특정 문자열의 저장 여부를 판단할 때 O(N), 삽입할 때 O(N), 삭제할때도 O(N)의 시간복잡도를 가집니다.
일반적인 배열에 문자열을 저장할 경우 저장된 문자열의 수가 M, 문자열의 길이가 N이라면 저장여부 판단은 O(NM)이 되고, 삽입은 O(1)의 시간복잡도를 가집니다.
그렇다면 어떤 작업을 할때 유용할까요?
문자열이 존재하는지, 잦은 조회를 할때 유용합니다.
예를 들어보자면 어떤게 있을까요?
자동완성, 또는 사전 기능을 구현할 때 Trie가 사용될 것 같습니다. 또한 라우팅 테이블에 저장된 IP주소를 Trie로 저장해서 빠른 접근이 가능할 수 있을 것 같습니다.
B-Tree & B+ Tree에 대해 설명해주세요.
B-Tree는 이진 트리를 확장해 더 많은 수의 자식을 가질 수 있게 일반화 시키고 균형된 트리 구조입니다. 그렇기 때문에 탐색에 있어서 O(logN)을 보장할 수 있습니다. 일반적으로 각 노드 내에서의 key는 오름차 순으로 정렬됩니다.
B+Tree의 경우는 기존의 B-Tree와 유사하지만, Inner Node는 Key만 저장되고 Leaf Node에는 키와 데이터를 저장됩니다. 또한 각 Leaf Node들이 링크드리스트로 연결되기 때문에, 풀 스캔, 포함문으로 검색했을 시 보다 더 높은 성능을 가집니다. 또한 Inner Node에 데이터를 넣지 않기 때문에, B-Tree보다 Inner Node의 용량이 작아 하나의 디스크에 더 많은 Inner Node를 배치할 수 있어 키 탐색에 있어 유리합니다.
B+Tree가 B-Tree에 비해 반드시 좋다고 할 수 있을까요?
B+Tree는 리프노드에만 데이터를 저장하고, 그 각각의 leaf node 들이 포인터로 연결되어 있기 때문에 데이터를 순차적으로 검색할때 유리합니다. 그렇지만 Inner node에 데이터가 저장되어 있지 않기 때문에 데이터를 찾고자 한다면 무조건 leaf node까지 도달하는 연산이 필요해 시간이 오래 걸릴 수 있다는 단점이 있습니다.
DB에서 B-Tree/B+Tree를 사용하는 이유가 있을까요?
DB는 대량의 데이터가 저장되는데, 이러한 데이터들은 메모리보다 블럭 단위로 입출력하는 하드디스크 or SSD에 저장되어야 합니다. 그런데 하드 디스크에 접근해 데이터를 불러오는 시간은 메모리 작동 시간에 비해 매우 크기 때문에, 최대한 디스크 접근 횟수를 줄이는 것이 필요합니다.
디스크 접근 횟수를 줄인다는 것은 노드의 접근 횟수를 줄이는게 좋다는 것이고, 이는 곧 트리의 높이를 줄이는 것이 좋다는 뜻이 됩니다. B Tree 같은 경우 한 노드에 두개 이상의 키를 저장할 수 있기 때문에, 이진 트리에 비해 트리의 높이를 획기적으로 줄일 수 있습니다.
B*Tree에 대해 설명해주세요.
B*Tree란 B-Tree의 개량형 자료구조로, 순차 탐색 문제를 해결하기 위해 나온 B+Tree와는 달리, 메모리 낭비와 보조 연산 문제를 해결하기 위한 자료구조입니다. 또한 B-Tree의 삽입/삭제 연산에서 분할과 병합 연산을 최소로 줄이기 위해 고안된 자료구조입니다.
B* Tree는 B-Tree와 다르게 모든 노드가 2/3이상 채워져야하며 (B-Tree는 1/2 이상), B-Tree는 노드가 가득 차면 분열하여 새로운 Node를 만드는데, B*Tree는 이웃한 형제 Node로 재배치함으로써 분열을 최소화 합니다.