기술면접 준비 - 자료구조

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

Array의 가장 큰 특징은 데이터를 순차적으로 저장한다는 점이다.
장점
- index를 사용해 특정 요소를 찾고 조작이 가능하다.
단점
- 요소가 삽입되거나 삭제되는 경우 그 뒤의 모든 요소를 한 칸씩 뒤로 밀거나 당겨줘야함
- 정보가 자주 바뀌는 데이터를 담기에는 적절하지 않음

 

💡 Stack, Queue / Tree, Heap의 구조에 대해 설명해주세요

Stack과 Queue는 선형 자료구조, Array와 LinkedList로 구현 가능
Stack: 후입선출(LIFO)
Queue: 선입선출(FIFO)

Tree는 비선형 자료 구조, 계층적 관계를 표현하기에 적합
Heap은 최대, 최소값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조

 

 

💡 Priority Queue에 대해 설명해주세요

append한 순서에 상관없이 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조
구현 방식: Array, Linkedlist, Heap
heap 방식이 시간 복잡도 O(logN)을 보장하기 때문에 일반적으로 이진트리 형태의 힙을 이용해 구현

 

 

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

Array: 크기가 고정적, 초기화 시 메모리에 할당됨
ArrayList: 크기가 가변적, 데이터 추가 및 삭제 시 메모리 재할당
따라서 Array가 ArrayList보다 속도가 빠르다.

 

 

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

Array
장점: 원소의 인덱스 값을 알고 있으면 해당 원소로 접근 가능, RandomAccess가 가능해 검색 속도가 빠름
단점: 삽입, 삭제 과정에서 원소들을 shift 해줘야해서 시간 복잡도가 O(n)

LinkedList
장점: 원소가 있는 부분만 다른 값으로 바꿔주면 삽입과 삭제를 O(1)로 해결 가능
단점: 검색이 느리다.

 

 

 

💡 Hash Table의 시간복잡도에 대해 설명해주세요

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

 

 

 

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

Hash Map
- 병렬 처리를 하지 않을 때(동기화 고려 x) thread-safe하지 않다.
- null값 허용

Hash Table
- 병렬 처리를 할 때(동기화 고려) thread-safe 하다
- null 값을 허용하지 않는다.

 

 

 

💡 Binary Search Tree와 Binary Tree에 대해 설명해주세요

Binary Tree
- 자식 노드가 최대 두개인 노드들로 구성된 트리

Binary Search Tree
- 이진 탐색과 연결 리스트를 결합한 자료구조
- 이진 탐색의 효율적인 탐색 능력을 유지하면서, 자료 입력과 삭제가 쉬움
- 왼쪽 트리의 모든 값은 반드시 부모 노드보다 작아야 하고, 오른쪽 트리의 값은 부모 노드보다 커야 함
- 높이가 h일 때 시간 복잡도 : O(h)
- Worst Case: 트리의 균형이 한쪽으로 치우쳐진 경우(O(n)