자료구조란?

자료구조는 자료의 표현과 그것과 관련된 연산을 의미합니다.
알고리즘 문제를 풀다보면, 특정 값을 자료구조 형태로 저장하고 필요에 따라 원하는 값을 꺼내는 작업이 매우 많이 일어납니다. 이렇게 자료구조에 값을 넣거나, 원하는 값을 꺼내거나, 원하는 값이 존재하는지 판정하는 요구를 쿼리(query)라고 부릅니다.

자료구조 1

첫번째로는 배열과 연결리스트, 해시테이블을 배웁니다.
각 자료구조의 쿼리 복잡도는 다음과 같습니다.

  배열 연결리스트 해시테이블
c++ 라이브러리 vector list unordered_set
i번째 요소의 접근 $O(1)$ $O(N)$ -
x 삽입 $O(1)$ $O(1)$ $O(1)$
x를 i번쨰에 삽입 $O(N)$ $O(1)$ $O(1)$
x 삭제 $O(N)$ $O(1)$ $O(1)$
find(x) $O(N)$ $O(N)$ $O(1)$

배열

배열은 같은 자료형의 데이터를 하나의 변수에 저장하는 자료구조입니다. 배열은 인덱스를 사용하여 데이터에 빠르게 액세스할 수 있습니다. 배열은 메모리에 연속적으로 저장되기 때문에 랜덤액세스1가 가능합니다. 이러한 특징으로 인해 배열은 많은 알고리즘에서 사용됩니다. 예를 들어 Dynamic Programming이라던지 이진탐색(binary search), Greedy등 여러 알고리즘에서 사용됩니다.

배열의 장점은 index i에 대해서 데이터 a[i]에 $O(1)$의 복잡도로 접근합니다.

하지만 요소 x를 y다음에 삽입하거나, 요소x를 삭제할 때 $O(N)$의 복잡도로 처리합니다.

연결리스트

해시테이블

  1. 배열의 랜덤 액세스는 배열에서 특정한 위치에 있는 데이터를 빠르게 찾는 것을 말합니다. 랜덤 액세스는 데이터를 순차적으로 읽는 것이 아니라, 데이터가 저장된 위치를 기반으로 데이터를 읽어오기 때문에 빠른 속도로 데이터를 찾을 수 있습니다. ↩