자료구조 면접 대비 질문 리스트업

1. 가장 중요한 건, 어떤 경우(목적)일 때 어떤 자료구조를 사용하면 좋은지를 알고 있는 것
2. 본인의 주 언어 자료구조 내부구현이 무엇으로 되어있는지 알고 가기

 

자료 구조를 왜 사용할까요?

메모리를 효율적으로 사용하면서 데이터를 빠르고 안정적으로 처리하기 위해 필요합니다. 특정 상황에서 유용하게 사용할 수 있는 자료구조를 선택하는 것이 중요합니다.

 

 

자료를 정리할 때 가장 중요한 것은 무엇일까요?

데이터와 목적에 따라 다르다고 생각합니다. 처리 시간, 크기, 활용 빈도, 갱신의 정도와 보안 등 고려해야할 점들 중 상황에 따라 우선순위를 정해야한다고 생각합니다.

 

 

1) 배열 vs 링크드 리스트

구현상 어떤 특징이 있는지, 시간복잡도가 어떤지, 어떤 경우에 사용하면 좋은지
위 3개 포인트만 제대로 전달하기!

 

 

Array는 어떤 자료구조 인가요?

연관된 데이터를 연속된 메모리에 미리 할당된 크기만큼 저장하는 자료구조입니다. 때문에 고정된 저장 공간을 갖고, 인덱스로 접근이 가능하다는 특징을 갖습니다.

 

배열의 접근이 어떻게 이루어지길래 O(1)이 될까요?

base-address + offset 연산으로 특정 인덱스의 주소를 바로 계산할 수 있습니다.

base-adress는 배열의 시작 주소이고, offset은 (자료구조의 크기 * index)로 계산합니다.

 

미리 예상한 것보다 더 많은 수의 data를 저장하느라 Array의 size를 넘어서게 됐다. 어떻게 해결할 수 있을까?

1. 기존의 size보다 더 큰 Array를 선언해 데이터를 옮겨 할당합니다. 모든 데이터를 옮긴 후에는 기존 Array는 메모리에서 삭제하면 됩니다.
2. 다른 방법으로는, size를 예측하기 쉽지 않다면 Array 대신 Linked List를 사용함으로써 데이터가 추가될 때마다 메모리 공간을 할당받는 방식을 사용할 수 있습니다.

---

Dynamic Array 는 어떤 자료구조 인가요?

배열을 선언한 후에 resize를 통해 유동적으로 size를 조절해 데이터를 저장하는 자료구조입니다. 배열의 fixed-size 한계점을 보완할 수 있는 자료구조입니다.

 

동적배열은 어떻게 Resizing 하나요?

데이터를 추가하다가 기존 할당된 메모리를 초과하면 사이즈를 늘린 배열을 선언하고 그곳으로 모든 데이터를 옮깁니다. 보통 기존 size의 2배로 resize 합니다.

 

동적배열의 append 연산의 시간복잡도와 그 이유는?

Amortized O(1) 입니다.

append 연산은 O(1)의 시간복잡도를 갖지만 데이터를 추가하다가 resize가 필요한 경우 데이터를 옮겨야 하기 때문에 O(N)의 시간 복잡도를 갖게 됩니다. 하지만 이는 가끔씩 일어나는 일이기 때문에 평균적으로 O(1)이라고 볼 수 있습니다.

---

Linked List에 대해 설명해주세요.

링크드 리스트는 노드라는 구조체로 이루어져 있고, 각 노드는 데이터와 다음 노드의 주소를 저장해 물리적으로는 비연속적이지만 논리적으로는 연속성을 갖는 자료구조입니다. 데이터가 추가 되는 시점에서 메모리를 할당하기 때문에 메모리를 효율적으로 사용할 수 있습니다.

 

⭐ Array 와 Linked list를 비교해서 설명해주세요

Array와 Linked List의 가장 큰 차이점은 메모리에 저장되는 방식과 이에 따른 operation의 연산 속도(time complexity)

Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조입니다. 반면 Linked List는 메모리 상에서는 연속적이지 않지만, 각가의 원소가 다음 원소의 메모리 주소값을 저장해놓음으로써 논리적 연속성을 유지합니다.

