자료구조, 그것이 알고싶다.

자료구조를 영어로 표현하면 Data Structure이다.

자료구조는 데이터(Data)를 어떤 구조(Structure)로 효율적으로 저장할지? 관리하는 방법을 의미한다.

데이터 삽입, 수정, 삭제, 조회, 정렬, 병합, 순회와 같은 기본적인 연산을 지원한다.

 

자료구조에는 선형 자료구조와 비선형 자료 구조가 있다.

• 선형 자료구조: 말그래도 일렬로 나열한 자료 구조이다. 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue)
• 비선형 자료구조: 순서에 상관없이 계층 혹은 그래프 구조이다. 트리(Tree), 그래프(Graph)

자료구조가 나오면 항상 나오는 단어가 있다. 바로 알고리즘.

입력 데이터를 받아 원하는 결과를 출력하는 과정들을 알고리즘이라고 한다.

더 생각해보면, 입력을 받고 출력을 받는데까지 시간과 자원을 최소화해야 효율적인 알고리즘이라 할 수 있다.

 

알고리즘 수행시간은 최악의 경우의 입력에 대한 기본연산 횟수를 의미한다.

예를들어, 1부터 10까지의 숫자가 막 놓여져 있고 내가 '5'라는 숫자를 찾고싶다면?

최악의 경우 10번째에 찾을 수 있다... 그러니 수행시간은 Time을 T라고 했을 때 T(10) 라고 표현할 수 있다.

 

그럼 숫자가 n개까지 있을 땐?

최악의 경우 수행시간은 T(n)=n으로 표현된다.

 

파이썬에서 이루어지는 모든 연산들 예를들어 계산연산, 대입연산, 비교연산..등 각 모든 연산에 대해서 수행시간은 +1 씩 늘어난다.

그러니까 다음과 같은 코드가 있을 때,

a = 5         # 대입 연산 (1회)
b = 10        # 대입 연산 (1회)
c = a + b     # 덧셈 연산 (1회) + 대입 연산 (1회)
print(c)      # 출력 연산 (1회)

총 수행시간: 1 + 1 + 1 + 1 + 1 = 5

 

n = 5             # 대입 연산 (1회)
for i in range(n): # 반복문 (n회 반복)
    if i % 2 == 0: # 나머지 연산 (n회) + 비교 연산 (n회)
        print(i)   # 출력 연산 (n/2회, 짝수일 때만)

총 수행시간: 1 + n + n + n + n/2 = 3n + n/2 + 1

 

그런데말입니다....

이렇게보면 너무 복잡해보인다..

 

그래서!!!

 

함수값을 결정하는 최고차항만으로 간단하게 수행시간을 표기하는 방법이 Big-O 이다.

 

Big-O 표기법을 표현하는 규칙이 있다.

1. 최고차항만 남긴다.
2. 최고차항 계수(상수)는 생략한다.
3. O 를 붙인다.

그럼 위에서 3n + n/2 + 1 의 최고차항은 3n이고 상수를 생략하면 n, O 를 붙이면? O(n) !

 

아래는 Big-O 표기법 시간 복잡도 그래프이다.

 

 

이제 시간 복잡도에 대해 어느정도 이해하였으니, 자료구조 종류별로 시간복잡도와 특징을 알아보자.

 

 

배열(Array)  |  시간복잡도: O(1), O(n)

배열은 번호(인덱스)와 번호와 대응하는 데이터들로 이루어진 자료구조이다.

일반적으로 배열에는 같은 종류의 데이터들이 순차적으로 저장되어 있다.

값의 번호가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다.

 

저렇게 저장되어 있을 때 장점은?

연속된 메모리 블록에 저장되므로 인덱스를 통해 빠르게 접근이 가능한 장점이 있다.

 

장점이 있다면 단점도 있는법...

배열은 고정된 크기를 가지며, 나중에 크기를 늘릴 수 없다.
만약 크기를 늘려야 한다면, 새로운 배열을 만들어 기존 데이터를 복사해야 한다. 

 

