면접 준비를 위한 자료구조

 

자료구조란 ?

효율적으로 데이터를 관리하고, 탐색, 저장, 수정, 삭제 할 수 있는 데이터 집합을 의미

 

Q. Array 는 어떤 자료구조인가?

A. 데이터를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조.

-> point 1.  메모리 상에 연속적으로 저장된다.

-> point 2. 미리 할당된 저장 공간 = 고정적인 저장공간

 

장점  : 조회와 append 가 빠르다. 

단점 : fixed Size 특성상 미리 메모리를 할당 받아야 하는데, 메모리 낭비나 추가적인 overhead 가 발생할 수 있다.

 

Q.  array 의 미리 고정된 크기보다 더 많은 data 를 저장하게 되면 어떻게 해결하나?

A. 기존 size 보다 더 큰 Array 를 생성하여 데이터를 옮겨 할당한다.

위와 같은 방식으로, 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic Array 라고 한다.

 

Q. Dynamic Array 란?

A. 저장공간이 가득차면, 동적으로 resize 하여 size 를 조절하는 자료구조를 의미한다. 

-> resize 방식 - Doubling : 기존 할당된 메모리를 초과하여 데이터를 저장하게 되면, size 를 2배 늘린 배열을 선언하고, 그곳으로 모든 데이터를 옮겨 늘어난 크기의 size 를 가진 배열이 된다. 

 

Q. Array 의 시간복잡도는 어떻게 되는가?

A.

- append() 할 때, 평상시엔 O(1) 이지만, Resize 가 발생한다면, 모든 데이터를 새로운 array 에 옮겨야 하기 때문에 O(n) 의 시간복잡도가 걸린다. 평균적으로는 O(1) 이라 볼 수 있다.

- 데이터 조회시, 배열의 인덱스로 곧바로 조회하기에 O(1) 의 시간복잡도가 걸린다.

 

Q. LinkedList 란?

A. Node 라는 구조체로 이루어져, 하나의 Node 에 데이터 값과 다음 Node 의 Address 를 저장하는 자료구조를 의미한다.

- Array 와 달리 물리적 메모리 상에는 비연속적으로 저장되지만, Linked List 를 구성하는 각각의 Node 가 다음 Node 의 address 를 가르킴으로 논리적인 연속성을 가진다. 

- 고정 크기의 Array 와 달리, Linked List 는 데이터가 추가되는 시점에 메모리가 할당되기에, 메모리를 더 효율적으로 사용할 수 있다.

 

Q. 어느 상황에서 Array 를 사용하는 것이 Linked List 보다 나은 선택인가?

A. 

• 주로 조회 작업을 자주할 때
• 데이터를 반복문을 통해 빠르게 순회할 때
• 메모리를 적게 쓰는게 중요한 상황일 때. 고정 크기 방식이지만, Linked List 보단 array 가 메모리를 적게 차지하기 때문에, 미리 데이터의 사이즈를 알고 있다면 Array 가 메모리를 더 효율적으로 사용한다. Linked List 는 Node 로 이루어졌기에 원래 메모리 할당량이 크다. 

Q. Array 와 LinkedList 비교해서 설명해보라

A. 우선 메모리 구조 차이로 인한 차이점이 존재한다.

• 1. Operation 구현 방법이 다르고,
• 2. 시간 복잡도도 다르다. 
  • Linked List 
  • O(N) : access / search <- 메모리에 비 연속적으로 저장돼 있기 때문. 
  • O(1) : insertion / delete <- 마찬가지로 메모리에 비 연속적으로 저장돼 있기 때문에, 삽입과 삭제는 쉽다. 
• 3. 메모리 활용도에서도 차이가 있다.
  • Array는 우선 연속적 메모리 할당이라는 특성에서 데이터 접근과 append 가 빠르지만, 고정 크기 할당이기에 메모리 낭비라는 단점도 존재한다. 
  • Linked List 는 runtime 중에도 size 를 늘리거나 줄일 수 있다. 그래서 array 와 달리 memory allocation 관점에서는 메모리 낭비가 없다. 하지만 비연속적 메모리 구조로 인해 데이터 접근과 탐색이 비교적 느리다. 

 

