자료구조

Hi YoungJin·2021년 9월 19일
data structurehash그래프리스트배열스택자료구조큐트리
0

Computer Science

목록 보기
1/1

자료구조란?

사람들이 사물을 정리하는 것과 마찬가지로 프로그램에서 자료들을 정리하는 여러가지 구조를 말한다.
-천인국ㆍ공용해ㆍ하상호,『C언어로 쉽게 풀어쓴 자료구조』,생능출판(2017)

일상 생활에서의 예해당하는 자료 구조
물건을 쌓아놓는 것stack
영화관 매표소의 줄queue
할 일 리스트list
영어사전dictionary, search
지도graph
조직도tree



1. Array 배열

배열은 거의 모든 프로그래밍 언어에서 기본적으로 제공되는 데이터 타입으로서, 많은 고급 자료 구조들이 배열을 사용하여 구현된다.

가장 기본적인 자료구조인 Array는 인덱스(index)가 주어지면 해당하는 요소(element)가 대응되며 논리적 저장 순서와 물리적 저장 순서가 일치한다. 즉, 배열에서는 인덱스를 사용하여 요소에 직접 접근이 가능하다.

  • 객체 : <인덱스, 요소> 쌍들의 집합
  • 연산 :
    • create(n) ::= n개의 요소를 가진 배열의 생성
    • retrieve(A, i) ::= 배열 A의 i번째 요소 반환
    • store(A, i, item) ::= 배열 A의 i번째 위치에 item 저장
연산시간 복잡도
random accessO(1)
삽입O(n)
삭제O(n)

삽입과 삭제와 경우 배열의 원소에 접근 후( O(1) ), 원소들의 인덱스를 앞 또는 뒤로 shift해줘야 하므로 O(n)의 시간을 요구한다.



2. Linked List 연결 리스트

물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법.
데이터와 링크로 구성되어 링크가 데이터들을 연결하는 역할을 한다. 동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터가 이동할 필요가 없다.

위의 Array의 문제점을 해결하기 위한 자료구조인 linked list는 각각의 원소들이 데이터 필드와 링크 필드로 구성되어(이를 '연결된 표현'이라 한다) 자기 자신 다음에 어떤 원소가 오는지를 기억한다.
이 부분만 다른 값으로 바꿔주면 삭제과 삽입 연산을 O(1)으로 해결할 수 있다.

But,

Array와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문에 원하는 위치를 찾는 Search 과정에서 첫번째 원소부터 모두 확인해야 한다는 단점이 있다.
결국 linked list는 기본적인 탐색 연산과, 삽입, 삭제 연산에 모두 O(n)의 시간 복잡도를 갖는다.

연산시간 복잡도
SearchO(n)
삽입O(n)
삭제O(n)



3. Stack 스택

후입 선출(LIF0 : Last-In First-Out)의 형식으로 가장 최근에 입력된 데이터가 가장 먼저 나온다.

스택의 입출력은 맨 위에서만 이루어지며 이 부분을 스택 상단(stack top)이라 한다.
그리고 반대쪽인 바닥 부분은 스택 하단(stack bottom)이라 한다.
스택에 저장되는 것은 요소(element), 요소가 하나도 없는 스택은 공백 스택(empty stack)이라고 부른다.

  • 객체 : n개의 element 타입의 요소들의 순서있는 모임
  • 연산 :
    • create() ::= 스택을 생성한다.
    • is_empty(s) ::= 스택이 비어 있는지를 검사한다.
    • is_full(s) ::= 스택이 가득 찼는가를 검사한다.
    • push(s,e) ::= 스택의 맨 위에 요소 e를 추가한다.
    • pop(s) ::= 스택의 맨 위에 있는 요소를 삭제한다.
    • peek(s) ::= 스택의 맨 위에 있는 요소를 삭제하지 않고 반환한다.



4. Queue 큐

선입 선출(FIFO : First-In Fist-out)의 형식으로 먼저 삽입된 데이터가 먼저 나온다.
스택과는 달리, 큐는 삽입과 삭제가 서로 다른 쪽에서 일어난다.

삽입이 일어나는 곳은 후단(rear)이라 하고, 삭제가 일어나는 곳은 전단(front)라고 한다.

  • 객체 : n개의 element 타입의 요소들의 순서있는 모임
  • 연산 :
    • create() ::= 큐를 생성한다.
    • init(q) ::= 큐를 초기화한다.
    • is_empty(q) ::= 큐가 비어 있는지를 검사한다.
    • is_full(q) ::= 큐가 가득 찼는가를 검사한다.
    • enqueue(q,e) ::= 큐의 뒤에 요소 e를 추가한다.
    • dequeue(q) ::= 큐의 앞에 있는 요소를 반환한 다음 삭제한다.
    • peek(q) ::= 큐에서 삭제하지 않고 앞에 있는 요소를 반환한다.



