/Data_Structure

자료구조 정리

Primary LanguageC

자료구조(Data Structure)

배열(Array)

  • 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
  • 같은 종류의 데이터를 효율적으로 관리하기 위해 사용
  • 같은 종류의 데이터를 순차적으로 저장
  • 장점
    • 빠른 접근 가능
      • 첫 데이터의 위치에서 상대적인 위치로 데이터 접근(인덱스 번호로 접근)
  • 단점
    • 데이터 추가/삭제의 어려움
      • 미리 최대 길이를 지정해야 함

큐(Queue)

  • 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
    • FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out)방식으로 스택과 꺼내는 순서가 반대

스택(stack)

  • 데이터를 제한적으로 접근할 수 있는 구조
    • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
  • 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조
  • LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름
  • 장점
    • 구조가 단순해서, 구현이 쉽다.
    • 데이터 저장/읽기 속도가 빠르다.
  • 단점 (일반적인 스택 구현시)
    • 데이터 최대 갯수를 미리 정해야 한다.
    • 저장 공간의 낭비가 발생할 수 있음

연결리스트(Linked List)

  • 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
  • 링크드 리스트 기본 구조와 용어
    • 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성
    • 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
  • 장점
    • 미리 데이터 공간을 미리 할당하지 않아도 됨
  • 단점
    • 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
    • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
    • 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

해쉬 테이블(Hash Table)

  • 키(Key)에 데이터(Value)를 저장하는 데이터 구조
  • Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
  • 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄
  • 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
  • 장점
    • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
    • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
  • 단점
    • 일반적으로 저장공간이 좀더 많이 필요하다.
    • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함
  • 시간복잡도
    • 일반적인 경우(Collision이 없는 경우)는 O(1)
    • 최악의 경우(Collision이 모두 발생하는 경우)는 O(n)

트리(Tree)

  • Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
  • 이진 트리: 노드의 최대 Branch가 2인 트리
  • 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
    • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음
    • 평균 시간 복잡도 : 𝑂(𝑙𝑜𝑔 𝑛)
    • 평균 시간 복잡도는 𝑂(𝑙𝑜𝑔𝑛) 이지만, 이는 트리가 균형잡혀 있을 때의 평균 시간복잡도이며, 최악의 경우는 링크드 리스트등과 동일한 성능을 보여줌 𝑂(𝑛)

힙(Heap)

  • 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
    • 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
  • 힙을 사용하는 이유
    • 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
    • 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, 𝑂(𝑙𝑜𝑔 𝑛)이 걸림
    • 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨
  • 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음
  • 힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조임
  1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
    • 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음
  2. 완전 이진 트리 형태를 가짐
  • 시간복잡도 : 𝑂(𝑙𝑜𝑔 𝑛)