[자료구조] 자료구조

in Study on etc

자료구조 정리

자료구조

  • 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조
  • 코드 상에서 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라, 체계적으로 데이터를 구조화 해야함
  • 종류 : 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 트리 등

분류

  1. 선형 구조
    • 배열, 링크드 리스트, 스택, 큐 등
  2. 비선형 구조
    • 그래프, 트리 등

선형구조

1. 배열

  • index 접근을 지원하는 구조. 인덱스를 통해 요소에 직접 접근 가능
  • 같은 종류의 데이터를 순차적으로 저장
  • 장점
    • 인덱스로 인한 빠른 접근 가능
  • 단점
    • 배열의 크기 고정. 데이터 추가 어려움
    • 중간에 삽입, 삭제하는 경우 index 들을 전부 shift해줘야 하는 비용 발생

2. 링크드 리스트

  • 원소의 물리적 순서와 논리적 순서가 다른 선형 구조
  • 배열구조의 단점을 보완
    • 정해진 크기의 공간 없이 필요할 때마다 데이터 추가 및 삭제가 가능한 데이터 공간, 무한정 크기의 데이터 공간
    • 삽입, 삭제의 배열 문제 발생하지 않음
  • 특정 index에 접근하려면 순차적으로 접근해야하는 비용 발생
  • 장점
    • 미리 데이터 공간을 할당하지 않아도 됨.
  • 단점
    • 연결을 위한 별도 데이터 공간이 필요, 저장공간 효율 높지 ❌
    • 연결 정보를 찾는 시간이 필요하므로 접근 속도 느림
    • 중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요
  • 더블 링크드 리스트
    • 이중 연결 리스트
    • 장점 : 양방향으로 연결되어 있어서 노드 탐색이 양쪽 모두 가능

3. 큐

  • FIFO 스택과 꺼내는 순서 반대
  • 기본용어
    • Enqueue : 큐에 데이터 삽입
    • Dequeue : 큐로부터 데이터 추출
  • BFS 너비탐색 알고리즘에 사용되는 자료구조

4. 스택

  • 데이터를 제한적으로 접근할 수 있는 구조
  • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
  • 후입 선출 : LIFO
    • 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조
  • DFS 깊이탐색 알고리즘에 활용되는 자료구조

스택 구조

  • LIFO 또는 FILO
  • 주요 기능
    • push() : 데이터 스택에 넣기
    • pop() : 데이터 스택으로부터 꺼내기

스택 장점

  • 구조가 단순해서, 구현이 쉬움
  • 데이터 저장/읽기 속도가 빠름

스택 단점

  • 데이터 최대 갯수를 미리 정해야 함
  • 저장 공간의 낭비 발생할 수 있음

비선형 구조

1. 그래프

  • 노드와 간선으로 구성된 자료구조
  • 사이클이 가능하고, 방향/무방향 모두 가능
  • 그래프 구조에서 방향을 갖도록 만든 것이 트리 구조

2. 트리

  • 사이클을 이루지 않도록 구성한 데이터 구조
  • 기본용어
    • Node : 트리를 구성하는 원소 자체
    • Edge : 노드와 노드를 이어주는 선
    • Root : 최상위 노드
    • Terminal(Leaf) : 최하위 노드
    • Internal : 중간 노드
    • Level : 최상위 노드를 Level 0으로 설정했을 때 노드의 깊이
  • 이진 트리 ? 이진 탐색 트리? 레드 블랙 트리?
    • 이진 트리 : Leaf노드를 제외하고 모든 노드의 자식이 2개인 트리구조
    • 이진 탐색 트리
      • 이진탐색 + 연결 리스트를 결합한 자료구조
      • 왼쪽 자식 노드 < 부모노드 < 오른쪽 자식 노드
      • 트리가 한 쪽으로 치우쳐진 모양으로 만들어 질 수 있음(Skewed Tree)
      • 데이터 검색 또는 탐색의 용도로 주로 쓰임
      • 시간 복잡도 O(log2n)
      • 단점 : 최악의 경우 링크드 리스트 등과 동일한 성능 (시간복잡도: O(n))
    • 레드 블랙 트리
      • 이진 탐색 트리의 삽입, 삭제, 탐색의 비효율을 개선한 방법
      • 조건 4가지
        1. 루트노드는 검정
        2. 모든 external node(자식이 없는 노드)는 검정
        3. 빨강노드의 자식은 검정 (→ 빨강노드가 연속으로 나올수 없음)
        4. 모든 리프노드에서 Black Depth는 같다
      • 루트부터 리프 노드까지의 Black 노드 개수는 같다
      • balanced binary search tree로 삽입, 삭제, 순회에 대해서 모두 O(logN) 만족, 최악의 경우에도 O(logN)

3. 힙

  • 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
  • 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

힙을 사용하는 이유

  • 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
  • 이에 반해, 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(log2 n)이 걸림
  • 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현에 활용

힙의 구조

  • 완전 이진 트리 형태

힙 종류

  • 힙은 최대값을 구하기 위한 구조(최대 힙, Max Heap)와 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류됨
  • 최대 힙 : 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같음 ( 부모노드 >= 자식노드 )
  • 최소 힙 : 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같음 ( 부모노드 <= 자식노드 )

힙 vs 이진 탐색 트리

  • 공통점 : 이진 트리
  • 차이점
    • 힙은 각 노드의 값이 자식노드보다 크거나 같음(Max Heap)
    • 힙의 양쪽 자식 노드의 크기는 일관성이 없음

시간 복잡도

  • 최악의 경우 root에서 leaf 노드까지 비교 필요 : O(log2 n)