이론) 자료구조

 

 

 

 

 

 

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

Stack과 Queue는 선형 자료구조의 일종이며, Array와 LinkedList로 구현할 수 있습니다.

Stack은 후입선출(LIFO)방식 즉, 나중에 들어간 원소가 먼저 나오는 구조이고

Queue는 선입선출(FIFO)방식 즉, 먼저 들어간 원소가 먼저 나오는 구조를 갖습니다.

Tree는 스택과 큐와 같은 선형 구조가 아닌 비선형 자료구조이며, 계층적 관계를 표현하기에 적합합니다.

Heap은 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로, 각 노드의 키값이 자식의 키값보다 작지 않거나(최대힙) 그 자식의 키값보다 크지 않은(최소힙) 완전이진트리 입니다.

 

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

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

 

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

 

동기화 지원 여부와 null 값 허용 여부의 차이가 있습니다.
해시 테이블(Hash Table)
병렬 처리를 할 때 (동기화를 고려해야 하는 상황) Thread-safe 하다.
Null 값을 허용하지 않는다.

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

 

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

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

 

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

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