[면접 준비] - 자료구조

🤗 모든 질문은 '아는대로 설명해주세요'가 베이스~!

 

🔔 Array(List)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점에 대해 설명해주세요.

• Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점입니다.
• 데이터에 순서가 있기 때문에 0부터 시작하는 index가 존재하며, index를 사용해 특정 요소를 찾고 조작이 가능하다는 것이 Array의 장점입니다.
• 순차적으로 존재하는 데이터의 중간에 요소가 삽입되거나 삭제되는 경우 그 뒤의 모든 요소들을 한 칸씩 뒤로 밀거나 당겨줘야 하는 단점도 있습니다.
• 이러한 이유로 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절치 않습니다.

---

🔔 Stack과 Queue, Tree와 Heap의 구조에 대해 설명해주세요.

• Stack과 Queue는 선형 자료구조의 일종이며, Array와 LinkedList로 구현할 수 있습니다.
• Stack은 후입선출(LIFO)방식 즉, 나중에 들어간 원소가 먼저 나오는 구조이고
• Queue는 선입선출(FIFO)방식 즉, 먼저 들어간 원소가 먼저 나오는 구조를 갖습니다.

 

• Tree는 스택과 큐와 같은 선형 구조가 아닌 비선형 자료구조이며, 계층적 관계를 표현하기에 적합합니다.
• Heap은 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로,
• 각 노드의 키값이 자식의 키값보다 작지 않거나(최대힙) 그 자식의 키값보다 크지 않은(최소힙) 완전이진트리 입니다.

 

---

🔔 Stack과 Queue의 실사용 예를 들어 간단히 설명해주세요.

• Stack - 자바의 Stack 메모리 영역
  • 지역변수와 매개변수 데이터 값이 저장되는 공간이며, 메소드 호출시 메모리에 할당되고 종료되면 메모리가 해제되며, LIFO(Last In First Out)구조를 가집니다.
•  Queue - OS의 스케쥴러
  • 자원의 할당과 회수를 하는 스케쥴러 역할을 큐가 할 수 있습니다.
  • 메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인가 그 순서를 결정하는 것이 자원의 효율적인 사용에 있고,
  • 가장 단순한 형태의 스케쥴링 정책이 선입선처리(First Com First Served) 즉, 큐라고 볼 수 있습니다.

---

🔔 Priority Queue(우선순위 큐)에 대해 설명해주세요.

• 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다.
• 우선순위 큐 구현 방식에는 배열, 연결 리스트, 힙이 있고, 그중 힙 방식이 worst case라도 시간 복잡도 O(logN)을 보장하기 때문에 일반적으로 완전 이진트리 형태의 힙을 이용해 구현합니다.

---

🔔 Array와 ArrayList의 차이점에 대해 설명해주세요.

• Array는 크기가 고정적이고, ArrayList는 크기가 가변적입니다.
• Array는 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르고,
• ArrayList는 데이터 추가 및 삭제 시 메모리를 재할당하기 때문에 속도가 Array보다 느립니다.

---

🔔 Array와 LinkedList의 장/단점에 대해 설명해주세요.

• Array는 인덱스(index)로 해당 원소(element)에 접근할 수 있어 찾고자 하는 원소의 인덱스 값을 알고 있으면 O(1)에 해당 원소로 접근할 수 있습니다.
• 즉, RandomAccess가 가능해 속도가 빠르다는 장점이 있습니다.
• 하지만 삽입 또는 삭제의 과정에서 각 원소들을 shift 해줘야 하는 비용이 생겨 이 경우 시간 복잡도는 O(n)이 된다는 단점이 있습니다.

 

• 이 문제점을 해결하기 위한 자료구조가 linkedlist입니다. 
• 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있기 때문에 이 부분만 다른 값으로 바꿔주면 삽입과 삭제를 O(1)로 해결할 수 있습니다.
• 하지만LinkedList는 원하는 위치에 한 번에 접근할 수 없다는 단점이 있습니다. 
• 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search 과정에 있어서 첫번째 원소부터 다 확인해봐야 합니다.

---

🔔 해시 테이블(Hash Table)과 시간 복잡도에 대해 설명해주세요.

• 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다.
• 빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문입니다.
• 각 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간 복잡도로 데이터를 조회합니다.
• 하지만 index값이 충돌이 발생한 경우 Chanining에 연결된 리스트들까지 검색해야 하므로 O(N)까지 증가할 수 있습니다.

---

🔔 Hash Map과 Hash Table의 차이점에 대해 설명해주세요.

동기화 지원 여부와 null 값 허용 여부의 차이가 있습니다.

• 해시 테이블(Hash Table)
  • 병렬 처리를 할 때 (동기화를 고려해야 하는 상황) Thread-safe 하다.
  • Null 값을 허용하지 않는다.
• 해시 맵(Hash Map)
  • 병렬 처리를 하지 않을 때 (동기화를 고려하지 않는 상황) Thread-safe하지 않는다.
  • Null 값을 허용한다.

---

🔔 BST(Binary Search Tree)와 Binary Tree에 대해 설명해주세요.

• 이진트리(Binary Tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리이고,
• 이진 탐색 트리(BST)는 이진 탐색과 연결 리스트를 결합한 자료구조입니다.
• 이진 탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있습니다.
• 이진 탐색 트리는 왼쪽 트리의 모든 값은 반드시 부모 노드보다 작아야 하고, 오른쪽 트리의 값은 부모 노드보다 커야 하는 특징이 있습니다.
• 이진 탐색 트리의 탐색 연산은 트리의 높이에 영향을 받아 높이가 h일 때 시간 복잡도는 O(h)이며,
  트리의 균형이 한쪽으로 치우쳐진 경우 worst case가 되고 O(n)의 시간 복잡도를 가집니다.
• 이런 worst case를 막기 위해 나온 기법이 RBT(Red-Black Tree)입니다.

---

🔔 RBT(Red-Black Tree)에 대해 설명해주세요.

• RBT(Red-Black Tree)는 BST를 기반으로 하는 트리 형식 자료구조이며,
  RBT는 BST의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어졌습니다.
• BST를 기반으로 하기 때문에 당연히 BST의 특징을 모두 갖습니다.
• 노드의 child가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장합니다.
• 이러한 NIL들을 leaf node로 간주합니다.
• 모든 노드를 빨간색 또는 검은색으로 색칠하며, 연결된 노드들은 색이 중복되지 않습니다.

 

 

참고

https://dev-coco.tistory.com/164 [슬기로운 개발생활:티스토리]