그래서 각 operation의 시간복잡도가 다릅니다. 데이터 조회는 Array의 경우 O(1), Linked List는 O(N)의 시간복잡도를 갖습니다. 삽입/삭제는 Array는 O(N), Linked List 는 O(1) 시간 복잡도를 갖습니다.

따라서 얼마만큼의 데이터를 저장할 지 미리 알고 있고, 조회를 많이 한다면 Array를 사용하는 것이 좋습니다. 반면에 몇 개의 데이터를 저장할 지 불확실하고 삽입/삭제가 잦다면 Linked List를 사용하는 것이 유리합니다.

 

Array와 Linked List의 Memory Allocation은 언제 일어나며, 메모리의 어느 영역을 할당받나요?

배열은 컴파일 단계에서 스택 영역에 메모리를 할당 받고,

링크드 리스트는 런타임 단계에서 새로운 노드를 추가할 때마다 힙 영역에 메모리 할당이 일어납니다.

 

Dynamic Array와 Linked List를 비교해서 장단점을 설명해주세요.

Linked List와 비교했을 때 Dynamic Array의 장점은 데이터 접근과 할당이 O(1)로 굉장히 빠르고, 맨 뒤에 데이터를 추가하거나 삭제하는 것이 상대적으로 빠르다는 점입니다.

Linked List와 비교했을 때 Dynamic Array의 단점은 데이터를 맨 끝이 아닌 곳에 삽입/삭제 할 때 O(N)으로 느리고, resize를 해야할 때 현저히 낮은 performance가 발생한다는 점입니다. 또한, 필요한 것 이상의 memory 공간을 할당받아 낭비되는 공간이 발생합니다.

 

 

2) 스택 vs 큐

코딩테스트에서는 굉장히 중요한 자료구조지만, 면접에서 단독으로 물어보는 경우는 많이 없다. 우선순위큐를 잘 답하기 위해서는 구현 방법과 operation의 시간복잡도를 잘 설명할 수 있어야 한다.

 

 

Stack은 어떤 자료구조인가요?

Stack은 마지막에 들어온 데이터를 먼저 내보내는 후입선출의 자료구조입니다. 마지막 원소를 가리키는 top을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠릅니다. 하지만 top 위치 외의 데이터에 접근할 수 없어 탐색이 불가능하다는 단점을 갖습니다.

 

Queue는 어떤 자료구조인가요?

Queue는 처음 들어온 데이터를 먼저 내보내는 선입선출 자료구조입니다. 첫 원소를 가리키는 front와 마지막 원소를 가리키는 rear 를 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠릅니다. 하지만 중간에 위치한 데이터에 대한 접근이 불가능하다는 단점을 갖습니다.

 

원형큐(circular queue)는 무슨 자료구조인가요?

선형 큐의 경우 삽입과 삭제를 반복하면 한 번 데이터를 삽입/삭제한 위치를 재사용하지 않는 문제가 발생합니다. 이 문제를 해결하기 위해  앞과 뒤가 연결된 원형 구조를 갖는 큐를 원형 큐라고 합니다.

 

큐 구현할 때 Array-Base 와 List-Base의 경우 어떤 차이가 있나요?

두 가지 종류의 자료구조로 queue를 구현을 하더라도 enqueue와 dequeue는 모두 O(1)의 시간복잡도를 갖습니다. 하지만 Array-Base의 경우 전반적으로 performance가 더 좋지만 resize가 필요한 worst case의 경우에는 훨씬 더 느릴 수 있습니다. List-Base의 경우에는 enqueue를 할 때마다 memory allocation을 해야 하기 때문에 전반적인 runtime이 느릴 수 있습니다.

---

Stack 두 개를 이용하여 Queue를 구현해 보세요

