CS 기술 면접 - 자료구조

📍 자료구조, 알고리즘

 

• 자료구조 : 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조
• 알고리즘 : 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임

 

 

📍 스택, 큐

 

• 스택, 큐
  
  • 선형 자료구조의 일종
• 스택(Stack)
  • 삽입과 삭제 연산이 후입선출(LIFO : Last-In First-Out)로 이뤄지는 자료구조
  • 후입선출(LIFO : Last-In First-Out) : 가장 나중에 삽입된 데이터를 가장 먼저 삭제한다.
• 큐(Queue)
  • 삽입과 삭제 연산이 선입선출(FIFO : First-In First-Out)로 이뤄지는 자료구조
  • 선입선출(FIFO : First In First Out) : 가장 먼저 삽입된 데이터를 가장 먼저 삭제한다.

 

 

📍 트리, 힙

 

• 트리(Tree)
  • 노드과 에지를 이용해 사이클을 이루지 않도록 구성한 그래프의 특수한 형태로, 계층이 있는 데이터를 표현하기에 적합하다.

• 힙(Heap)
  • 완전 이진 트리로, 최대값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조이다.
  • 최대 힙(max heap) : 부모 노드 값 > 자식 노드 값, 값이 큰 데이터 먼저 삭제
  • 최소 힙(min heap) : 부모 노드 값 < 자식 노드 값, 값이 낮은 데이터 먼저 삭제

 

 

📍 ArrayList, LinkedList

 

• ArrayList
  • 데이터들이 순서대로 늘어선 배열의 형식
  • 사이즈 : 리스트의 크기가 제한되어 있으며, 이를 재조정하는 것은 많은 연산이 필요하다.
  • 접근 : index를 통해 원하는 데이터에 무작위로 접근할 수 있다. (시간 복잡도 : O(1))
  • 삽입, 삭제 : 각 요소들을 재배치해야하기 때문에 오래 걸린다. (시간 복잡도 : O(N))
  • 정적 메모리 할당 : Compile time에 Stack 영역에 메모리 할당이 이루어진다.
• LinkedList
  • 데이터들이 자료의 주소값으로 서로 연결된 형식
  • 사이즈 : 리스트의 크기에 영향 없이 데이터를 추가할 수 있다.
  • 접근 : 무작위 접근이 불가능하며, 순차 접근만이 가능하다. (시간 복잡도 : O(N))
  • 삽입, 삭제 : 새로운 노드를 생성하여 연결하기 때문에 빠르다. (시간 복잡도 : O(1))
  • 동적 메모리 할당 : Runtime에 Heap 영역에 메모리 할당이 이루어진다.

 

 

📍 우선순위 큐

 

• 우선순위 큐(Priority Queue) : 값이 들어간 순서와 상관없이 우선순위가 높은 데이터를 가장 먼저 삭제하기 위해 고안된 자료구조
  
  • 힙을 이용해 구현
  • 시간 복잡도 : O(logn)

 

 

📍 해시 테이블

 

• 해시테이블(Hash Table) : (Key, Value)로 데이터를 저장하는 자료구조
  • 빠른 데이터 검색이 필요할 때 유용
  • Key 값에 Hash 함수를 적용해 고유한 index를 생성하고, 이를 활용해 값을 조회하기 때문에 시간복잡도 O(1)을 갖는다.
  • index 값에 충돌이 발생한 경우, 연결된 데이터들을 활용해 값을 조회하기 때문에 시간복잡도 O(N)까지 증가할 수 있다.