Q. Array 와 LinkedList 의 메모리 할당은 언제 일어나며, 메모리의 어느 영역을 할당받나?

A. 

• Array 는  컴파일 단계에서 메모리 할당이 일어난다. 이를 static memory allocation 이라 부르며, Stack Memory  영역에 할당된다. 
• LInked List 는 런타임 단계에서 새로운 node 가 추가될 때마다 memory allocation 이 일어난다. 이를 dynamic memory allocation 이라 부르며, heap 메모리 영역에 할당된다. 

 

Q. Queue 는 어떤 자료구조인가?

A. 선입선출 형식으로 데이터를 저장하는 자료구조 !! 

• 시간복잡도
  • Enqueue : 데이터 추가 : O(1)
  • Dequeue : 데이터 삭제 : O(1)
• 활용 예시
  • Cache 구현, Process 관리, BFS 등

 

Q. Array Based Queue 와 List Based Queue 를 설명해달라

A. 

• Array-Base 는 circular queue 로 구현하는 것이 일반적이다. 메모리를 효율적으로 사용하기 위함인데, enqueue 가 계속 발생시 fixed size 를 넘어서더라도, 시간복잡도는 O(1) 을 유지할 수 있다. 
• List-Base 는 보통 linked list 로 구현한다. enqueue 는 단순히 linked list 에서 append 를 하는것으로 구현되고, 이 때 시간복잡도는 O(1) 이 된다. dequeue 는 맨 앞의 원소를 삭제하고 first head 를 변경하기 때문에 역시 O(1) 의 시간복잡도가 걸린다.

 

Q. Queue vs Priority Queue 를 비교하여 설명해보라

A. 

Queue 는 시간순서상 먼저 들어간 데이터가 먼저 출력되는 자료구조이며, 

Priority queue 는 들어간 순서와 상관없이, 우선순위가 높은 데이터가 먼저 출력된다. 

 

Q. Heap 은 어떤 자료구조인가? 

A. Heap 은 그 자체로 우선순위 큐의 구현과 일치한다. 

• Heap 은 완전이진트리로 아래의 조건을 가진다. 
  • 1) Max Heap : 각 노드에 저장된 값은 child node 의 값보다 크거나 같다. 
  • 2) Min Heap : 각 노드에 저장된 값은 child node 의 값보다 작거나 같다. 

 

Q. Heap 은 어떻게 구현할 수 있는가?

A. 보통의 Tree 는 linked list 로 구현하지만, Heap 은 트리임에도 불구하고 Array 를 기반으로 구현한다. 

새로운 node 를 heap 의 마지막 위치에 추가해야하는 특징 때문인데, array 기반으로 구현해야 더 수월하기 때문이다. 마지막 위치에 추가하긴 하지만, swap 과정을 거쳐 자신의 위치를 찾아간다. 

 

 

Q. Stack 은 어떤 자료구조인가?

A. 후입선출 형태로 데이터를 저장하는 자료구조. 

• 시간복잡도는 push, pop 모두 O(1) 
• 활용 예시 : 후위 표기법 연산, 괄호 유효성 검사, 브라우저 뒤로가기 기능, DFS 등 

 

Q. BST(Binary Search Tree) 는 어떤 자료구조인가?

A. 이진 탐색 트리는 정렬된 트리 구조로, 어떤 노드의 left 에 위치하는 모든 값은 해당 노드보다 작은 값을 가지며, right 에 위치한 값은 해당 node 보다 큰 값을 갖는다.

• BST 는 저장과 동시에 정렬을 하는 자료구조로, 새로운 Data 저장시 일정한 규칙에 따라 저장하게 된다. 
• 시간 복잡도 
  • 검색, 저장, 삭제 : O(logN) -> 트리의 높이가 logN 이기 때문
  • worst case 일 때 : O(logN) -> 선형 구조이기 때문

 