5. Tree 트리

계층적인 구조(hierarchical structure)를 가지고 있는 자료를 표현하는데 이용되는 자료구조.

트리의 구성요소

  • node (노드) : 트리를 구성하는 각각의 요소
  • root node (루트 노드) : 트리 구조에서 최상위에 있는 단 하나의 노드
  • subtree (서브 트리) : 루트 노드를 제외한 나머지 노드들
  • edge (간선) : 노드와 노드를 연결하는 선
  • parent node (부모 노드) : 어떤 노드의 위쪽으로 단 하나의 간선으로 연결된 노드
  • ancestor node (조상 노드) : 루트 노드부터 어떠한 노드까지의 경로를 이루고 있는 노드 (루트 ~ 부모 노드)
  • sibling (형제 관계) : 같은 부모 노드를 둔 노드들 간의 관계
  • children node (자식 노드) : 어떤 노드의 아래쪽으로 단 하나의 간선으로 연결된 노드 (여러 개의 자식 노드를 가질 수 있다.)
  • descendent node (자손 노드) : 어떤 노드의 하위에 연결된 모든 노드 (어떤 노드의 subtree에 속하는 모든 노드)
  • terminal node (= leaf node, 단말 노드) : 자식 노드가 없는 노드
  • nonterminal node (= internal node, 비단말 노드, 내부 노드) : 단말 노드를 제외한 모든 노드 (루트 노드 포함)
  • degree (차수) : 어떤 노드가 가지고 있는 자식 노드의 개수
  • 트리의 차수 : 트리가 가지고 있는 노드의 차수 중 가장 큰 차수
  • level (레벨) : 트리의 각 층에 매겨진 번호 (루트의 레벨은 1, 이후로 1씩 증가)
  • height (트리의 레벨) : 트리가 가지고 있는 최대 레벨

  • 이진 트리 (binary tree)

    • 포화 이진 트리 (perfect binary tree)
      : 모든 레벨에 노드가 꽉 차 있는 이진 트리
    • 완전 이진 트리 (complete binary tree)
      : 높이가 k일 때 레벨 1부터 레벨 k-1까지는 포화 이진 트리의 형태이고, 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리. 마지막 레벨에서는 노드가 꽉 차 있지는 않아도되지만 중간에 빈 곳이 있어서는 안 된다.
    • 기타 이진 트리
      : 정 이진 트리(full binary tree)는 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리이다.

    ※ 포화 이진 트리는 늘 완전 이진 트리이다.
    ※ 완전 이진 트리는 항상 포화 이진 트리라고 할 수 없다.

배열 기준 이진 트리의 인덱스 (루트 노드 인덱스는 1)

현재 노드의 인덱스ii
부모의 인덱스i/2i / 2
왼쪽 자식의 인덱스i∗2i * 2
오른쪽 자식의 인덱스(i∗2)+1(i * 2) + 1

n 개의 노드를 가진 이진 트리의 성질

값
간선n−1n-1
최대 높이n
최소 높이ceil(log⁡2(n+1))ceil(\log_{2}{(n+1)})

높이가 h인 이진 트리의 성질

값
최대 노드 개수2h−12^h -1
최소 노드 개수hh
  • 높이가 k인 포화 이진 트리의 전체 노드 개수는 2k−12^k-1로 최대 노드 개수와 같다.

BST (Binary Search Tree)

탐색(search)은 가장 중요한 컴퓨터 응용의 하나로, 시간이 많이 걸리면서 자주 사용되는 작업이기에 효율적인 수행이 매우 중요하다.

이진 탐색 트리는 이진 트리 기반의 탐색을 위한 자료 구조

이진 탐색 트리의 정의
1. 모든 노드의 키(key)는 유일하다.
2. 왼쪽 서브 트리의 키들은 루트의 키보다 작다.
3. 오른쪽 서브 트리의 키들은 루트의 키보다 작다.
4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

  • 이진 탐색 트리의 분석
    이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라 했을 때 O(h)가 된다. 균형 잡힌 이진 트리의 높이는 ceil(/log2n)ceil(/log_{2}{n})이므로 이진 탐색 트리 연산의 평균적인 시간 복잡도는 O(log n)이다.

    그러나 편향 트리(skewed tree)의 경우에는 트리의 높이가 n과 같게 되어 탐색, 삽입, 삭제 시간이 거의 선형 탐색과 같이 O(n)이 된다.

    balanced tree 균형 트리

  • 2-3-4 트리

  • 레드-블랙 트리

  • AVL 트리



6. Binary Heap 힙

배열에 기반한 Complete Binary Tree(완전 이진 트리)의 일종으로 우선순위 큐를 위해 만들어진 자료 구조