queue의 enqueue()를 구현할 때 첫 번째 stack을 사용하고, dequeue()를 구현할 때 두 번째 stack을 사용하면 queue를 구현할 수 있습니다. 편의상 enqueue()에 사용할 stack을 instack이라고 부르고 dequeue()에 사용할 stack을 outstack이라고 칭하겠습니다. 두 개의 stack으로 queue를 구현하는 방법은 다음과 같습니다.

1. enqueue() :: instack에 push()를 하여 데이터를 저장합니다.
2. dequeue() ::
   1. 만약 outstack이 비어 있다면 instack.pop() 을 하고 outstack.push()를 하여 instack에서 outstack으로 모든 데이터를 옮겨 넣습니다. 이 결과로 가장 먼저 왔던 데이터는 outstack의 top에 위치하게 된다.
   2. outstack.pop()을 하면 가장먼저 왔던 데이터가 가정 먼저 추출된다.(FIFO)

 

시간복잡도는 어떻게 되는지 설명해 주세요.

• enqueue() : instack.push()를 한번만 하면 되기 때문에 시간복잡도 O(1)입니다.
• dequeue() : 두 가지 경우를 따져봐야 합니다. worst case는 outstack이 비어있는 경우입니다. 이 때는 instack에 있는 n개의 데이터를 instack.pop()을 한 이후에 outstack.push()를 해줘야 합니다. 따라서 총 2*n 번의 operation이 실행되어야 하므로 O(n)의 시간복잡도를 갖습니다.
• 하지만 outstack이 비어있지 않는 경우에는 outstack.pop()만 해주면 됩니다. 이는 O(1)의 시간복잡도를 갖습니다. 이를 종합했을 때, amortized O(1)의 시간복잡도를 갖는다고 할 수 있습니다.

 

Queue 두 개를 이용하여 Stack을 구현해 보세요

스택의 push()와 pop()을 위해 큐를 하나씩 사용해 구현할 수 있습니다. 편의상 push()에 사용할 큐는 q1이라고 부르고 pop()에 사용할 큐를 q2라고 칭하겠습니다.

• push() : q1에 enqueue()를 하여 데이터를 저장
• pop()
  • q1에 저장된 데이터를 1개 제외하고 q2에 옮긴다.
  • q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환한다.
  • q1과 q2의 이름을 swap한다.

 

시간복잡도는 어떻게 되는지 설명해 주세요.

• push() : q1.enqueue()를 한번만 하면 되기 때문에 $O(1)$의 시간복잡도를 갖습니다.
• pop() : q1에 저장되어 있는 n개의 원소중에 n-1개를 q2로 옮겨야 하므로 $O(n)$이 됩니다.

---

⭐ Queue vs priority queue를 비교하여 설명해 주세요

Queue 자료구조는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 구조로 저장하는 형식입니다. 이와 다르게 우선순위큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옵니다.

Queue의 operation 시간복잡도는 enqueue $O(1)$, dequeue $O(1)$이고,

Priority queue는 push $O(logn)$ , pop $O(logn)$ 입니다.

 

우선순위 큐의 구현 방법은?

배열, 링크드 리스트, 힙으로 구현할 수 있습니다.

• 배열과 링크드리스트로 구현할 경우 enqueue 의 경우 O(1)이지만, dequeue 는 O(N) 의 시간복잡도를 갖습니다.
• 힙으로 구현할 경우 그 자체로 우선순위 큐의 역할을 할 수 있고, enqueue/dequeue 연산에서 모두 O(logN) 을 보장합니다.

 

 

 

3) 트리 & 힙

BST는 저장과 동시에 정렬을 하는 자료구조 이진탐색 트리가 되기 위한 조건이 무엇인지, 시간복잡도, worst case, worst case가 발생하지 않게 하기 위해서는 어떻게 해야하는지를 대답할 수 있으면 됩니다.

 

 

Heap 자료구조에 대해 설명해주세요

힙은 완전이진트리를 기본으로 해서 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조입니다. 삽입, 삭제에 O(logN)이 걸리며, 최댓값/최솟값 확인은 O(1)입니다.

 

