【알고리즘】 3강. 자료구조

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의 개수 확인

○ 응용 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