이진 탐색 트리와는 달리 중복된 값을 허용하며 힙 안의 데이터들은 느슨한 정렬 상태를 유지한다.
힙(heap)에는 최대 힙(max heap)과 최소 힙(min heap) 두 종류가 있다.

  • max heap : 부모 노드의 값이 자식 노드의 키 값보다 크거나 같다.

  • min heap : 부모 노드의 값이 자식 노드의 키 값보다 작거나 같다.

    ※ 서로 반대

    max heap에서는 root node에 있는 값이 제일 크므로, 최대 값을 찾는데 소요되는 연산의 시간 복잡도는 O(1)이다.

    max heap 최대값 탐색 시간 복잡도 O(log n)

    ① 루트 노드(= 최대값) 제거
    ② 맨 마지막 노드를 루트 노드로 대체
    ③ heapify 과정을 거쳐 heap 구조 유지

    min heap 최소값 탐색 역시 동일하다.



7. Red-Black Tree 레드-블랙 트리

2-3-4 트리의 단점을 극복한 이진 탐색 트리

Red-Black Tree의 성질
1. 각 노드는 red or black이라는 색깔을 갖는다.
2. root node와 leaf node의 색깔은 모두 black이다. (연결된 노드는 색이 중복되지 않는다.)
3. red 노드의 자식노드의 색은 모두 black이다.
4. 각 노드로부터 해당 노드를 포함하지 않은 단말 노드까지의 단순 경로에 있는 블랙 노드의 수는 모두 같다. 이를 Black-Height(= rank)이라 한다. (단말 노드의 rank는 0이다.)

Red-Black Tree의 특징

  1. 이진 탐색 트리의 특징을 모두 갖는다.

  2. root node부터 leaf node까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율을 2보다 크지 않다. 이러한 상태를 balanced상태라고 한다.

  3. 자식 노드가 없을 경우 child를 가리키는 포인터는 NIL값을 저장하고 이러한 NIL들을 leaf node로 간주한다.

    삽입과 삭제는 BST의 특성을 유지하면서 이루어진다.
    삽입되는 노드의 색은 red이고 RBT(레드-블랙 트리)의 특성에 위배된다면 rotation을 통해 height를 조정한다.
    삭제될 노드의 child개수에 따라 rotation 조정한다. 지워진 노드이 색이 black 이라면 black-height가 감소한 경로에 black node가 1개 추가되도록 노드의 색을 조정, 지워진 노드이 색이 red라면 violation이 발생하지 않으므로 RBT를 그대로 유지한다.



8. AVL Tree AVL 트리

한 쪽으로 값이 치우치는 이진 균형 트리(Balanced Search Tree)의 한계점을 보완하는 높이 균형 이진 탐색 트리(height-balanced binary search tree)
각 노드의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차가 1 이하인 이진 탐색 트리
-채진석,『알고리즘과 파이썬』,정익사(2019)

균형 인수 = 오른쪽 서브트리의 높이 - 왼쪽 서브트리의 높이
균형 인수 ∈ { -1, 0, +1 }

균형 인수가 +2 또는 -2가 되었을 때 회전을 수행하며, 균형 인수가 +2 또는 -2가 되는 조상 노드 중에서 삽입노드로부터 가장 가까운 노드가 회전 수행 기준 노드가 된다.

class node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class Dict:
    def __init__(self):
        self.node = None
        self.height = 0
        self.balance = 0

    def search(self, search_key):
        x = self.node
        while x is not None:
            if x.key == search_key:
                return x.key
            if x.key > search_key:
                x = x.left.node
            else:
                x = x.right.node
        return -1

    def insert(self, v):
        x = self.node
        if x is None:
            self.node = node(v)
            self.node.left = Dict()
            self.node.right = Dict()

        elif x.key > v : 
            self.node.left.insert(v)

        else:
            self.node.right.insert(v)
        
        self.check_balance()

    def check_balance(self):
        self.update_heights(False)
        self.update_balances(False)

        while self.balance <-1 or self.balance >1 :
            if self.balance > 1:
                if self.node.left.balance < 0:
                    self.node.left.rotate_left()
                self.rotate_right()
            else:
                if self.node.right.balance > 0:
                    self.node.right.rotate_right()
                self.rotate_left()

            self.update_heights()
            self.update_balances()

    def rotate_right(self):
        g = self.node
        p = g.left.node
        x  =p.right.node

        self.node = p
        p.right.node = g
        g.left.node = x
    
    def rotate_left(self):
        g = self.node
        p = g.right.node
        x  =p.left.node

        self.node = p
        p.left.node = g
        g.right.node = x
    
    def update_heights(self, recurse = True):
        if self.node is not None:
            if recurse:
                if self.node.left is not None:
                    self.node.left.update_heights()
                if self.node.right is not None:
                    self.node.right.update_heights()
            self.height = max(self.node.left.height, self.node.right.height) +1
        else:
            self.height = 0

    def update_balances(self, recurse = True):
        if self.node is not None:
            if recurse:
                if self.node.left is not None:
                    self.node.left.update_balances()
                if self.node.right is not None:
                    self.node.right.update_balances()
            self.balance = self.node.left.height - self.node.right.height
        else:
            self.balance = 0