힙 Heap 연산의 시간복잡도에 대해 설명해주세요

• 삽입의 경우 새로운 값을 마지막 노드에 넣고 swap 하면서 정렬하기 때문에 $O(logn)$ 시간 복잡도를 갖습니다.
• Heap pop의 경우 루트 노드를 pop 한 뒤 마지막 노드를 루트 노드 위치에 넣고 swap 하면서 정렬하기 때문에 마찬가지로로 $O(logn)$ 시간복잡도를 갖습니다.

 

힙을 배열로 구현하는 이유는?

힙은 새로운 노드를 힙의 ‘마지막 위치’에 추가한 뒤 정렬하는데, 이 때 array기반으로 구현하면 이 과정이 수월해지기 때문입니다. 또한 완전이진트리 기반이므로 배열의 인덱스로 부모-자식 인덱스를 쉽게 찾을 수 있습니다.

 

파이썬에서 힙은 어떻게 구현되어 있나요?

파이썬은 heapq 모듈에서 힙 자료구조를 제공하고 있습니다. 리스트 자료구조를 이용해 최소힙을 기준으로 구현되어 있습니다.

---

트리 자료구조에 대해 설명해주세요

트리는 계층적 데이터를 나타내는 노드들의 집합입니다. 노드와 간선으로 이뤄진 비선형 자료구조로 무방향이면서 사이클이 없는 그래프입니다.  트리의 가장 중요한 속성은 '루트노드를 제외한 모든 노드는 단 하나의 부모노드를 갖는다'는 것입니다.

 

 

트리의 순회 방식에는 어떤게 있나요?

• 전위 순회, 중위 순회, 후위 순회가 있습니다.
• 전위 순회는 루트 → 왼쪽 자식 → 오른쪽 자식 순으로 방문하고
• 중위 순회는 왼쪽 자식 → 루트 → 오른쪽 자식 순으로 방문하고
• 후위 순회는 왼쪽 자식 → 오른쪽 자식 → 루트 순으로 방문합니다.

---

이진트리(Binary tree)는 어떤 자료구조 인가요?

모든 node의 자식 노드의 갯수가 2 이하인 트리를 이진 트리라고 합니다.

 

⭐⭐ BST는 어떤 자료구조 인가요?

이진 탐색 트리는 정렬된 트리입니다. 어느 node를 선택하든 해당 node의 left subtree에는 그 node의 값보다 작은 값들을 지닌 node들로만 이루어져 있고, node의 right subtree에는 그 node의 값보다 큰 값들을 지닌 node들로만 이루어져 있는 binary tree입니다.

 

BST의 시간 복잡도는 어떻게 되나요?

검색과 저장, 삭제의 시간복잡도는 모두 $O(logn)$이고, worst case는 한쪽으로 치우친 tree가 됐을 때 $O(n)$입니다.

최악의 경우는 균형이 많이 깨져서 한 쪽으로 치우친 BST로 이렇게 되면 Linked list와 다를게 없어져 탐색 시간복잡도가 $O(n)$이 됩니다.

 

BST의 worst case 해결방법은 무엇인가요?

자가 균형 이진 탐색 트리(Self-Balancing BST)는 알고리즘을 사용해 이진 트리의 균형이 잘 맞도록 유지하여 높이를 가능한 낮게 유지할 수 있습니다. 대표적으로 AVL트리와 Red-black tree가 있습니다.

---

자가 균형 이진 탐색 트리 (self-balancing BST)는 무엇인가요?

자가 균형 이진 탐색 트리는 트리가 편향된 경우 발생할 수 있는 O(N) 연산을 개선하기 위한 자료구조입니다. 트리에서 노드의 삽입 혹은 삭제가 일어날 때 어떤 노드도 왼쪽과 오른쪽 자식의 높이 차가 1 이하가 되도록 균형을 맞추는 트리입니다. 따라서 검색과 저장, 삭제의 시간복잡도는 모두 O(logN)을 유지합니다. 대표적으로 AVL 트리와 Red-black Tree가 있습니다.

 

