CS준비 - 자료구조

자료구조와 알고리즘

자료구조는 데이터를 저장하고 관리하는 방식입니다. 알고리즘은 선택된 자료구조에 의해 쌓인 데이터를 활용한 문제 해결 방식 입니다. 자료구조에 따라 알고리즘이 달라지며, 알고리즘에 따라 문제 해결 속도가 달라집니다.

 

스택, 큐, 트리, 힙 구조 설명

스택 : 후입 선출의 구조 즉, LIFO(Last-in First-out)의 구조로 되어있습니다.

큐 : 선입 선출의 구조 즉, FIFO(First-in First-out)의 구조로 되어있습니다.

트리 : 노드로 이루어진 자료구조이며, 정점(Root)과 간선(edge)로 이루어져있습니다. 계층이 있는 데이터를 표현하기에 적합합니다.

힙 : 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로, 완전 이진트리의 구조를 가집니다.

 

우선순위 큐와 내부 구조 및 시간복잡도

우선순위 큐는 FIFO(First-in First-out)의 구조를 따르지 않고, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조입니다. 우선순위 큐를 구현하기 위해서 일반적으로 힙을 사용합니다. 여기서 힙이란 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기위해 고안된 구조로, 완전 이진트리의 구조를 가집니다. 따라서 우선순위 큐의 시간 복잡도는 O(logn)입니다.

 

해시 테이블과 해시 테이블의 시간 복잡도

해시 테이블이란 key, value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다. 해시 테이블이 빠른 검색 속도를 제공하는 이유는 내부적으로 배열(buckets)을 이용하여 데이터를 저장하기 때문입니다. 해시 테이블은 고유한 index로 값을 조회하기 때문에 평균적으로 O(1)의 시간 복잡도를 갖습니다.

 

LinkedList와 ArrayList 차이

ArrayList의 경우 저장되는 방식이 배열과 같아서 데이터에 접근하기가 쉽지만 데이터의 추가, 삭제가 오래 걸린다는 것이 단점입니다.

반대로 LinkedList의 경우 노드로 저장되기 때문에 데이터의 추가, 삭제가 쉽습니다. 하지만 노드로 저장되는 특성으로 인해 데이터 접근 시 순차 접근만이 가능하여 데이터 접근이 ArrayList에 비해 어렵습니다.