파이썬에는 사실... 배열이라는 개념이 없다. 대신 리스트가 있다. 

 

리스트와 배열의 공통점

1. 순서가 있다: 리스트는 배열처럼 요소들이 순서대로 저장된다.
2. 인덱스로 접근 가능: 배열처럼 리스트에서도 인덱스를 통해 요소에 접근할 수 있다.

리스트와 배열의 차이점

1. 리스트는 동적 크기: 파이썬의 리스트는 배열과 달리 크기가 고정되어 있지 않아서, 필요에 따라 자동으로 크기를 늘리거나 줄일 수 있다. 그렇지만 크기를 늘릴 때, 기존 배열보다 더 큰 메모리를 할당하고 데이터를 복사하는 과정을 거친다.
2. 성능 비용: 배열에 비해 사용하기 더 편리하지만, 내부적으로 성능 비용이 추가될 수 있다.

 

연결 리스트(Linked List)  |  시간복잡도: O(1), O(n)

포인터를 가지는 노드들로 이루어진 자료구조이다.
1, 2, 3, 4, 5라는 linked list는 메모리공간에서 연속적이지 않으며 노드를 연결시키는 형태로 구현된다.

 

따라서 배열과 달리 유연하게 데이터를 삽입, 삭제할 수 있다는 장점이 있다.

그냥 1개의 메모리 공간에 숫자 '6'을 넣어주고 노드를 연결시키면 된다. 따라서 메모리공간에 관하여 배열보다 효율적이다.

그렇지만 연속적이지 않아 인덱스를 통해 접근할 때 배열보다는 시간이 조금 걸린다는 단점이 있다.

 

한방향: 단순 연결 리스트

양방향: 이중 연결 리스트 (대신 노드의 사이즈가 크다.) 이전과 다음 노드 위치 정보를 가지고 있으니까.

 

 

스택(Stack)  |  시간복잡도: O(1)

스택은 드럼통 모양을 생각하면 된다. 

드럼통에 차례대로 물건을 담고 다시 꺼낼 때, 가장 마지막에 담은 것을 먼저 꺼내게 된다. 후입선출이다.

메소드로는 push(삽입), pop(삭제), peek(확인) 이 있다. 

스택 사용예시) 웹브라우저 '뒤로가기' 기능

 

파이썬 스택 구현

class Stack:
    def __init__(self):
    	self.items = [] #데이터를 저장을 위한 리스트 준비
    
    def push(self, value):
    	self.items.append(value)
    
    def pop(self):
    	try:
        	return self.items.pop()
        except IndexError:
        	print("Stack is empty.")
    
    def top(self):
    	try:
        	return self.items[-1]
        except IndexError:
        	print("Stack is empty.")
    
    def __len__(self):
    	return len(self.items)

S = Stack
S.push(10)
S.pop()
print(len(S))

 

 

큐(Queue)  |  시간복잡도: O(1)

큐는 사람들이 줄 서 있는 것을 생각하면 된다.

스택과는 달리 선입선출이다.

메소드로는 enqueue, dequeue가 있다.

그리고 줄 서 있을 때, 가장 앞에 있는 사람을 front 그리고 방금 막 줄 선 사람을 rear 라고 생각하면 된다.

큐 사용예시) 티켓팅, 예약시스템

 

큐 파이썬 구현

class Queue:
	def __init__(self):
    	self.items=[]
        self.front_index = 0
    
    def enqueue(self, value):
    	self.items.append(value)
    
    def dequeue(self):
    	if self.front_index == len(self.items):
        	print("Q is empty")
        
        else:
       	    x = self.items[self.front_index]
            self.front_index += 1
            return x

 

 

트리(Tree)

트리란 노드들이 나무가지처럼 연결된 비선형 계층적 자료구조이다.

루트(Root)에서 시작하여 자식 노드(Child Node)로 연결되며, 부모-자식 관계로 표현한다.

