3강. 자료구조(data structure)
추천글 : 【알고리즘】 알고리즘 목차
1. 개요 [본문]
2. 배열 [본문]
3. linked list [본문]
4. 스택 [본문]
5. 큐 [본문]
6. 트리 [본문]
7. 그래프 [본문]
8. 해시 [본문]
9. 셋 [본문]
a. Java 자료구조
1. 개요 [목차]
⑴ 기본 연산
① append
② pop
③ insert
④ remove
⑤ get
⑥ size
⑵ 주요 자료구조 비교
self-mutablility (저장 용량이 변경 가능한지) |
mutability of element |
repeatability of element |
|
str | X | X | O |
list | O (e.g., resizing) | O | O |
tuple | X | O | O |
dictionary | O (e.g., append) | key : X, value : O | X |
set | O (e.g., append) | X | X |
Table. 1. 주요 자료구조 비교
2. 배열(array) [목차]
⑴ 단점 1. 고정된 길이
⑵ 단점 2. array resizing
① 배경
○ 메모리 낭비 : 만일 원소의 개수가 너무 적으면 불필요하게 낭비되는 메모리 낭비가 있음
○ 메모리 부족 : 만일 원소의 개수가 너무 많으면 배열에 모든 원소를 담을 수 없음
○ 이 이유로 array resizing이 필요함
② array resizing expense 이슈
○ array resizing의 빈도를 최소화하기 위해 array resizing 정도를 array 크기에 비례하도록 함
○ 해결 방법 : 파이썬의 경우 array resizing을 0, 4, 8, 16, 25, 35, 46, 58, ···과 같이 함
3. 연결된 리스트(linked list) [목차]
⑴ 개요
① C 언어는 기본적으로 array를 제공
② Python은 기본적으로 linked list를 제공
③ 단점 : navigation이 번거로움
④ 해결 방법 : caching
⑵ 3-1. SLList(single linked list)
① 구성 : 노드에 저장된 변수, 다음 노드를 가리키는 포인터
② 연산
○ addFirst(x) : 앞에서 추가
○ getFirst() : 맨앞의 값을 추출
○ getSize() : 연결된 리스트의 크기를 반환
○ append(x) : 끝에서 추가
③ 알고리즘 (Python)
class LinkedNode():
def __init__(self,x):
self.val = x
self.next = None
class SLList():
def __init__(self)->None:
self.sentinel = LinkedNode(0)
self.size = 0
def addFirst(self, x:int)->None:
newFirst = LinkedNode(x)
newFirst.next = self.sentinel.next
self.sentinel.next = newFirst
self.size += 1
def getFirst(self)->int:
if self.sentinel.next:
return self.sentinel.next.val
return None
def getSize(self)->int:
return self.size
def append(self, x:int)->None:
self.size += 1
curNode = self.sentinel
while curNode.next != None:
curNode = curNode.next
curNode.next = LinkedNode(x)
⑶ 3-2. DLList(doubly linked list)
① 구성 : 노드에 저장된 변수, 이전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터
② 알고리즘 (Python) (추후 업데이트)
class LinkedNode():
def __init__(self,x):
self.val = x
self.left = None
self.right = None
4. 스택(stack) [목차]
⑴ 정의 : LIFO(last-in first-out) 원리를 취하는 자료구조
① array, list 중 어떤 것으로 구현하는지를 불문
⑵ 연산
① push(x) : 맨 앞에 특정 값의 원소를 추가
② pop() : 첫 번째 원소를 추출하고 그 원소를 제거
③ top()
④ getSize()
⑤ isEmpty()
⑶ 알고리즘 (Python)
class LinkedNode():
def __init__(self,x):
self.val = x
self.next = None
class Stack():
def __init__(self)->None:
self.sentinel = LinkedNode(0)
self.size = 0
def push(self, x:int)->None:
self.size += 1
curNode = self.sentinel.next
self.sentinel.next = LinkedNode(x)
self.sentinel.next.next = curNode
def pop(self)->int:
self.size -= 1
if not self.sentinel.next:
return None
curNode = self.sentinel.next
self.sentinel.next = curNode.next
return curNode.val
def top(self)->int:
if not self.sentinel.next:
return None
return self.sentinel.next.val
def getSize(self)->int:
return self.size
def isEmpty(self)->bool:
return self.size==0
5. 큐(queue) [목차]
⑴ 정의 : FIFO(first-in first-out) 원리를 취하는 자료구조
① array, list 중 어떤 것으로 구현하는지를 불문
⑵ 연산
① enqueue(x) : 맨 끝에 특정 값의 원소를 추가
② dequeue() : 첫 번째 원소를 추출하고 그 원소를 제거
③ top()
④ getSize()
⑤ isEmpty()
⑶ 알고리즘 (Python)
class LinkedNode():
def __init__(self,x):
self.val = x
self.next = None
class Queue():
def __init__(self)->None:
self.sentinel = LinkedNode(0)
self.size = 0
def enqueue(self, x:int)->None:
self.size += 1
curNode = self.sentinel
while curNode.next != None:
curNode = curNode.next
curNode.next = LinkedNode(x)
def dequeue(self)->int:
self.size -= 1
if not self.sentinel.next:
return None
val = self.sentinel.next.val
self.sentinel.next = self.sentinel.next.next
return val
def top(self)->int:
if not self.sentinel.next:
return None
return self.sentinel.next.val
def getSize(self)->int:
return self.size
def isEmpty(self)->bool:
if self.sentinel.next:
return False
return True
6. 트리(tree) [목차]
⑴ 개요
① 정의 : 두 개의 노드 간에 오직 한 개의 경로만 존재하는 경우
② 한 개의 노드만 있는 경우에도 트리로 인정
③ parent : 모든 node는 하나의 parent를 가짐
④ leaf : child가 없는 node
⑵ 종류
① rooted tree : 트리의 맨 꼭대기에 root를 두어 트리에 방향성이 생기게 된 경우
Figure. 1. ⒜ unrooted tree와 ⒝ rooted tree
② rooted binary tree : 각각의 노드가 최대 두 개의 children node를 가지는 경우
③ BST(binary search tree) : 아래 참고
④ balanced BST : 최대한 퍼져 있는 BST로 balanced BST의 search 알고리즘의 시간복잡도는 O(log n)
⑤ k-ary tree : 자녀의 개수가 최대 k개인 트리
class TreeNode():
def __init__(self, x:int, k:int)->None:
self.val = x
self.arity = k
self.child = [None]*k
⑥ m-원 검색 트리(m-Way Search Tree)
○ 한 노드가 1개의 키 값과 2개의 서브 노드를 갖는 이진 검색 트리를 일반화한 트리
○ 한 노드가 최대 m-1개의 키 값과 최대 m개의 서브 노드를 가짐
⑦ B 트리
⑧ B* 트리
○ B 트리의 문제점인 빈번한 노드의 분할을 줄이는 목적으로 제시된 B 트리의 변형
⑨ B+ 트리
○ B 트리의 변형
○ 단말 노드가 아닌 노드로 구성된 인덱스 세트(Index Set)와 단말 노드로만 구성된 순차 세트(Sequence Set)로 구분
○ 단말노드끼리 포인터로 연결돼 있어 B 트리와 달리 직접 접근과 순차 접근을 모두 지원
⑶ BST(binary search tree)
① 조건
○ 각 노드의 값이 고유한 값이어야 함
○ 특정 노드의 왼쪽 subtree의 모든 값이 그 노드의 값보다 작아야 함
○ 특정 노드의 오른쪽 subtree의 모든 값이 그 노드의 값보다 커야 함
② 연산
○ search(x)
○ insert(x)
○ delete(x)
○ 전략 1. 주어진 값을 가지는 노드 curNode 탐색 → curNode의 왼쪽 subtree에서 맨 오른쪽 노드 rightMostNode 탐색 → rightMostNode의 왼쪽 subtree에서 맨 왼쪽 노드 leftMostNode 탐색 → leftMostNode의 left를 curNode의 left와 일치시킴 → rightMostNode의 right를 curNode의 right와 일치시킴 → rightMostNode를 반환
Figure. 2. binary search tree의 delete 구현 전략 1
○ 전략 2. 주어진 값을 가지는 노드 curNode 탐색 → curNode의 오른쪽 subtree에서 맨 왼쪽 노드 leftMostNode 탐색 → leftMostNode의 오른쪽 subtree에서 맨 오른쪽 노드 rightMostNode 탐색 → rightMostNode의 right를 curNode의 right와 일치시킴 → leftMostNode의 left를 curNode의 left와 일치시킴
③ 생성 알고리즘 (Python) : 전략 1의 delete 방식을 따름
class TreeNode():
def __init__(self,x):
self.val = x
self.left = None
self.right = None
### K-ary Trees ###
# self.arity = k
# self.child = [None]*k
class BST():
def __init__(self):
self.root = None
def search(self, x:int)->TreeNode:
return self.__searchHelp(self.root, x)
def __searchHelp(self, curNode: TreeNode, x)->TreeNode:
if not curNode:
return None
if x == curNode.val:
return curNode
elif x < curNode.val:
return self.__searchHelp(curNode.left, x)
else:
return self.__searchHelp(curNode.right, x)
def insert(self, x:int)->None:
self.root = self.__insertHelp(self.root, x)
def __insertHelp(self, curNode:TreeNode, x:int)->TreeNode:
if not curNode:
return TreeNode(x)
if x < curNode.val:
curNode.left = self.__insertHelp(curNode.left, x)
elif x > curNode.val:
curNode.right = self.__insertHelp(curNode.right, x)
else:
print("Value already exists.")
return curNode
def delete(self, x:int)->None:
self.root = self.__deleteHelp(self.root, x)
def __deleteHelp(self, curNode: TreeNode, x:int)->TreeNode:
if not curNode:
return curNode
elif x > curNode.val :
return self.__deleteHelp(curNode.right, x)
elif x < curNode.val:
return self.__deleteHelp(curNode.left, x)
elif not curNode.left:
return curNode.right
rightMostNode = curNode.left
while rightMostNode.right != None:
rightMostNode = rightMostNode.right
leftMostNode = rightMostNode
while leftMostNode.left != None:
leftMostNode = leftMostNode.left
if rightMostNode == leftMostNode:
rightMostNode.right = curNode.right
return rightMostNode
else:
leftMostNode.left = curNode.left
rightMostNode.right = curNode.right
return rightMostNode
④ 탐색 알고리즘
○ 종류 1. depth-first traversal : 재귀함수 또는 LIFO stack으로 구현
○ 1-1. 전위 순회(preorder traversal) : directory listing 등에 활용
class Tree():
def visit(self, node: TreeNode)->None:
print(node.val)
def DFT_preorder(self):
self.__DFT__preorderHelp(self.root)
def __DFT__preorderHelp(self, curNode: TreeNode)->None:
if curNode == None:
return
self.visit(curNode)
self.__DFT__preorderHelp(curNode.left)
self.__DFT__preorderHelp(curNode.right)
○ 1-2. 중위 순회(inorder traversal) : binary search tree를 sorted array로 만들고 싶을 때 (flatening)
class Tree():
def visit(self, node: TreeNode)->None:
print(node.val)
def DFT_inorder(self):
self.__DFT__inorderHelp(self.root)
def __DFT__inorderHelp(self, curNode: TreeNode)->None:
if curNode == None:
return
self.__DFT__inorderHelp(curNode.left)
self.visit(curNode)
self.__DFT__inorderHelp(curNode.right)
○ 1-3. 후위 순회(postorder traversal) : 폴더 용량 계산 등에 활용
class Tree():
def visit(self, node: TreeNode)->None:
print(node.val)
def DFT_postorder(self):
self.__DFT__postorderHelp(self.root)
def __DFT__postorderHelp(self, curNode: TreeNode)->None:
if curNode == None:
return
self.__DFT__postorderHelp(curNode.left)
self.__DFT__postorderHelp(curNode.right)
self.visit(curNode)
○ 폴더 용량 계산과 후위 순회
class Tree():
def visit(self, node: TreeNode, x:float)->float:
return node.val
def __DFT_postorderHelp(curNode: TreeNode)->float:
ans = 0
if curNode:
for i in range(len(curNode.child)):
ans += self.__DFT_postorderHelp(curNode.child[i])
ans += self.visit(curNode)
return ans
def DFT_postorder(self)->float:
return self.__DFT_postorderHelp(self.root)
○ k-ary tree의 전위 순회
class Tree():
def visit(self, node: TreeNode)->None:
print(node.val)
def DFT_inorder(self):
self.__DFT__preorderHelp(self.root)
def __DFT__inorderHelp(self, curNode: TreeNode)->None:
if curNode == None:
return
if len(curNode.child) != 0:
for i in range(len(curNode.child)):
if i == 1:
self.visit(curNode)
self.__DFT__inorderHelp(curNode.child[i]
else:
self.visit(curNode)
○ 종류 2. level-order (breadth-first) traversal
○ 개요
○ FIFO queue (파이썬 기준 deque)로 구현
○ root부터 시작하여 level이 작은 것부터 방문
○ 같은 level에 대해 왼쪽부터 방문
○ 알고리즘 (Python)
class Tree():
def visit(self, node: TreeNode)->None:
print(node.val)
def BFT(self):
if self.root == None:
return
q = [self.root]
while q:
curNode = q.pop(0)
self.visit(curNode)
for childNode in curNode.child:
if childNode:
q.append(childNode)
7. 그래프(graph) [목차]
⑴ 개요
① 정의 : node와 edge로만 구성된 자료구조. 동떨어져 있는 노드가 있어도 그래프가 됨을 유의
② node : vertex
③ edge : vertex의 쌍. vertex v, w에 대해 (v, w)와 같이 나타냄
④ 인접(adjacent) : 그래프가 (v, w)라는 edeg가 있으며 v와 w는 인접함
○ 이때 두 노드를 neighbor라고 함
⑤ 루프(loop) : 특정 노드에서 시작하여 자기 자신으로 곧장 향하는 edge
○ 즉, (v, v)
⑥ parallel edge : 두 노드를 잇는 서로 다른 edge
○ 즉, e1 = (v,w), e2 = (v, w), e1 ≠ e2
⑦ 경로(path) : edge로 연결된 node들의 sequence
○ (v, w), (w, y), (y, z)라는 edge가 있으면 (v, w, y, z)라는 경로가 있다는 의미
⑧ 사이클(cycle) : 처음과 마지막 vertex가 같은 경로
⑨ 단순 경로(simple path) : 하부 사이클이 없는 경로
○ 즉, 경로상에 중복되는 노드가 없는 경로
⑩ 그래프 내 사이클이 있으며 cyclic graph, 사이클이 없으면 acyclic graph라고 함
⑪ 연결(conncected) : 두 노드 사이에 경로가 있으면 두 노드는 연결돼 있음
⑫ (v, w)가 undirected라면 v와 w는 서로 도달할 수 있지만, directed라면 v에서 w로만 갈 수 있음
⑬ undirected edge로 구성된 그래프는 undirected graph이고 directed edge로 구성된 그래프는 directed graph
⑵ 종류 1. 단순 그래프(simple graph)
① 정의 : self-loop와 parallel edge를 포함하지 않는 그래프
② 생성 알고리즘 (Python)
class Node():
def __init__(self, i, j):
self.i = i
self.j = j
class undirected_graph():
def __init__(self, V:list, E:list)->None:
self.V = V[:]
self.neighbor = {}
for v in V:
self.neighbor[v] = []
for (v,w) in E:
self.neighbor[v].append(w)
two_d_list = []
line = []
line.append(1)
line.append(2)
line.append(3)
line.append(4)
line.append(5)
two_d_list.append(line)
line = []
line.append(6)
line.append(7)
line.append(8)
line.append(9)
line.append(10)
two_d_list.append(line)
line = []
line.append(11)
line.append(12)
line.append(13)
line.append(14)
line.append(15)
two_d_list.append(line)
line = []
line.append(16)
line.append(17)
line.append(18)
line.append(19)
line.append(20)
two_d_list.append(line)
V = []
E = []
for i in range(len(two_d_list)):
for j in range(len(two_d_list[0])):
if True:
V.append(Node(i, j))
for v in V:
for w in V:
if True:
E.append((v,w))
g = undirected_graph(V, E)
③ 탐색 알고리즘 (Python)
○ 종류 1. depth-first traversal
○ 응용 1. 두 node가 연결됐는지 여부 확인
○ 응용 2. 그래프 내 disjoint island의 개수 확인 (counting island 알고리즘)
○ 응용 3. 그래프 내 cycle이 있는지 여부 확인
○ 1-1. 전위 순회(preorder traversal)
class undirected_graph():
def __init__(self, V:list, E:list)->None:
self.V = V[:]
self.neighbor = {}
for v in V:
self.neighbor[v] = []
for (v,w) in E:
self.neighbor[v].append(w)
self.neighbor[w].append(v)
def DFT_preorder(self)->None:
if self.V:
visited = {}
for v in self.V:
visited[v]=False
for v in self.V:
if not visited[v]: # gatekeeper
self.__DFT__preorderHelp(visited, v)
def __DFT__preorderHelp(self, visited: list, v: int)->None:
if not visited[v]:
visited[v] = True
print(v)
for w in self.neighbor[v]:
self.__DFT__preorderHelp(visited, w)
○ 1-2. 후위 순회(postorder traversal)
class undirected_graph():
def __init__(self, V:list, E:list)->None:
self.V = V[:]
self.neighbor = {}
for v in V:
self.neighbor[v] = []
for (v,w) in E:
self.neighbor[v].append(w)
self.neighbor[w].append(v)
def DFT_postorder(self)->None:
if self.V:
visited = {}
for v in self.V:
visited[v]=False
for v in self.V:
if not visited[v]: # gatekeeper
self.__DFT__postorderHelp(visited, v)
def __DFT__postorderHelp(self, visited: list, v: int)->None:
if not visited[v]:
visited[v] = True
for w in self.neighbor[v]:
self.__DFT__postorderHelp(visited, w)
print(v)
○ 종류 2. breadth-first traversal
class undirected_graph():
def __init__(self, V:list, E:list)->None:
self.V = V[:]
self.neighbor = {}
for v in V:
self.neighbor[v] = []
for (v,w) in E:
self.neighbor[v].append(w)
self.neighbor[w].append(v)
def BFT(self)->None:
if self.V:
visited={}
# initialize
for v in self.V:
visited[v]=False
q = deque([])
for v in self.V:
q.append(v)
while q:
v = q.popleft()
if not visited[v]:
visited[v] = True
for w in self.neighbor[v]:
q.append[w]
8. 해시(hash) [목차]
⑴ 개요 : data → hash function → hash value → reduction (e.g., modulo) → valid inidex
⑵ (참고) data indexed array
① 개요
○ 특정 원소를 삽입해도 메모리 사용량이 변하지 않음
○ 원소의 종류가 상당히 많으면 초기 배열 정의 시 너무 많은 메모리를 필요로 함
② 알고리즘 (Python)
class LinkedNode():
def __init__(self,x):
self.val = x
self.next = None
class SLList():
def __init__(self)->None:
self.sentinel = LinkedNode(0)
self.size = 0
def addFirst(self, x:int)->None:
newFirst = LinkedNode(x)
newFirst.next = self.sentinel.next
self.sentinel.next = newFirst
self.size += 1
class data_indexed_array():
max_element = 10
def __init__(self)->None:
self.array = [None] * max_element
def hash_valu(self, x:int)->int:
return x^3 % max_element
def add(self)->None:
i = hash_value(x)
if self.array[i] == None:
self.array[i] = SLList()
self.array[i].addFirst(x)
⑶ 해시함수(hash function)
① 정의 : 임의의 사이즈를 가지는 데이터를 고정된 사이즈를 가지는 값으로 맵핑하는 모든 함수
② 주어진 데이터를 최대한 랜덤하게 해시 자료구조에 골고루 분포하게 해야 함
⑷ 개선 1. collision handling
① 각 칸에 값만 저장하지 말고 linked list로 표현하면 해결됨
⑸ 개선 2. hash table performance
① 해시 자료구조의 크기와 원소의 개수 간의 관계를 어떻게 할지가 자료구조의 효율에 중요하게 작용
② resizing : 탐색 알고리즘이 O(1)이 되도록 함. resizing을 할 때는 O(N)이 걸림
③ 보통 다음과 같이 resizing하여 resizing time을 줄임 : 1 + 2 + 4 + 8 + ··· + N = 2N - 1
④ 따라서 원소를 하나씩 증가시킬 때마다 걸리는 time complexity는 O((2N-1) / N) = O(1)
⑤ 시간복잡도
add |
in-operation (e.g., search) |
|
SLList | O(1) | O(N) |
list | O(1) | O(N) |
data-indexed array | O(1) | O(1) |
data-indexed array with chains (fixed size) |
O(1) | O(K) |
data-indexed array with chains (resizing) |
O(1) | O(1) |
Table. 2. 주요 자료구조와 data-indexed array의 시간복잡도
○ 보충 : data-indexed array with chains (fixed size)
○ M개의 index를 가지지는 hash table에 대하여 N개의 item을 넣을 때
○ K는 N/M (best case) ~ N (worst case)의 값을 가짐
9. 셋(set) [목차]
⑴ 특징 : element immutability, no repeatablility (dictionary와 같음)
⑵ 위와 같은 특징으로 인해 해시 자료구조를 쓸 수 있어 list, tuple보다 search가 훨씬 빠름
입력: 2021.09.22 11:45
'▶ 자연과학 > ▷ 알고리즘·머신러닝' 카테고리의 다른 글
【알고리즘】 4강. 데이터 시각화 (0) | 2021.10.28 |
---|---|
【알고리즘】 1-1강. 정렬 알고리즘 실험 (0) | 2021.10.01 |
【알고리즘】 2강. 탐색 알고리즘 (0) | 2021.09.22 |
【알고리즘】 1강. 정렬 알고리즘 (2) | 2021.09.14 |
【알고리즘】 2-1강. 탐색 알고리즘 실험 (0) | 2020.07.05 |
최근댓글