Red-black 트리란?

각 노드에 색상을 추가해 red와 black을 갖게 하고, 트리에 노드를 삽입 혹은 삭제할 때 특정한 규칙을 지키도록 조정이 이루어져 트리의 균형을 유지합니다. 규칙이란 루트 노드와 말단 노드는 모두 black 이어야 하고, red 의 자식은 모두 black이어야 한다는 규칙입니다. AVL보다 느슨하게 균형을 유지해 삽입과 삭제가 더 빠릅니다.

 

AVL 트리란?

AVL 트리는 트리에 노드를 삽입 혹은 삭제할 때마다 자가 균형 조정 메서드를 호출하여 트리의 균형을 유지합니다. 자가 균형 메서드는 왼쪽 자식과 오른쪽 자식의 높이 차이가 1보다 커지면 회전을 통해 트리의 균형을 유지합니다.

---

검색 자동완성을 어떻게 구현할 수 있을까요?

트라이 자료구조를 활용하면 빠르게 문자열을 찾을 수 있습니다. 트라이는 트리 루트에서부터 문자 하나별로 자식노드에 저장하는 방식의 자료구조입니다. 이진 검색 트리에서는 탐색에 O(log N) 시간이 걸리고 문자열을 비교하는 시간이 추가로 들어 O(M logN) 시간이 걸리는데 반해, 트라이의 경우 저장되어 있는 문자열 개수에 상관없이 O(M)의 시간 복잡도를 갖기 때문입니다.

---

B-Tree 와 B+Tree란?

B-tree 는 이진 트리를 확장해 모든 리프 노드들이 같은 높이를 갖도록 하는 트리입니다. 노드는 정렬된 N개의 Key를 가질 수 있고 그 경우 자식 노드는 N+1 개가 됩니다. B+tree는 B-tree와 비슷하지만 리프 노드에만 데이터가 있고, 각 리프 노드가 연결 리스트 형태를 띄어 선형 검색이 가능한 트리입니다.

 

 

4) 해시 테이블

Hash Table 은 단골 면접 질문!

 

 

직접 주소화 테이블 방법의 장단점은?

직접 주소화 테이블은 key값으로 k를 갖는 원소는 index k에 저장하는 방식입니다. 키 값으로 접근하기 때문에 속도가 빠르지만 키 값이 한정된다는 단점이 있습니다.

 

⭐⭐ Hash table는 어떤 자료구조 인가요?

hash table은 효율적인 탐색을 위한 자료구조로써 키-값 쌍의 데이터를 입력받고, 키에 대한 해시 값을 사용해 값을 저장하고 조회하는 자료구조입니다. 저장, 삭제, 검색의 시간복잡도는 모두 $O(1)$입니다.

 

해시 테이블의 시간복잡도와 공간효율

저장, 삭제, 검색 모두 기본적으로 $O(1)$ 시간복잡도를 갖지만, collision으로 인한 최악의 경우 $O(n)$이 될 수 있습니다.

공간효율성은 떨어집니다. 데이터가 저장되기 전에 미리 저장공간(slot, bucket)을 확보해야 하기 때문입니다. 

 

어떻게 해시 테이블 자료구조는 조회에 시간복잡도 O(1)을 보장하나요?

해시 테이블은 내부적으로 배열을 사용해서 데이터를 저장합니다. 해시 함수의 시간복잡도가 O(1)임을 가정한다면 해시함수를 적용해 KEY 값을 구해 배열의 인덱스 연산으로 바로 조회할 수 있습니다.

 

해시 함수란?

해시 함수는 임의의 길이의 데이터를 고정 길이의 데이터로 매핑하는 함수입니다. 해시 테이블에서는 키에 대한 해시 값을 인덱스로 사용하는데, 이때 고르게 분포될 수 있는 해시 함수를 선택해야 해시 테이블을 효율적으로 사용할 수 있습니다.

 

좋은 hash function의 조건은?

