[CS] 자료구조 총정리

4.1 복잡도

1. 복잡도와 빅오 표기법 ⭐

알고리즘을 수행하면 시간과 메모리 공간 등의 자원이 사용된다.

알고리즘이 얼마나 효율적인지 정량화하는 데 시간 복잡도와 공간 복잡도라는 개념을 사용한다.

알고리즘의 복잡도는 주로 빅오 표기법으로 나타낸다.

 

🤔 시간복잡도?

알고리즘의 실행 시간을 정량화하는 것

 

🤔 공간 복잡도?

실행하는 데 필요한 메모리 사용량을 정량화하는 것이다.

 

🤔 빅오 표기법?

입력 값(n)에 대한 수식에서 최고차항을 기준으로 알고리즘이 수행되는 최악의 시간 복잡도

 

빅오 표기법으로 나타낼 때 최고차항을 기준으로 하는 이유는

연산의 수가 극한에 수렴할 때 나머지 항이 복잡도에 미치는 영향이 미미하기 때문이다.

 

대표적인 빅오 표기법에는 O(1), O(logn), O(n), O(nlogn), O(n^2), O(2^n), O(n!)이 있다.

 

4.2 선형 자료구조

1. 배열 ⭐⭐

선형 자료구조는 연속적으로 데이터가 나열되는 자료구조를 나타낸다.

즉, 하나의 데이터 뒤에 다른 하나의 데이터가 연결되는 배열, 리스트, 스택, 큐 등이 있다.

 

배열은 정해진 크기만큼 데이터가 일렬로 저장되는 정적 자료구조다.

 

각 데이터: 배열의 요소

인덱스: 데이터를 가리키는 번호

 

접근 O(1)

검색 O(n)

삽입 O(n), 해당 위치에 데이터를 저장할 수 있는 공간이 있다면 O(1)

삭제 O(n), 삭제하려는 데이터가 마지막 데이터라면 O(1)

 

2. 연결 리스트 ⭐⭐

연결리스트는 배열과 달리 크기가 정해져 있지 않은 동적 자료구조

연결 리스트가 여러 개의 노드로 구성되어 있기 때문이다.

 

연결 리스트는 헤드 포인터와 테일 포인터로 시작과 끝을 알 수 있다.

 

검색 O(n)

추가 맨 앞 데이터를 추가하는 경우 O(1), 나머지 위치에 노드를 추가하는 경우 O(n)

삭제 첫 번째 데이터를 삭제하는 경우 O(1), 해당 위치까지 이동하기 위한 연산 최대 O(n)

 

3. 스택 ⭐⭐⭐

스택은 데이터를 쌓는 형태, 마지막에 들어온 데이터가 먼저 나가는 LIFO(Last In First Out) 후입선출 구조

 

스택에 데이터를 삽입하는 연산 push

스택에 데이터를 삭제하는 연산 pop

 

스택은 top이라는 변수를 이용해서 데이터를 마지막으로 저 정한 인덱스를 기억한다.

push나 pop 연산을 할 때 배열을 이용해도 O(1)로 마지막 데이터에 접근할 수 있다.

 

4. 큐 ⭐⭐⭐

큐는 데이터가 순차적으로 들어오는 형태, 먼저 들어온 데이터가 먼저 나가는 FIFO(First in First out) 선입선출 구조

큐의 맨 앞을 front, 큐의 맨 뒤를 rear

 

큐에 데이터를 추가하면 큐의 맨 뒤에 데이터가 삽입되는데 이를 enqueue

큐에서 데이터를 삭제하면 큐의 맨 앞에서 삭제되며 이를 dequeue

 

큐를 사용하는 대표적인 예)

운영체제에서 프로세스가 CPU를 할당받기 전까지 대기하는 준비 큐가 있다.

 

4.3 비선형 자료구조

1. 그래프 ⭐⭐⭐

 

인접: 두 정점이 간선으로 연결되어 있으면 인접

차수: 정점에 연결된 간선의 수

진입 차수: 해당 정점으로 향하는 간선의 수

진출 차수: 해당 정점에서 나가는 간선의 수 

경로: 한 정점에서 다른 정점으로 이어지는 정점들의 리스트

경로 길이: 경로를 구성하는 간선의 수

단순 경로: 모두 다른 정점으로 구성된 경로

사이클: 한 정점에서 시작해 같은 정점으로 돌아올 수 있는 경로

 

1. 무방향 그래프

간선에 방향성이 없는 그래프

최대 간선의 개수는 n x (n - 1) / 2

 

2. 방향 그래프

간선에 방향성이 있는 그래프

최대 간선의 개수는 n x (n - 1) 

 

경로탐색

너비 우선 탐색(BFS)

탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색하는 방식이다.

먼저 발견한 정점과 인접한 정점들을 탐색하면서 큐에 삽입한다.

 

깊이 우선 탐색(DFS)

시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색한다.

재귀 호출 또는 스택으로 구현할 수 있다.

 

2. 트리 ⭐⭐⭐

그래프의 한 종류로 사이클이 없어서 계층적 관계를 표현할 수 있다.

 

이진트리

자식 노드가 최대 2개인 트리다.

 

- 완전 이진트리

트리의 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있으며, 마지막 레벨은 안쪽에서부터 오른쪽으로 노드가 채워져 있는 이진트리다.

 

- 포화 이진트리

마지막 레벨까지 노드가 모두 채워져 있는 이진트리다.

 

- 이진 탐색 트리

왼쪽 서브 트리는 해당 노드의 값보다 작은 값을 가진 노드로 구성되고,

오른쪽 서브 트리는 해당 노드의 값보다 큰 값을 가진 노드로 구성된 트리다.

 

3. 우선순위큐 ⭐⭐

우선순위가 높은 데이터가 먼저 나오는 자료구조다.

구현하는 방식은 배열, 연결 리스트, 완전 이진트리인 힙이 있다.

 

4. 힙 ⭐⭐⭐

완전 이진트리로, 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조다.

최대 힙: 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진트리다.

최소 힙: 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진트리다.

 

5. 해시 테이블 ⭐⭐⭐

하나의 키에 대해 하나의 값을 저장하는 형태의 자료 구조다.