Q. 이진 탐색트리의 시간복잡도를 말해달라. 

A. 검색과 저장, 삭제의 시간복잡도는 모두 O(logN) 이고, Worst Case 는 한쪽으로 치우친 Tree 가 됐을 때 O(N) 이 된다. 

 

Q. 이진 트리는 어떤 자료구조인가?

A. 모든 Nodes 의 Child nodes 갯수가 2 이하인 트리.

 

Q. 이진 트리의 worst case 는 어떤 경우인가?

A. 한쪽으로 치우친 트리구조가 될 때, 즉 선형처럼 보일 때 worst case 가 된다. (linked list 와 다를게 없어지기 때문)

마찬가지로 BST 의 Worst case 도 한쪽으로 치우친 트리형태 일 때다. 

 

Q. Hash Table 은 어떤 자료구조인가?

A. key-value 쌍으로 데이터를 입력받는, 효율적인 탐색을 위한 자료구조. 

• hash function h() 를 이용해 key - value 를 Hash Table 에 저장한다.
• key 는 반드시 존재해야하며, 중복돼선 안된다.
• Hash Table 을 구성하는 key - value 를 저장할 수 있는 공간을 bucket 혹은 slot 이라 부른다.
• 시간 복잡도
  • 저장, 탐색, 삭제 : O(1)
  • collision : O(n)

Q. 좋은 Hash function 의 특징은 ?

A. 각 상황마다 좋은 hash function 의 특징은 다르지만, 대략적인 기준은 1) 연산속도가 빨라야하고, 2) 해시 충돌은 가능한 피해야 한다. 

 

Q. collision 이란?

A. key 값은 다르지만, key 의 해시값이 같을 때 발생하는 충돌을 의미한다. -> 중복되는 key 는 없지만, Hash 값은 중복될 수 있다는 뜻

 

Q. Collision 해결 방법은?

A. Seperate Chaining 과 Open Addressing 2가지 방식으로 해결할 수 있다. 

• Open Addressing : 추가적인 메모리를 사용하지 않기에, Seperate Chaining 에 비해 메모리 효율이 좋다.
  • Linear Probing : 선형 조사법 : 충돌이 발생한 해시값으로부터 일정한 값 만큼 건너뛰어 비어있는 Slot 에 데이터를 저장한다 ( + 1, +2, +3 ... )
  • Quadratic Probing : 이차 조사법 :선형 조사법이 1단위로 건너뛰었다면, 이차 조사법은 제곱수로 건너뛰어 빈 slot 을 탐색한다 (+1, +4, +9 ... )
  • Double Hashing : Linear / Quadratic Probing 은 탐사 이동폭이 일정하기 때문에, 특정 영역에 데이터가 몰리는 clustering 현상이 발생할 수 있다.(clustering -> 탐색시간이 길어지는 문제 발생) Clustering 문제를 해결하기 위해 2개의 해시함수를 사용하는 방식을 Double Hashing 이라 한다. 하나는 최초의 Hash 값을 얻을 때 사용하고, 두번 째는 collision 발생 시 탐사 이동폭을 얻기 위해 사용한다.
• Seperate Chaining : Linked List (or Tree) 를 이용하여 Collision 을 해결한다. 
  • 충돌이 발생시 Linked List 에 노드를 추가하여 데이터를 저장한다. 즉 같은 슬롯에 링크드 리스트를 계속 추가하여 데이터를 저장하는 것이다. 
  • 삽입 시 : 서로 다른 두 key 가 같은 해시값을 가지면, linked list 에 노드를 추가하여 key - value 를 저장, 시간 복잡도는 O(1)
  • 삭제 시 : 기본적으로 O(1), worst case 는 O(N)
  • 조회 시 : 기본적으로 O(1), worst case 는 O(N). -> Worst case : 서로 다른 n 개의 key 가 동일한 해시값을 갖게 되면, 길이 n 의 linked list 를 생성한다. => 시간복잡도 O(N) 으로 증가.