상황마다 좋은 hash function은 달라질 수 있지만, 연산 속도가 빠르고 해시값이 최대한 고르게 분포되게 하는 함수입니다.

 

해시 테이블의 단점은?

배열에 데이터를 저장하므로 공간효율성이 떨어집니다. 또 순서를 보장하지 않아서 순서나 관계가 필요할 때는 적합하지 않습니다.

---

해시 테이블 자료구조에서 발생할 수 있는 문제는?

서로 다른 데이터가 같은 해시값을 가지게 되는 해시 충돌 문제가 있습니다. 해시 충돌 문제가 자주 발생하면 삽입, 조회에 있어 해시 테이블 성능이 안좋아질 수 있습니다.

 

⭐⭐⭐⭐ Hash table에서 collision이 발생하면 어떻게 되나요? 해결방법엔 뭐가 있을까요?

collision이 발생할 경우 대표적으로 2가지 방법으로 해결합니다.

첫 번째, open addressing 방식은 collision이 발생하면 미리 정한 규칙에 따라 비어있는 해시 테이블에 데이터를 저장하는 방법입니다. 빈 slot을 찾는 방법에 따라 크게 Linear Probing, Quadratic Probing, Double Hashing으로 나뉩니다.

두 번째, separete chaining 방식은 linked list를 이용해 충돌이 발생하면 노드를 추가해 데이터를 저장합니다.

 

Open addressing의 장단점

추가적인 메모리를 사용하지 않으므로 linked list 또는 tree자료구조를 통해 추가로 메모리 할당을 하는 separate chaining방식에 비해 메모리를 적게 사용합니다. 다만 충돌 횟수가 많아지면 특정 영역에 데이터가 집중적으로 몰리는 클러스터링 현상이 발생할 수 있고, 조회/검색/삭제를 할 때 인덱스의 키 값이 찾고자 하는 값이 아니라면 추가적인 탐색이 필요하다는 단점이 있습니다.

 

Open Addressing의 Double Hashing 방법이란? 필요한 이유는?

해시 충돌이 발생해 다음 slot을 찾을 때 해시 함수를 사용하는 방법입니다. 비어 있는 slot을 찾기위해 새로운 해시 함수를 사용해 탐사 이동폭을 더 랜덤하게 만들어 클러스터링 문제를 줄일 수 있습니다.

 

Separate chaining 장단점

테이블 확장을 늦출 수 있고 구현이 간단하다는 장점이 있지만, 추가 메모리를 사용해야 하고 조회 성능이 O(1)보다 안좋아진다는 단점이 있습니다. 최악의 경우 n개의 모든 key가 동일한 해시값을 갖게 되면 길이가 n인 링크드 리스트가 생성되게 되고, 검색과 삭제에 있어 O(n)의 시간복잡도를 갖게 됩니다.

 

Hash 충돌이 잦은 경우 어떻게 하면 좋을까?

우선 해시 테이블이 아닌 다른 자료 구조를 사용할 수 있나 찾아볼 것이고, 해시 테이블을 사용해야 한다면 해시 함수가 적절한지 확인할 수 있습니다. 또는 해시 테이블이 75% 이상 차 있다면 테이블을 확장해볼 수 있습니다.

해시 충돌이 잦은 경우 효율적으로 해시 테이블을 사용하려면 separate chaining 에서 링크드 리스트가 아닌 Tree를 사용함으로써 최악의 경우에도 O(log N)의 시간을 보장하도록 할 수 있습니다.

 

해시 테이블의 Resize (동적 확장)

해시 테이블의 빈 슬롯이 적으면 충돌이 잦아져 성능 손실이 발생하므로 일정 임계점 이상 데이터가 채워지면 2배로 해시 테이블을 늘려줍니다.

---

어떨 때 해시를 쓰고 어떨 때 트리를 쓰는 게 좋을까요?

빠른 삽입과 삭제가 필요한 경우에는 해시를 사용합니다. 그리고 내부적으로 자료가 정렬되어 있어야 하거나 범위 탐색이 필요하다면 트리를 사용합니다.