트리 사용예시) 디렉토리와 파일 관리, 데이터베이스: B-트리, B+트리를 이용한 인덱스 관리

 

여러 트리 중에서 가장 많이 쓰이는 자료구조인 이진트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리이다.

 

트리의 특징

1. 노드의 연결:
   루트 노드: 트리의 시작점이 되는 최상위 노드.
   부모 노드(Parent): 자식 노드를 가진 노드.
   자식 노드(Child): 부모 노드에 의해 연결된 하위 노드.
   리프 노드(Leaf): 자식이 없는 노드.
2. 순환 없음(Acyclic): 트리는 순환(Cycle)이 없는 그래프

이진트리에도 또 다시 여러종류로 나뉘는데 그중 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있으며, 마지막 레벨은 왼쪽 노드부터 채워져 있어야 한다. 마지막 레벨은 꽉 차있을 필요는 없다.

 

그리고 완전 이진 트리 형태이며, 우선순위 큐를 위해 만들어진 자료구조를 힙이라 한다.

우선순위 큐(Priority Queue)는 데이터가 들어온 순서에 상관없이, 우선순위가 높은 데이터순으로 처리되는 구조이다.

 

최소 힙(Min-Heap): 부모 노드가 자식보다 작거나 같음.

최대 힙(Max-Heap): 부모 노드가 자식보다 크거나 같음.

 

힙에서 최소값, 최대값을 찾는 연산자체는 항상 Root에 있는 값이 되기때문에 이때의 시간복잡도는 O(1)이 된다.

하지만 힙에서 데이터의 삽입,삭제 연산을 할때는 이진트리에 데이터 N개가 있을때 1/2씩 인덱스를 줄여나가면서 삽입,삭제의 위치를 찾아나가기 때문에, 이때 시간복잡도는 O(logN)이 된다.

 

트리의 종류

1. 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식을 가지는 트리.
   예: 완전 이진 트리, 포화 이진 트리, 편향 이진 트리.
2. 이진 탐색 트리(Binary Search Tree, BST): 이진 트리의 특수한 형태로, 모든 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼.

 

그래프(Graph)

그래프는 여러 개의 정점(Vertex)와 이들을 연결하는 간선(Edge)으로 이루어진 자료구조이다.

여기서 Vertex는 위에서 표현된 노드(Node)로도 표현될 수 있다.

그래프 사용예시) 지하철 노선도 최단경로, 소셜 미디어

 

그래프 표현방법

 

• 인접 행렬(Adjacency Matrix):
  • 정점 간의 연결 관계를 2차원 배열로 표현.
  • 장점: 구현이 간단하며 간선 유무를 빠르게 확인 가능.
  • 단점: 메모리 소모가 큼(O(V^2)).
• 인접 리스트(Adjacency List):
  • 각 정점에 연결된 정점들의 리스트를 저장.
  • 장점: 메모리 효율적(O(V + E)).
  • 단점: 특정 간선의 유무를 확인하는 데 시간이 더 걸림.

 

그래프의 주요 알고리즘

• 탐색 알고리즘:
  DFS(Depth-First Search): 깊이 우선 탐색. 재귀나 스택을 사용.
  BFS(Breadth-First Search): 너비 우선 탐색. 큐를 사용.
• 최단 경로 알고리즘: 다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), 플로이드-와샬(Floyd-Warshall).
• 최소 신장 트리(Minimum Spanning Tree): 크루스칼(Kruskal), 프림(Prim).
• 위상 정렬(Topological Sort): 방향성이 있는 비순환 그래프(DAG)에서 정점의 선후 관계를 정렬.

주요 알고리즘 시간 복잡도

알고리즘	인접 행렬	인접 리스트
DFS	O(V^2)	O(V+E)
BFS	O(V^2)	O(V+E)
다익스트라(우선순위 큐 사용)	O(V^2)	O((V+E)⋅logV)