CS 공부 기록 - 자료구조 (1)

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

1. 선형 자료구조 (linear data structure)

연속적으로 데이터가 나열되는 자료구조를 나타낸다. 하나의 데이터 뒤에 다른 하나의 데이터가 연결되며, 대표적인 자료구조는 배열, 리스트, 스택, 큐 등이 있다.

• 배열(array) : 정해진 크기만큼 데이터가 일렬로 저장되는 정적(static) 자료구조이다. 각 데이터를 요소(element)라고 하며 번호를 인덱스(index)라고 한다.
• 연결 리스트(linked list) : 대표적인 선형 자료구조로, 크기가 정해져 있지 않은 동적(dynamic) 자료구조이다. 여러 개의 노드(node)로 구성되며, 노드는 데이터와 다음 노드가 작성된 주소 값을 가지고 있다.
• 스택(stack) : 데이터를 쌓는 형태로, 마지막에 들어온 데이터가 먼저 나가는 LIFO(Last In First Out, 후입선출)형태의 자료구조이다. 웹 브라우저 방문 기록 등에 쓰인다. 
• 큐(queue) : 데이터가 순차적으로 들어오는 형태로, 먼저 들어온 데이터가 먼저 나가는 FIFO(First in First out, 선입선출) 형태의 자료구조이다. 
  
  • 큐를 사용하는 대표적인 예로, OS에서 프로세스가 CPU를 할당받기 전까지 대기하는 준비 큐가 있다. 이렇듯 어떠한 작업을 처리할 때 주로 큐를 사용한다.

 

2. 비선형 자료구조(non-linear data structure)

하나의 데이터 뒤에 N개의 데이터가 이어질 수 있는, 1:N 또는 N:N 구조로 데이터가 나열되는 자료구조를 뜻한다.

계층적 구조를 나타내기에 편리하며, 선형 자료구조와 달리 데이터를 하나하나 탐색하지 않아도 원하는 데이터를 찾을 수 있다는 장점이 있다. 그래프, 트리, 우선순위 큐, 힙, 해시 테이블등이 있다.

• 그래프(graph) : 그래프는 데이터를 포함하는 정점(vertex)과 정점을 잇는 간선(edge)로 구성된 자료구조이다. 정점은 노드(node)라고도 한다. 일반적으로 그래프는 G = (V, E)로 표현한다. 간선의 방향성 유무에 따라 무방향 그래프와 방향 그래프로 구분할 수 있다.
  • 무방향 그래프(undirected grapth): 무방향 그래프는 간선에 방향이 없는 그래프다. (A, B)와 (B, A)는 동일한 간선을 의미한다. 노드가 n개일때 간선의 개수는 n * (n - 1) / 2이다.
  • 방향 그래프(directed graph): 방향 그래프틑 간선에 방향이 있는 그래프다. 방향이 있으므로 <A, B>와 <B, A>는 다른 간선이다. 노드가 n개일때 간선의 개수는 n * (n - 1) 이다
  • 시작 정점이 주어졌을 때 간선을 거쳐 모든 정점을 탐색하는 그래프 탐색에 사용되는 방법은 BFS와 DFS가 있다.
    • BFS : 탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색하는 방식이다.
    • DFS : 시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색한다.
• 트리(tree) : 트리는 그래프의 한 종류로 사이클이 없어 계층적 관계를 표현할 수 있다.
  • 이진 트리(binary tree): 자식 노드가 최대 2개인 트리이다. 완전 이진 트리, 포화 이진 트리, 이진 탐색 트리 등이 있다.
• 우선순위 큐(priority queue) : 우선순위가 높은 데이터가 먼저 나오는 자료구조다. 큐와 동일하게 데이터 삽입과 삭제 연산을 지원한다. 삭제 연산을 수행하면 우선순위가 가장 높은 데이터를 얻을 수 있다.
  • 우선순위 큐를 구현하는 방식은 배열, 연결 리스트, 완전 이진 트리인 힙이 있다.
• 힙(heap) : 힙은 완전 이진 트리로, 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조이다. 우선순위 큐를 구현하는 데 자주 사용한다.
  • 최대 힙(max heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리다.
  • 최소 힙(min heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리다.
• 해시 테이블(hash table) : 하나의 키에 대해 하나의 값을 저장하는 형태의 자료구조이다. 키는 해시 함수를 사용해 해시를 얻을 수 있다. 해시는 값이 저장되어 있는 해시 테이블의 인덱스를 찾을 수 있는 값이다. 해시 테이블에는 해시 충돌이라는 단점이 있는데, 해시 충돌은 다른 키에 대해 같은 해시가 도출되는 것을 말한다. 이를 해결하기 위한 방법에는 체이닝과 개방 주소법이 있다.
  1. 체이닝(chaining) : 해시 충돌이 발생하면 같은 해시가 나오는 키의 값을 연결 리스트에 저장하는 방식이다.
  2. 개방 주소법(open addressing) : 해시 충돌이 발생했을 때 해당 해시가 아닌 비어 있는 공간에 값을 저장하는 방식이다.

 

트리와 그래프의 차이

 

그래프는 정점과 간선으로 구성된 자료구조. 루트 노드 개념이 없다.

트리는 그래프의 한 종류, 방향성이 있으며 사이클이 존재하지 않는다. 하나의 루트 노드가 존재한다.