[ 자료구조 ] 선형 자료구조 & 비선형 자료구조

선형 자료구조

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

 

배열(array)

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

 

🔍 용어

요소(element)	각각의 데이터
인덱스(index)	데이터를 가리키는 번호

 

 

🔍 연산

연산	설명	시간복잡도
접근	특정 인덱스에 접근	O(1)
검색	데이터를 검색	O(n)
삽입	특정 위치에 데이터 삽입	O(n)
삭제	데이터 삭제	O(n)

 

 

연결 리스트(linked list)

대표적인 선형 자료구조의 하나로 배열과 달리 크기가 정해져 있지 않은 동적 자료구조이다.

 

🔍 용어

노드(node)	데이터와 다음 노드가 저장된 주소값을 가짐
헤드(head) 포인터	첫 번째 노드를 가리킨다.
테일(tail) 포인터	마지막 노드를 가리킨다.

 

 

🔍 연산

연산	설명	시간복잡도
검색	데이터를 검색	O(n)
추가	특정 위치에 데이터 삽입	O(1), 자리를 찾아가는데는 O(n)
삭제	데이터 삭제	O(1), 자리를 찾아가는데는 O(n)

 

💡 배열과 연결 리스트의 차이점

• 배열은 정적 자료구조로 크기가 정해져 있다.
• 연결리스트는 동적 자료구조로 크기가 정해져있지 않다.
• 배열은 특정 인덱스에 접근은 쉽지만, 삽입과 삭제 연산시에 나머지 데이터를 옮겨야하기 때문에 연산이 복잡하다.
• 연결리스트는 인덱스가 따로 없어 특정 인덱스에 접근은 어렵지만, 삽입과 삭제 연산은 쉽다.
  삽입하려는 위치 전 노드의 포인터를 삽입하려는 데이터 주소로 바꾸고 삽입하려는 데이터 주소의 포인터를 다음 노드 주소로 변경한다.

 

스택(stack)

데이터를 쌓는 형태로, 마지막에 들어온 데이터가 먼저 나가는 LIFO 형태의 자료구조이다.

 

 

🔍 연산

연산	설명	시간복잡도
push	새로운 데이터 삽입	O(1)
pop	가장 위에 있는 데이터 삭제	O(1)
peek	가장 위에 있는 데이터 확인	O(1)
isEmpty	스택이 비어있는지 확인	O(1)
isFull	스택이 가득 찼는지 확인	O(1)

 

 

큐(queue)

데이터가 순차적으로 들어오는 형태로, 먼저 들어온 데이터가 먼저 나가는 FIFO 형태의 자료구조이다.

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

 

🔍 용어

front	큐의 맨 앞
rear	큐의 맨 뒤

 

 

🔍 연산

연산	설명	시간복잡도
enqueue	rear에 새로운 데이터 삽입	O(1)
dequeue	front에서 데이터 삭제	O(1)
peek	front에 있는 데이터 확인	O(1)
isEmpty	큐가 비어있는지 확인	O(1)
isFull	큐가 가득 찼는지 확인	O(1)

 

 

덱(deque)

양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능한 자료구조로, 큐와 스택을 합친 형태다.

 

🔍 용어

front	덱의 맨 앞
rear	덱의 맨 뒤

 

 

 

 

비선형 자료구조

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

 

그래프(graph)

데이터를 포함하는 정점(노드)과 정점을 잇는 간선으로 구성된 자료구조이다.

 

🔍 용어

인접(adjacent)	두 정점이 간선으로 연결되어 있는 상태
차수(degree)	정점에 연결된 간선의 수
진입 차수(in-degree)	해당 정점으로 향하는 간선의 수
진출 차수(out-degree)	해당 정점에서 나가는 간선의 수
경로(path)	한 정점에서 다른 정점으로 이어지는 정점들의 리스트
경로 길이(path length)	경로를 구성하는 간선의 수
단순 경로(simple path)	모두 다른 정점으로 구성된 경로
사이클(cycle)	항 정점에서 시작해 같은 정점으로 돌아올 수 있는 경로

 

 

