📚 [CS면접] 웹 면접 질문 [18] [자료구조 / 알고리즘]

1. 자료구조와 알고리즘이란 ?

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

 

2. Array [ 배열 ] 와 LinkedList [ 연결리스트 ]

Array 는 순서가 있는 데이터를 저장하기 위한 선형 자료구조이며, 고정 길이의 크기를 가진 자료구조이다. 순서가 있기 때문에 각 데이터의 순서를 의미하는 Index가 존재하며, Index를 통해 데이터에 접근하는 Random Access를 지원한다. Index를 통해 값을 색인하면 O(1)의 시간복잡도가 소요된다.

 

하지만, 중간에 값을 삽입하거나 삭제하면 O(N)의 시간복잡도를 갖는다.

 

이러한 고정길이와 느린 삽입, 삭제 연산을 해결하기 위해 나온 자료구조가 LinkedList이다. 데이터를 저장하고 있는 각 노드들을 서로 연결 시켜 만든 선형 자료구조로, 가변 길이의 크기를 가지고 있다. 중간에 값을 삽입이나 삭제하는 과정에서 O(1)의 시간복잡도를 갖는다. 반면, 검색에 있어서는 최악의 경우 O(N) 이라는 단점이 있다.

 

3. Stack [ 스택 ] 과 Queue [ 큐 ]

스택은 FIFO의 특징을 가진 자료구조이다. 스택을 구현하기 위해서는 배열 / 연결리스트 사용이 가능하며, 주료 배열을 통해 구현한다. 스택이 실제로 사용되는 부분은 브라우저의 '뒤로가기' 기능이나 메모리 영역의 스택 영역에 사용된다.

 

큐는 FILO의 특징을 가진 자료구조이다. 큐는 주로 연결리스트를 통해 구현한다. 큐가 실제로 사용되는 부분은 프린터 큐, CPU 스케줄링의 Ready Queue등에 사용된다. 

 

3. Priority Queue [ 우선순위 큐 ]

선입선출의 구조를 가진 큐와는 다르게, 우선순위가 높은 원소가 우선적으로 빠져나오게 되는 자료구조이다.

 

우선순위 큐는 배열, 연결리스트, Heap으로 구현할 수 있으며, 일반적인 경우에는 삽입과 삭제 연산이 모두 O(LogN)이 보장된 Heap 자료구조를 사용해서 우선순위 큐를 구현한다.