8. 자료구조

안녕하세요! 이번 포스팅에서는 자료구조에 대해 공부하고 정리해보겠습니다!

 

 

 

728x90

 

자료구조는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 말합니다.

 

# 복잡도

1. 시간 복잡도

* 빅오 표기법

시간 복잡도란 입력 크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간입니다. 주요 로직의 반복되는 횟수를 중점으로 측정합니다.

 

빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것입니다. 

 

- 시간 복잡도의 존재 이유 : 효율적인 코드로 개선하는 데 쓰이는 척도가 됩니다. 

ex) O(n^2) vs O(n)

 

보통 시간 복잡도를 생각할 때 평규느 최악의 시간 복잡도를 고려하여 사용합니다.

 

2. 공간 복잡도

프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말합니다. 정적 변수로 선언된 것 이외에 동적 재귀함수로 인해 지속적인 공간 할당이 필요한 부분도 이에 포함됩니다.

 

3. 선형 자료 구조

선형 자료 구조란 요소가 일렬로 나열되어 있는 자료구조를 말합니다. 

 

1. 연결 리스트

데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화 시킨 자료구조입니다. 맨 앞의 노드를 head라고 지칭합니다.

시간 복잡도 : 삽입/삭제 = O(1), 탐색 = O(n)

 

* 싱글 연결 리스트 : next 포인터만 가짐

* 이중 연결 리스트 : next, prev 포인터를 가짐

* 원형 이중 연결 리스트 : 이중 연결리스트와 같지만 마지막 노드의 next가 헤더를 가리킵니다.

 

2. 배열

같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합입니다. 중복을 허용하고 순서가 존재합니다.

 

시간 복잡도 : 접근에 O(1), 삽입/삭제는 O(n)

 

랜덤 접근(직접) : 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능

순차적 접근 : 순서대로 검색해야하는 기능

 

배열과 다르게 연결 리스트는 데이터 구조 안의 요소를 알기 위해서는 하나씩 내부를 확인해봐야 한다는 점이 다릅니다.

 

3. 벡터

동적으로 요소를 할당할 수 있는 동적 배열입니다. 컴파일 시점에서 개수를 모른다면 벡터를 사용해야 합니다. 중복을 허용하고 순서가 있으며 랜덤 접근이 가능합니다. 탐색, 맨 뒤의 요소를 삭제/삽입시 O(1), 이외의 삭제/삽입시 O(n)의 시간복잡도가 생깁니다.

 

4. 스택

가장 마지막에 들어간 데이터가 가장 먼저 나오는 LIFO 후입 선출의 구조를 가지고 있습니다. 웹 브라우저 방문기록 등에 사용됩니다.

 

시간 복잡도 : 삽입,삭제에 O(1), 탐색에 O(n)이 걸립니다.

 

5. 큐

먼저 집어넣은 데이터가 가장 먼저 나오는 성질 FIFO 선입선출의 구조를 가지고 있습니다. 

 

시간 복잡도 : 삽입,삭제에 O(1), 탐색에 O(n)이 걸립니다.

 

CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용됩니다.

 

 

4. 비선형 자료 구조

자료구조를 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말합니다.

 

1. 그래프

정점과 간선으로 이루어진 데이터 구조를 말합니다. 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을때, 어떠한 곳은 정점이 되며 무언가는 간선(단방향, 양방향)이 됩니다.

 

* 가중치

간선과 정점에 드는 비용을 뜻합니다. 1 ~ 2 노드 사이 가는 비용이 1칸이라면 가중치는 1이 됩니다. 

 

2. 트리

그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있으며, 트리 구조로 배열된 일종의 계층적 데이터 집합입니다. 트리로 이루어진 집합을 숲이라고 하며 루트 노드, 내부 노드, 리프(자식이 없는) 노드 등으로 구성됩니다. 

 

* 트리의 특징

1. 부모, 자식의 계층 구조를 가집니다.

2. 간선 수 = 노드 수 - 1

3. 트리 내의 노드 간 경로는 반드시 존재합니다.

 

깊이 : 루트 노드로 부터 특정 노드간의 최단 거리

높이 : 루트 ~ 리프 노드까지 거리 중 가장 긴 거리

레벨 : 깊이와 같은 의미

서브트리 : 트리 내의 하위 집합

 

# 이진트리 : 자식의 노드 수가 2개 이하인 트리

1. 정이진 트리 : 자식의 노드 수가 0 or 2

2. 완전 이진 트리 : 왼쪽에서부터 채워져 있는 이진 트리를 의미

3. 변질 이진 트리 : 자식 노드가 하나만 있는 이진 트리

4. 포화 이진 트리 : 모드 노드가 꽉 차 있는 이진 트리

5. 균현 이진 트리 : 왼쪽과 오른쪽의 높이 차이가 1 이하

 

* 이진 탐색 트리(BST)

노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리를 말합니다. 

* AVL 트리

최악의 경우 선형 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리입니다. 두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있습니다.

* 레드블랙 트리

균형 이진 탐색 트리로 모두 시간 복잡도가 O(logn) 입니다. 각 노드를 빨강, 검정 색상을 추가하는 비트를 저장해 트리가 균형을 유지하도록 사용됩니다.

 

힙

완전 이진 트리 기반의 자료 구조이며, 최소힙(루트는 모든 자식보다 최소)과 최대힙(루트는 모든 자식보다 최대) 두 가지가 있고 해당힙에 따라 특정한 특징을 지닌 트리입니다.

 

* 최대힙의 삭제 : 최대힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 해당 과정을 거쳐 재구성 됩니다.

 

3. 우선순위 큐

우선순위 대기열, 대기열에서 우선순위가 높은 요소가 우선 순위보다 먼저 제공되는 자료구조입니다. 우선순위 큐는 힙을 기반으로 구현됩니다. 

 

4. 맵

특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조입니다. 

 

5. 셋

특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소는 없고 희소한 값만 저장하는 자료 구조입니다.

 

6. 해시 테이블

무한에 가까운 수 많은 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블입니다. 

 

 

이번 포스팅은 여기서 마무리하겠습니다! 감사합니다.