무방향 그래프

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

최대 간선의 개수 = n * (n - 1) / 2(방향 X)

 

EX) (A, B)와 (B, A)는 동일한 간선을 의미한다.

 

 

방향 그래프

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

최대 간선의 개수 = n * (n - 1)

 

EX) A에서 B로 향하는 간선을 <A, B>로 표기하고, <A, B>와 <B, A>는 다른 간선을 의미한다.

 

 

경로 탐색

시작 정점이 주어졌을 때 간선을 거쳐 모든 정점을 탐색하는 경로를 탐색

 

너비 우선 탐색(BFS)

탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색

• 주로 큐를 사용한다.
• 방문한 배열을 체크하는 방문배열과, 인접리스트로 해당 노드에 연결되어있는 노드들을 저장해둔다.
• 비가중치 그래프에서 시작 정점부터 특정 정점까지의 최단 거리를 알 수 있다.

 

깊이 우선 탐색(DFS)

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

• 주로 스택이나 재귀 호출을 사용한다.
• 방문한 배열을 체크하는 방문배열과, 인접리스트로 해당 노드에 연결되어있는 노드들을 저장해둔다.
• 특정 정점에서 다른 정점까지의 경로를 알 수 있다.

 

 

트리

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

 

이진 트리(binary tree)

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

• 완전 이진 트리 : 마지막 레벨을 제외한 모든 레벨이 노드가 채워져있고, 마지막 레벨은 왼쪽이 채워져 있는 이진트리
• 포화 이진 트리 : 마지막 레벨까지 노드가 모두 채워져 있는 이진 트리
• 이진 탐색 트리(BST) : 왼쪽 서브 트리는 해당 노드의 값보다 작은 값을 가진 노드로 구성되고 오른쪽 서브 트리는 해당 노드의 값보다 큰 값을 가진 노드로 구성된 트리
• AVL 트리 : 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이를 유지해 균형을 잡는 트리, 최대 높이 차이는 1

 

 

우선순위 큐

우선순위가 높은 데이터가 먼저 나오는 자료구조(큐는 먼저 들어간 데이터가 나오고, 이건 우선순위가 높은게 나옴)

• 주로 삽입과 삭제 연산에서 시간복잡도가 O(log n)인 힙을 사용한다.

 

힙

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

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

 

 

해시 테이블

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

• 키는 해시 함수를 사용해 해시를 얻을 수 잇다.
• 해시는 값이 저장되어 있는 해시 테이블의 인덱스를 찾을 수 있는 값이다.
• 키 -> 해시 함수 -> 인덱스 -> 인덱스에 있는 값 찾음

 

해시 충돌

서로 다른 키에 대해 같은 해시가 도출되는 것

 

💡 해시 충돌 문제를 해결하는 방법 2가지

1. 체이닝(chaining)
   같은 해시가 나오는 키의 값을 연결 리스트에 저장하는 방식이다.
   장점 : 연결 리스트에 노드를 저장해 저장 공간에 대한 제약이 적다.
   단점 : 하나의 해시에 여러 노드가 몰릴 수 있다.
   
   
2. 개방 주소법(open addressing)
   해시 충돌이 일어났을 때 해당 해시가 아닌 비어있는 다른 공간에 값을 저장한다.
   
   • 선형 조사법 : h[n]에서 해시 충돌 발생 -> h[n+1], h[n+2]와 같이 다음 인덱스로 이동하면서 빈공간 찾음
   • 이차 조사법 : h[n]에서 해시 충돌 발생 -> h[n+1*1], h[n+2*2]와 같이 거듭제곱한 만큼 다음 인덱스로 이동하면서 빈공간 찾음
   • 이중 해싱 : 해시 충돌 발생 -> 다른 해시 함수를 한 번 더 적용해서 저장

 

아무래도 내용이 너무 많음...