자료 구조 Data structure 요약 노트

데이터 구조란?

• 데이터를 조직하는 방법
• 자료 구조에 의해 데이터를 다루는 성능과 메모리 효율성이 달라진다.
• 분류
  • Linear Structure 선형 구조 : List(Array), Stack, Queue
  • Non-linear Structure 비선형 구조 : Graph, Tree
• 구현 방법
  • Contiguous Data Structure 순차 자료구조
    • 메모리에 연속 저장
    • 임의 원소 바로 접근
    • Cache Locality 캐시 지역성으로 인해 빠른 순회
    • 데이터 크기만큼의 메모리 크기
  • Linked Data Structure 연결 자료구조
    • 데이터를 노드에 저장, 불연속적인 메모리 공간 사용
    • 선형시간의 임의 원소 접근
    • 흩어진 메모리 공간으로 느린 순회
    • 이어진 노드 정보 저장을 위해 여분의 메모리 사용
• Abstract Data Type 추상 자료형 (ADT)
  • 구체적인 구현이 아닌 작업 기능만 정의한 것
• Collection 컬렉션 (C#)
  • 연관된 data 묶음을 관리하기 위해 제공된 자료 구조
  • Iterator 반복자
    • Collection 내 Data 들을 반복하여 훑기 위해 사용
    • 순차적 요소 접근 가능
    • IEnumerable Interface 구현으로 foreach 반복문과 같은 구문으로 접근 가능
• Array 배열
  • 같은 type의 데이터를 고정 크기의 연속적으로 저장하는 구조
  • index가 0으로 시작하는 이유
    • index 위치의 메모리에 data type의 size만큼 더해서 접근하기 때문
• Dynamic Array 동적 배열 { Vector(C++) / List(C# Generic) / ArrayList(C# Collection) }
  • ADT
    • 읽기 - index 혹은 iterator를 통해 특정 원소 접근
    • 검색 - 특정 원소, 특정 범위 원소를 찾기
    • 삽입 - 모든 위치에 원소 삽입 가능
    • 삭제 - 특정 원소 삭제
  • Linear List 선형 리스트
    • Ordered List 순서 리스트
    • 순차적 구현으로 임의 접근 가능
    • Generic인 List는 해당 type의 list를 만들어 data를 복사하기 때문에 Boxing에서 자유로워 성능에 이점이 있다.
    • 성능
      • 읽기 - O(1)
      • 검색 - O(N)
      • 삽입 - O(N)
      • 삭제 - O(N)
• Liked List 연결 리스트
  • 불연속적인 메모리 배치로 임의 접근 불가
  • 데이터 공간 + 다음 연결을 담을 메모리 공간이 필요
  • 종류
    • Singly Linked List 단일 연결 리스트
    • Doubly Linked List 이중 연결 리스트
    • Circular Linked List 원형 연결 리스트 (※ 구현 해보기)
  • 성능
    • 읽기 - O(N)
    • 검색 - O(N)
    • 삽입 - 위치를 알 경우 O(1), 모를 경우 O(N)
    • 삭제 - 위치를 알 경우 O(1), 모를 경우 O(N)
• Stack 스택
  • LIFO (Last-In First-Out) 구조
  • ADT
    • Peek 읽기 - Top에 위치한 데이터에 접근
    • Push 삽입 - Stack 위에 데이터를 삽입
    • Pop 삭제 - Stack의 Top 데이터를 삭제
  • 괄호쌍 검사, Postfix notation 후위 표기식, DFS 등에 사용

Stack

• Queue 큐
  • FIFO (First-In First-Out) 구조
  • ADT
    • Peek 읽기 - Queue의 Front 위치 데이터에 접근
    • Enqueue 삽입 - Queue의 Rear에 데이터를 삽입
    • Dequeue 삭제 - Queue의 Front의 데이터를 삭제
  • Deque 덱 (Double-ended Queue)
    • Front, Rear 모두 삽입 삭제가 가능
    • CPU 스케쥴링, 데이터 버퍼, BFS 등에 사용

Queue

• Graph 그래프
  • 계층, 관계와 같이 선형 자료구조로는 표현 할 수 없는 데이터를 Vertex 정점과 Edge 간선으로 구성하여 표현한 자료구조
  • Vertex 정점 - 고유하게 식별 되는 객체
  • Edge 간선 - 정점 간의 관계
  • 종류
    • 방향성 여부
      • Directed Graph 방향 그래프
      • Undirected Graph 무방향 그래프
    • 간선의 정보 여부
      • Weighted Graph 가중치 그래프
  • 용어
    • Adjacent 인접 - 연결 된 정점 간의 관계
    • Incident 부속 - 연결 된 간선과 연결 정점 간 관계
    • Degree 차수 - 정점에 부속 되어 있는 간선 수
      • In-degree 진입 차수
      • Out-degree 진출 차수
    • Path 경로 - 한 정점에서 다른 정점까지의 인접 정점을 순서대로 나열한 리스트
      • Path Length 경로 길이 - 경로 간선 수
      • Simple Path 단순 경로 - 모두 다른 정점으로 구성된 경로
      • Cycle 사이클 - 단순 경로 중 시작 정점과 마지막 정점이 같은 경로
  • 구현
    • 인접 행렬 - 2차원 배열
      • 간선이 적다면 메모리 낭비가 생기게 됨
    • 인접 리스트
      • 연결 된 간선 만을 저장
• Tree 트리
  • 계층적인 구조를 나타내기 위한 자료구조 (Hierachical Data Structure)로 그래프의 한 종류이다.
  • 순환 구조를 가지지 않는다.
  • 노드가 N개라면 간선은 항상 N-1개이다.
  • 두 노드 사이의 경로는 오직 하나이다.
  • 용어
    • 노드와 간선은 그래프에서의 것과 동일
    • 루트 노드 (Root) : 꼭대기에 부모가 없는 노드
    • 리프 노드 (Leaf) : 자식이 하나도 없는 최하단 마지막 노드
    • 차수 (Degree) : 노드가 가지는 자식의 수
    • 깊이 (Depth) : 루트→특정노드까지 거치는 간선 수
    • 높이 (Height) : 루트→가장 먼 리프노드까지의 간선 수
  • 순회
    • 트리의 모든 노드를 방문하는 방법
    • 전위 순회 (Pre-order) - 루트 → 왼쪽 → 오른쪽
    • 중위 순회 (In-order) - 왼쪽 → 루트 → 오른쪽
    • 후위 순회 (Post-order) - 왼쪽 → 오른쪽 → 루트
  • 이진 트리 (Binary Tree)
    • 포화 이진 트리 (Full-BT) : 모든 리프 노드가 같은 레벨, 모든 노드가 자식을 2개씩가진 이진 트리
    • 완전 이진 트리 (Complete-BT) : 위에서 아래로 전위 순회 순서대로 채워진 이진 트리
  • 이진 탐색 트리 (Binary Search Tree)
    • 한 노드 기준 값보다 작은 값을 왼쪽 서브 트리에, 높은 값을 오른쪽 서브 트리에 위치한 노드의 자식 수가 2인 트리
    • 중위 순회 (In-order) 시 오름차순 정렬
    • 효율은 트리의 높이에 의해 결정
    • 편향이 된다면 기존의 O(logN)이 아닌 최악의 경우 O(N)의 성능.
    • 균형을 맞추기 위한 자가 균형 이진 탐색 트리(Self-Balancing BST)
      • AVL Tree (Adjacency List Tree)
        • 왼,오 서브트리의 높이 차가 1 초과 시 회전
      • RB Tree (Red-Black Tree)
        • 규칙을 통해 재 색칠 및 회전
• Heap 힙
  • 최대값,최소값,우선순위가 높은 값을 빠르게 찾을 수 있는 자료구조
  • 특징
    • 완전 이진 트리 (Complete BT) 구조
    • 루트 노드에 가장 우선순위가 높은 값
    • 반정렬 상태(느슨한 정렬) : 부모 자식간의 우선순위만 성립 (형제 간은 X)
    • 중복 값 허용. (BST는 X)
  • 성능
    • 추출 - 루트노드에 우선순위가 가장 높은 값이 있고 O(1) 상수시간으로 값을 추출
    • 삽입 - 노드를 최하단에 삽입하여 부모와 비교하여 올리는 Heapify-Up, O(logN)
    • 삭제 - 추출 후 마지막 노드를 루트로 올려 자식과 비교하여 내리는 Heapify-Down, O(logN)
  • 힙 정렬(O(NlogN)), 우선순위 큐, 다익스트라 알고리즘에 사용.
• Hash Table 해시 테이블
  • 키를 해시 함수의 결과 값에 매핑한 인덱스에 데이터를 저장하는 자료구조
  • 데이터의 매우 빠른 탐색 속도를 보장
  • 순서대로 저장되지 않아 정렬이 필요한 경우 부적합
  • 요소
    • 키 (Key) : 해싱 이전의 원본 데이터
    • 해시 함수 (Hash Function) : 키를 일정 규칙에 따라 가공하여 인덱스로 만드는 공식
    • 해시 값 (Hash Value) : 해시 함수를 거쳐 나온 값으로 해시 테이블의 인덱스.
  • 해싱 (Hashing) : 어떠한 길이를 가진 데이터를 일정 길이의 특정 값으로 변환하는 것
    • 특징
      • 균일성 : 충돌 방지를 위해 해시 값들이 고르게 분포해야 함.
      • 효율성 : 해시 값은 계산 하기 쉬워 속도가 빨라야 함.
      • 결정적(일관성) : 같은 입력값에 대해 항상 같은 해시 값을 출력해야 함.
  • 성능
    • 접근, 삽입, 삭제 : 평균 O(1), 최악의 경우 O(n) ⇒ 모든 키가 동일한 해시 값
  • 해시 충돌 (Hash Collision) : 서로 다른 키가 같은 해시 값으로 출력되어 인덱스가 겹치는 현상.
    • 분리 연결법 (Seperate Chaining) : 해당 인덱스에 연결 리스트로 이어서 저장
      • 해시 테이블 슬롯보다 많은 데이터 저장
      • 한 인덱스에 데이터가 몰리면 효율 저하
    • 개방 주소법 (Open Addressing) : 비어 있는 인덱스를 찾아 저장
      • 선형, 제곱, 더블 해싱 등 일정 규칙에 따라 다른 인덱스로 저장