AVL은 항상 좌/우로 데이터를 균형잡힌 상태로 유지한다.



9. Hash Table 해시 테이블

hash table이란 키 값의 연산에 의해 직접 접근이 가능한 구조를 말한다.

키 값에 직접 산술적인 연산(Hash Function)을 적용하여 항목이 저장되어 있는 테이브의 주소를 계산하고 항목에 접근하기 때문에 average case에 대해 O(1)의 시간 복잡도를 갖는다.

Hash Function

좋은 해시 함수의 조건

  • 충돌(collision)이 적어야 한다.
  • 해시 함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포되어야 한다.
  • 계산이 빨라야 한다.

고유한 인덱스 값을 설정하는 해시 함수(hash function)는 저장되는 값들의 key값을 작은 범위의 값으로 바꿔준다.

하지만 동일한 key값을 가지는 복수의 데이터가 하나의 테이블에 존재하게 된다면 Collision이 발생하기 때문에 충돌 해결은 필수이다.

간단하게 생각해볼 수 있는 충돌 해결의 2가지 방식

  • 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장한다. (선형 조사법(linear probing))
  • 해시 테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시 테이블의 구조를 변경한다. (체이닝(chaining))

충돌 해결 참조

linear probing과 같은 방식은 Open Address방식으로 공개 주소 방식이라고도 불린다.
일반적으로 Open Addressing보다 빠른 Seperate Chaining은 보조 해시 함수를 통해 해시 충돌이 잘 발생하지 않도록 조정하는 방식이다. 분리 연결법이라고도 불린다.

Open Address vs Seperate Chaining

두 방식 모두 Worst Case에서 O(M)이다. 하지만 Open Address방식은 연속된 공간에 데이터를 저장하므로 Seperate Chaining에 비해 캐시 효율이 높다. 그러나 Open Address방식은 버킷을 계속해서 사용하기 때문에, 테이블의 확장을 보다 늦추려면 Seperate Chaining 방식이 효율적이다.

효율이 더 높은 방식
데이터의 수가 충분히 적은 경우Open Address
일반적인 경우Seperate Chaining



10. Graph 그래프

cf) 트리는 사이클이 허용되지 않는 그래프이다.

연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조
그래프는 간선의 종류에 따라 무방향 그래프와 방향 그래프로 구분된다.

그래프 용어

  • vertex (= node, 노드, 정점)
  • edge (= link, 링크, 간선)
  • 무방향 그래프 (undirected graph) : 간선을 통해 양방향으로 갈 수 있는 그래프. (A,B)와 (B,A)는 동일한 간선
  • 방향 그래프 (directed graph) : 간선에 방향성이 존재하므로 간선을 통해 한쪽 방향로만 갈 수 있는 그래프. <A,B>와 <B,A>는 다른 간선.
  • adjacent vertex (인접 정점) : 간선에 의해 직접 연결된 정점
  • degree(차수) : undirected graph에서 하나의 vertex에 연결된 edge의 개수
  • in-degree (진입 차수) : directed graph에서 외부에서 오는 간선의 수
  • out-degree (진출 차수) : directed graph에서 외부로 향하는 간선의 수
  • path length (경로 길이) : 경로를 구성하는데 사용된 간선의 수
  • simple path (단순 경로) : 경로 중에서 반복되는 간선이 없을 경우의 경로
  • cycle (사이클) : 단순 경로 중에서 시작 vertex와 종료 vertex가 일치하는 경로

가중치 그래프(weighted graph) 또는 네트워크(network)

가중치 그래프란 간선에 가중치 정보를 두어서 구성한 그래프이다. 간선의 역할이 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있으므로 훨씬 복잡한 관계를 표현할 수 있게 된다.

부분 그래프(sub graph)

부분 집합과 유사한 개념으로, 그래프 G를 구성하는 정점의 집합 V(G)와 간선의 집합 E(G)의 부분 집합으로 이루어진 그래프이다.


그래프를 구현하는 방법시간 복잡도공간 복잡도
인접 행렬간선 존재 여부 확인 : O(1), 간선의 수 확인 : O(E²)O(V²)
인접 리스트간선 존재 여부 확인 : O(E), 간선의 수 확인 : O(E+V)O(E+V)

※ 인접 리스트 표현은 간선의 개수가 적은 희소 그래프의 표현에 적합하다.

reference

profile
Hi YoungJin
For me, By me.

0개의 댓글