자료구조

• 복잡도
  • 시간 복잡도
    • 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.
    • 빅오 표기법
      • 어떠한 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지를 나타내는데 쓰인다.
      • 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것인데, 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없애서 표기한다. 예를 들어 어떤 알고리즘의 복잡도가 10n^2+5n이라면 O(n^2)이 된다.
    • 시간 복잡도는 효율적인 코드로 개선하는 데 쓰이는 척도가 된다.
    • 크게 O(n^2), O(n), O(log n), O(1) 순으로 입력 크기가 커질수록 효율적이다.
  • 공간 복잡도
    • 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다.
    • 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함한다.
  • 자료 구조에서의 시간 복잡도
    • 보통 시간 복잡도를 생각할 때 평균, 그리고 최악의 시간 복잡도를 고려해서 쓴다.

각 자료 구조의 평균 시간 복잡도

자료 구조	접근	탐색	삽입	삭제
배열(array)	O(1)	O(n)	O(n)	O(n)
스택(stack)	O(n)	O(n)	O(1)	O(1)
큐(queue)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트(doubly linked list)	O(n)	O(n)	O(1)	O(1)
해시 테이블(hash table)	O(1)	O(1)	O(1)	O(1)
이진 탐색 트리(BST)	O(log n)	O(log n)	O(log n)	O(log n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)
레드 블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)

 

각 자료 구조의 최악의 시간 복잡도

자료 구조	접근	탐색	삽입	삭제
배열(array)	O(1)	O(n)	O(n)	O(n)
스택(stack)	O(n)	O(n)	O(1)	O(1)
큐(queue)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트(doubly linked list)	O(n)	O(n)	O(1)	O(1)
해시 테이블(hash table)	O(n)	O(n)	O(n)	O(n)
이진 탐색 트리(BST)	O(n)	O(n)	O(n)	O(n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)
레드 블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)

 

• 선형 자료 구조
  • 요소가 일렬로 나열되어 있는 구조를 말한다.
    • 연결 리스트
      • 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조이다.
      • prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이며, 싱글, 이중, 원형이 있다.
      • 싱글 연결 리스트 - next 포인터만 가진다.
      • 이중 연결 리스트 - next 포인터와 prev 포인터를 가진다.
      • 원형 이중 연결 리스트 - 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.
      • 맨 앞에 있는 노드를 헤드라고 한다.
    • 배열
      • 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다.
      • 중복을 허용하고 순서가 있다.
      • 정적 배열을 기반으로 랜덤 접근이 가능하다.
        
        • 랜덤 접근 - 직접 접근이라고도 하며 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능이다. 이와 반대로 데이터를 저장된 순서대로 검색해야 하는 순차적 접근이 있다.
      • 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용한다.
      • 데이터 추가와 삭제를 많이 할 때는 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋다.
    • 벡터
      • 동적으로 요소를 할당할 수 있는 동적 배열이다.
      • 컴파일 시점에 개수를 모른다면 벡터를 써야 한다.
      • 중복을 허용하고 순서가 있고 랜덤 접근이 가능하다.
    • 스택
      • 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료 구조이다.
      • 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다.
    • 큐
      • 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 가진 자료 구조이다.
      • 스택과는 반대되는 개념을 가진다.
      • CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용한다.
• 비선형 자료 구조 
  • 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 자료 구조를 말한다. 
    
    • 그래프
      • 정점과 간선으로 이루어진 자료 구조를 말한다.
        • 정점과 간선 - 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때 어떠한 곳이 정점, 무언가는 간선이 된다.
      • 정점으로 나가는 간선을 해당 정점의 outdegree라고 하며, 들어오는 간선을 indegree라고 한다.
      • outdegree만 있거나 indegree만 있다면 단방향 간선이고, 둘 모두 있다면 양방향 간선이 된다.
      • 가중치 - 간선과 정점 사이에 드는 비용을 말한다.
    • 트리
      • 그래프 중 하나로 그래프처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합이다.
      • 루트 노드, 내부 노드, 리프 노드 등으로 구성된다.
        • 루트 노드 - 가장 위에 있는 노드를 뜻한다. 보통 트리 문제가 나오고 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 많다.
        • 내부 노드 - 루트 노브와 리프 노드 사이에 있는 노드를 뜻한다.
        • 리프 노드 - 자식 노드가 없는 노드를 뜻한다.
      • 부모, 자식 계층 구조를 가진다. 같은 경로상에서 어떤 노드보다 위에 있으면 부모, 아래 있으면 자식 노드가 된다.
      • 간선 수는 노드 수 - 1 이다.
      • 임의의 두 노드 사이의 경로는 하나만 존재한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있다.
      • 깊이 - 각 노드마다 다르며, 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리를 말한다. 레벨이라고도 한다.
      • 높이 - 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리를 의미한다.
      • 서브트리 - 트리 내의 하위 집합을 말한다. 트리 내의 부분집합이라고도 보면 된다.
      • 이진 트리
        • 자식의 노드 수가 2개 이하인 트리를 의미하며, 아래와 같이 구분된다.
        • 정이진 트리 - 자식 노드가 0 또는 두 개인 이진 트리를 말한다.
        • 완전 이진 트리 - 왼쪽에서부터 채워져 있는 이진 트리를 말한다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있다.
        • 변질 이진 트리 - 자식 노드가 하나밖에 없는 이진 트리를 말한다.
        • 포화 이진 트리 - 모든 노드가 꽉 차 있는 이진 트리를 말한다.
        • 균형 이진 트리 - 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 말한다. map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나이다.
      • 이진 탐색 트리
        • 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리를 말한다. 이 특성은 하위 트리에도 적용되어있다.
        • 이와 같은 특성은 검색에서 용이하다.
      • AVL 트리
        • 트리가 최악의 경우인 선형적 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리이다.
        • 두 자식 서브트리의 높이는 항상 최대 1만큼 차이나는 특징이 있다.
        • 삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전 시키며 균형을 잡는다.
      • 레드 블랙 트리
        • 균형 이진 탐색 트리로 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는데 사용된다.
        • "모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다." 등의 규칙을 기반으로 균형을 잡는 트리이다.
    • 힙
      • 완전 이진 트리 기반의 자료 구조이며, 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리를 말한다.
      • 최대힙 - 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 한다. 또한, 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
      • 최소힙 - 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
      • 어떠한 값이 들어와도 특정 힙의 규칙을 지키게 만들어져 있다. 최대힙을 기반으로 예시를 살펴보자.
      • 최대힙의 삽입
        1. 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
        2. 이 새로운 노드를 부모 노드들과의 크기를 비교하며 교환해서 힙의 성질을 만족시킨다.
      • 최대힙의 삭제
        • 최대힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 또 다시 스왑 등의 과정을 거쳐 재구성된다.
    • 우선순위 큐
      
      • 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조이다.
      • 힙을 기반으로 구현된다.
    • 맵
      • 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조이다.
    • 셋
      • 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소는 없고 오로지 unique한 값만 저장하는 자료구조이다.
    • 해시 테이블
      
      • 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블이다.