자료구조
-
자료구조(Data Structure)는 데이터를 효율적으로 저장하고 관리하여 빠르게 접근하고 수정할 수 있도록 설계된 구조이다.
-
프로그래밍에서 데이터를 다룰 때, 어떤 자료구조를 사용하느냐에 따라 성능이 크게 달라질 수 있다.
-
자료구조는 크게 선형(Linear) 구조와 비선형(Non-Linear) 구조로 나뉜다.
선형 자료구조, 비선형 자료구조
선형 자료구조
-
특징 : 데이터 간의 관계가 1:1로 연결되어 일렬로 나열된 구조
-
예시 : 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue)
비선형 자료구조
-
특징 : 데이터 간의 관계가 1:다 또는 다:다로 연결되어 계층적 구조를 가짐
-
예시 : 트리(Tree), 그래프(Graph)
알고리즘 성능 평가
-
효율적인 문제 해결을 위해 알고리즘의 성능을 평가하는 기준이 필요하다.
-
상황에 따라 적합한 알고리즘을 선택하기 위해 공간 복잡도와 시간 복잡도를 고려해야 한다.
공간 복잡도
-
알고리즘이 얼마나 많은 메모리를 사용하는지를 나타낸다.
-
예전에는 제한된 메모리 때문에 중요했지만, 현재는 저장 공간이 늘어나 상대적으로 중요성이 감소했다.
그러나 대규모 데이터 처리에서는 여전히 중요한 요소이다.
시간 복잡도
-
알고리즘이 실행될 때 소요되는 연산의 횟수를 나타낸다.
-
데이터양(n)이 증가할 때 연산량이 어떻게 변화하는지 분석한다.
빅오(Big-O) 표기법
- 알고리즘의 성능을 표현하는 점근 표기법으로,
입력 크기 증가에 따른 시간 복잡도를 나타내는 방식이다.
Big-O 주요 유형
| 표기법 | 설명 |
|---|---|
| O(1) | 데이터양과 상관없이 항상 동일한 속도 |
| O(n) | 데이터양(n)과 비례해서 증가 |
| O(n²) | 데이터양(n²)과 비례해서 증가 |
| O(log n) | 데이터양이 절반씩 줄어듦 |
자료구조별 기본 연산
- 자료구조는 접근, 검색, 삽입, 삭제 시 연산 속도가 전부 다르다.
| 자료구조 | 접근 | 검색 | 삽입 | 삭제 |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| LinkedList | O(n) | O(n) | O(1) | O(1) |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |
Array
List
LinkedList
Stack
Queue
Hi