[WEEK 1] 자료구조

1. Array

▶ 개념과 특징

: 같은 타입의 데이터를 나열한 선형 자료구조이다.

  연속된 메모리 공간에 순차적으로 저장할 배열의 크기는 선언할 때 정하고 변경할 수 없다.

 

▶ 시간복잡도

- 배열의 맨 앞에 삽입/삭제하는 경우 : O(n)

- 배열의 맨 뒤에 삽입/삭제하는 경우 : O(1)

- 배열의 중간에 삽입/삭제하는 경우 : O(n)

- 탐색하는 경우 : O(1)

 

▶ 장점

- 인덱스를 가지고 있어 바로 접근할 수 있다. (시간복잡도 O(1))

- 자료구조의 크기가 클수록 더 강력한 장점이 된다.

- 연속된 메모리 공간에 존재하기 때문에 관리하기가 편하다.

 

▶ 단점

- 삽입과 삭제가 어렵고 오래 걸린다.

- 데이터 삽입 또는 삭제 시 해당 원소 이후의 모든 원소들을 한칸씩 밀거나 당겨야 한다.

- 배열의 크기를 바꿀 수 없다. 크기를 변경하기 위해서는 원하는 크기의 새로운 배열을 선언한 뒤에 값을 복사해야 한다.

- 연속된 메모리라서 공간 낭비가 발생할 수 있다.

  (처음에 크기를 100으로 선언했는데 실제로는 10정도만 쓰면 나머지 공간을 낭비하게 된다.)

 

▶ 언제 사용?

- 데이터의 개수가 확실하게 정해져 있을 때

- 데이터의 삽입과 삭제가 적을 때

- 검색을 해야 할 때

---

2. Linked List

▶ 개념과 특징

: 연결 리스트는 자료들을 임의의 기억공간에 저장하되 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다. 
- 첫번째 노드를 헤드(Head, 머리), 마지막 노드를 테일(Tail, 꼬리)이라고 한다.
- 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져있다.
- 크기가 고정되어 있지 않고, 새로운 요소를 크기가 정해져 있지 않으므로 새로운 요소를 쉽게 추가할 수 있다.
- 인덱스 접근이 불가능하다.

 

▶ 시간복잡도

- 리스트의 맨 앞/뒤에 삽입하는 경우 : O(1) 
- 리스트의 중간에 삽입하는 경우 : O(n) (탐색하는 시간) 
- 리스트의 맨 앞/뒤에서 삭제하는 경우 : O(1) 
- 리스트의 중간에서 삭제하는 경우 : O(n) (탐색하는 시간) 
- 탐색하는 경우: O(n) 

 

▶ 장점

- 삽입과 삭제가 용이하다. (포인터로 연결되어 있어서 포인터가 가리키는 노드만 변경해주면 됨)
- 크기가 정해져 있지 않고 동적으로 생성한다.
- 연속적인 메모리 할당이 필요하지 않다,
- 사용한 메모리 재사용 가능하다.

 

▶ 단점

- 원소를 탐색할 때 임의 접근이 불가능하다. ([], .at(i)등, 반복자를 이용하여 탐색하기 때문에 검색 성능이 좋지 않음) 
- 포인터로 인하여 저장 공간의 낭비가 발생한다.

 

▶ 언제 사용?

- 크기가 정해져 있지 않을 때 
- 삽입과 삭제가 자주 일어날 때 
- 검색을 자주 하지 않을 때 

---

3. Stack

▶ 개념과 특징

- LIFO (Last In First Out) 구조 : 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 구조
- 스택에 데이터를 push하면 항상 top에 들어가고, pop하면 가장 최근에 푸시한 데이터가 나오는 구조이다.
- 맨 위 요소만 접근할 수 있다.
- 자료가 없을 때 pop하는 오류를 stack underflow라고 한다.
- 스택의 크기 이상의 자료를 push 하려고 할 때의 오류를 stack overflow라고 한다.

 

▶ 시간복잡도

- 맨 위 원소를 삽입/삭제하는 경우 : O(1) 
- 중간에 삽입/삭제하거나 탐색하는 것은 stack의 목적에 맞지 않다.

 

▶ 장점

- 데이터의 삽입과 삭제가 빠르다. (맨 위 원소 접근 O(1)) 

 

▶ 단점

- 탐색을 하려면 원소를 하나하나 꺼내서 옮겨가면서 해야 한다.
- 맨 위의 원소만 접근 가능하다.

 

▶ 언제 사용?

- 재귀 알고리즘에서 유용하게 사용 
- 역추적을 해야할 때 (ex. 문서 작업 시 실행 취소) 
- DFS (너비 우선 탐색) 구현할 때 

---

4. Queue

▶ 개념과 특징

- FIFO(First-In-First-Out) 구조 : 먼저 넣은 데이터가 먼저 나오는 구조이다.
- push와 pop이 다른 곳에서 된다.

 

▶ 시간복잡도

- 원소를 삽입/삭제하는 경우 : O(1) 
- 중간에 삽입/삭제하거나 탐색하는 것은 queue의 목적에 맞지 않다.

 

▶ 장점

-  데이터의 삽입/삭제가 빠르다. O(1)

 

▶ 단점

- queue의 중간에 위치한 데이터로의 접근이 어렵다.
(참고) 배열로 구현했을 때
    ▷ 선형 큐

    - Front는 고정, Back을 이동하면서 데이터를 삭제하는 경우: 데이터를 제거했을 때, 나머지 데이터를 한 칸씩 다 옮겨야 함 
    - 둘 다 이동하면서 삽입, 삭제를 할 경우 : 배열의 끝에 저장되어 있는 상황되면, Back을 더 이상 이동시킬 수 없어서 overflow 발생 
    ▷ 순환 큐(환형 큐)

    - 선형 큐를 보완하기 위한 방식. front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내서 원형으로 연결

 

▶ 언제 사용?

- 데이터를 입력된 순서대로 처리해야 할 때 
- BFS (너비 우선 탐색) 구현할 때 

---

5. Deque

 

▶ 개념과 특징

- Deque(Double Ended Queue)는 front와 end에서 삭제와 삽입이 모두 가능한 구조이다.

 

▶ 시간복잡도

- 원소를 앞/뒤에 삽입하는 경우 : O(1) 
- 원소를 앞/뒤에 삽입하는 경우 : O(1) 
- 원소를 탐색하는 경우 : O(1) (index 접근)

 

▶ 장점

-  데이터의 삽입과 삭제가 빠르다. 
- 크기가 가변적이다. 
- 앞, 뒤에서 데이터를 삽입/삭제할 수 있다. 
- index로 임의 원소 접근이 가능하다. 
- 새로운 원소 삽입 시에, 메모리를 재할당하고 복사

 

▶ 단점

- deque의 중간에서의 삽입과 삭제가 어렵다.
- 구현이 어렵다

 

▶ 언제 사용?

- 앞과 뒤에서 삽입, 삭제가 자주 일어나는 경우 
- 데이터의 개수가 가변적일 경우 
- 데이터 검색을 거의 하지 않을 경우 (랜덤 요소에 접근해야할 때) 

 

---