CS 공부 - 자료구조

1. 자료구조

- 자료구조는 여러 데이터들을 저장하고 사용하는 방법을 정의한 것이다.

- 데이터를 체계적으로 저장하고, 효율적으로 활용하기 위해 사용한다.

- 자료구조는 선형 구조와 비선형 구조로 이루어진다.

 

(1) 선형 구조

- 자료를 구성하는 데이터를 순차적으로 나열시킨 형태를 의미한다.

- 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue) 등

 

(2) 비선형 구조

- 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 것을 의미한다

- 선형 구조가 아닌 형태를 의미한다.

- 그래프(Graph), 트리(Tree) 등

 

+ 시간 복잡도

- 프로그램의 성능을 파악하는 데에 사용되는 방법으로, 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 의미한다.

- 일반적으로 빅오 표기법을 사용한다.

---

2. Array와 Linked List

(1) Array

- 동일한 형태의 데이터를 순차적으로 저장하는 선형 자료구조이다.

- index로 데이터에 접근할 수 있어 원소의 인덱스 값을 알면 O(1)의 성능으로 접근할 수 있다.

- 삽입 또는 삭제 과정에서 각 데이터들을 shift 해줘야 하기 때문에 O(n)만큼 걸린다.

 

(2) Linked List

- 각 데이터를 포인터로 연결하여 관리하는 선형 자료구조이다. 

- 각 데이터들은 자신 다음에 어떤 데이터인지만을 기억하기 때문에 이 부분만 수정하면 삽입과 삭제는 O(1)로 해결할 수 있다.

- 원하는 위치에 한 번에 접근할 수 없다. 첫 번째 원소부터 확인해봐야 한다.

 

+ Array와 ArrayList 차이

- Array는 고정 길이 데이터 구조이다. 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르다.

- ArrayList는 가변 길이 데이터 구조이다. 데이터 추가 및 삭제 시 메모리를 재할당하므로 속도가 느리다.

---

3. 스택(stack)

- 후입선출(LIFO) 개념을 가진 선형 자료구조이다.

- 바구니 형태와 같이 데이터의 입구와 출구(top)가 하나로 구성되어 있다.

- 대표적으로 스택 메모리가 있다.

---

4. 큐(queue)

- 선입선출(FIFO) 개념을 가진 선형 자료구조이다.

- 터널 형태와 같이 한 쪽에는 입구(front), 다른 쪽에는 출구(rear)로 구성되어 있다.

- 선형큐, 환형큐 등이 있다.

 

+ 우선순위 큐

---

5. 트리(tree)

- 트리는 비선형 구조로, 계층적 관계를 표현하는 데에 적합한 비선형 자료구조이다.

---

6. 그래프(graph)

- 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다.

 

+ 트리와 그래프 차이점

트리는 사이클을 허용하지 않지만, 그래프는 사이클을 허용한다.

---

7. 해시 테이블(hash table)

- 해시 테이블은 키와 값을 받아 해시함수를 통해 나온 index에 값을 저장하는 자료구조이다.

---

8. 힙(heap)

- 이진 트리 형태를 가지며, 우선 순위가 높은 요소를 정렬해 최댓값, 최솟값 연산을 쉽게 하는 자료구조이다.