[신입 CS 질문] 자료구조

Array(List)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점

• 순차적 데이터 저장
• 0부터 시작하는 index를 토해 특정 요소의 검색과 조작이 쉽다는 장점
• 중간에 요소의 삽입, 삭제가 일어나는 경우 뒤의 모든 요소들을 옮겨야 하는 단점이 있음
• 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않음

Array를 적용시키면 좋을 데이터의 예

• 주식 차트는 순서가 날짜별로 가져야 저장되어야 하며 중간에 데이터에대한 추가 및 삭제가 없기 때문에 좋은 예시
• 순서가 가장 중요하므로 순서를 보장해주는 array 자료구조가 적합

Stack

• 선형 자료구조
• Array와 LinkedList로 구현
• 후입선출(LIFO) 구조
• 자바의 지역변수, 매개변수 데이터 값이 저장되는 메모리 영역

QUEUE

• 선형 자료구조
• Array와 LinkedList로 구현
• 선입선출(FIFO)구조
• OS에서 자원의 할당과 회수를 하는 스케쥴러 역할

Priority Queue(우선순위 큐)

• 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조

• 우선순위 큐 구현 방식에는 배열, 연결 리스트, 힙이 있고, 그중 힙 방식이 worst case라도 시간 복잡도 O(logN)을 보장하기 때문에 일반적으로 완전 이진트리 형태의 힙을 이용해 구현

TREE

• 비선형 구조
• 계층적 관계 표현

HEAP

• 최댓값 또는 최솟값을 찾아내기 위해 고안된 구조
• 완전 이진트리이며
• 각 노드의 키 값이 자식의 키 값보다 작지 않은 최대힙을 가짐
• 각 노드의 키 값이 자식의 키 값보다 크지 않은 최소힙을 가짐

완전이진트리

• 마지막 레벨을 제외하고 모든 레벨은 노드가 완전히 채워져 있으며, 마지막 레벨이 모든 노드는 가능한 가장 왼쪽에 있는 트리

Array와 ArrayList의 차이점

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

Array와 LinkedList의 장/단점

Array

• Array는 검색이 빠르지만, 삽입, 삭제가 느리다.

LinkedList

• LinkedList는 삽입, 삭제가 빠르지만, 검색이 느리다.

해시 테이블(Hash Table)과 시간 복잡도

• 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조

• Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간 복잡도를 가짐

Hash Map과 Hash Table의 차이점

• 동기화 지원 여부와 null 값 허용 여부의 차이

해시 테이블(Hash Table)

• 병렬 처리를 할 때 (동기화를 고려해야 하는 상황) Thread-safe 하다.
• Null 값을 허용하지 않는다.

해시 맵(Hash Map)

• Null 값을 허용한다.

BST(Binary Search Tree)와 Binary Tree에 대해 설

이진트리

• 이진트리(Binary Tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리

이진탐색트리

• 이진 탐색 트리(BST)는 이진 탐색과 연결 리스트를 결합한 자료구조
• 왼쪽 트리의 모든 값은 바드시 부모 노드보다 작아야하고, 오른쪽 트리의 값은 부모노드보다 커야 한다.
• 높이가 H일때 시간 복잡도는 O(h)이며, 트리의 균형이 한쪽으로 치우쳐진 경우 worst case가 디ㅗ고 O(n)의 시간 복잡도를 가진다.

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

• RBT(Red-Black Tree)는 이진 탐색 트리를 기반으로 하는 트리 형식 자료구조

• 이진 탐색 트리의 worst case를 막기위해 나온 구조

• BST의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어졌음

• 노드의 child가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장합니다. 이러한 NIL들을 leaf node로 간주합니다.

참조
https://dev-coco.tistory.com/159