자료구조란?

프로그래밍에서 여러 데이터들의 묶음을 저장하고 사용하는 방법을 정의한 것으로 데이터를 구조적으로 표현하는 방식과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초이론이다.

잘 짜인 자료구조는 메모리 용량을 최소한으로 하고, 실행시간도 단축시킴으로써 보다 효율적인 알고리즘을 실행할 수 있게 한다.

배열 (Array)

• 가장 기본적인 선형 데이터 구조이다.
• 한 가지 자료형의 데이터를 순차적으로 저장하는 자료구조
• 생성 시, 크기가 고정되고, 인덱스와 대응하는 데이터를 저장한다.
• 장점 : 인덱스를 통한 검색 연산이 빠르다.
• 단점 : 배열의 크기가 고정되어 있으며 추가/삭제 연산이 느리다.

연결리스트 (Linked List)

• 배열의 단점이 보완된 형태의 자료구조로 배열의 크기가 가변적이다.
• 노드와 포인터를 사용하여 데이터를 저장 및 연결한다.
• 노드(Node) : 데이터와 다음 노드의 주소를 가리키는 포인터 한 쌍으로 구성된다.
• 장점 : 배열의 크기가 가변적이며, 추가/삭제 연산을 할 때는 해당 노드의 포인터 주소만 변경해주면 된다.
• 단점 : 데이터를 삭제하면 데이터 연결을 재구성 해야하고, 인덱스를 참조할려면 첫번째 노드부터 접근해야 한다는 비효율성이 있다.
• 단순 연결리스트, 이중 연결리스트, 원형 연결리스트가 있다.

이중 연결리스트 (Double Linked List)

• 노드가 데이터, 앞뒤 노드의 주소값을 가리키는 포인터로 구성되어 있는 연결 리스트이다.
• 장점 : 앞뒤 양방향으로 검색이 가능하다.

스택 (Stack)

• 순서가 유지되는 선형 자료구조의 일종
• 리스트의 한쪽에서만 데이터의 삽입과 삭제가 일어나는 FILO(First In Last Out) 메커니즘을 가지고 있다.
• 장점 : 구현이 단순하고 메모리 크기가 동적이며, 데이터의 저장 및 검색 속도가 빠르다.
• 단점 : 한 번에 하나의 데이터만 처리 가능하다.
• 프로세스의 실행구조의 기본으로 사용된다.

큐 (Queue)

• 순서가 유지되는 선형 자료구조의 일종
• Stack과 반대로 리스트의 한쪽에서는 삽입이 일어나고 다른 쪽에서는 삭제가 일어나는 FIFO(First In First Out) 메커니즘을 가지고 있다.
• 장점 : 메모리 크기가 동적이며, 데이터 삭제 시 재정렬이 필요없다.
• 단점 : 한 번에 하나의 데이터만 처리 가능하다.
• OS에서 프로세스 스케쥴링 방식 구현에 사용한다.

트리 (Tree)

• Stack, Queue와는 다르게 비선형 자료구조로, 노드와 브랜치를 이용하여 계층적 구조를 표현하는 자료구조이다.
• 그래프의 한 종류로 사이클이 없는 하나의 연결 그래프(Connected Graph) 또는 **방향성이 있는 비순환 그래프(Directed Acyclic Graph)**의 한 종류이다.
• Tree 용어
  • Node (노드) : 트리를 구성하고 있는 원소 그 자체를 말한다.
  • Edge (간선) : 노드와 노드사이를 연결하고 있는 선을 말한다. (=Link, branch)
  • Root node : 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
  • Leaf node : 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
  • Internal node : 단말 노드가 아닌 노드
• 트리를 기반으로 이진트리를 활용하여 탐색 알고리즘 구현에 자주 사용된다.
• 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS 안에 있다.
• 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.

이진트리 (Binary Tree)

• 각 노드가 최대 2개의 자식을 갖는 트리
• 이진 트리 순회
  • 중위 순회(in-order traversal) : 왼쪽 가지 → 현재 노드 → 오른쪽 가지
  • 전위 순회(pre-order traversal) : 현재 노드 → 왼쪽 가지 → 오른쪽 가지
  • 후위 순회(post-order traversal) : 왼쪽 가지 → 오른쪽 가지 → 현재 노드

이진 탐색 트리(Binary Search Tree)

• 이진트리를 기반으로 하여 좌측에는 우측에 위치한 노드보다 작은 값을 가지는 트리
• 이진탐색 트리는 검색에 용이하지만, 구현이 복잡하다.

균형 트리

• O(log N) 시간에 insert와 find를 할 수 있을 정도로 균형이 잘 잡혀 있는 경우 균형 트리라고 한다.
• 예시로 레드-블랙 트리, AVL 트리가 있다.

완전 이진 트리(Complete Binary Tree)

• 트리의 모든 높이에서 노드가 꽉 차 있는 이진트리이다.
• 마지막 레벨을 제외하고 모든 레벨이 채워져 있어야 한다.
• 마지막 레벨은 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

전 이진 트리(Full Binary Tree / Strictly Binary Tree)

• 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

포화 이진 트리(Perfect Binary Tree)

• 전 이진 트리 이면서 완전 이진 트리인 트리이다.
• 모든 내부 노드가 2개의 자식 노드를 가진다.
• 모든 말단 노드가 동일한 깊이 또는 레벨을 가진다.

힙 (Heap)

• 트리구조를 기반으로 한 자료구조로 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리(Complete Binary Tree) 이다.
• 우선순위 큐를 위하여 만들어진 자료구조로 힙으로 우선순위 큐를 구현 시, 삽입과 삭제의 시간 복잡도는 O(log N)이다.
• 최소힙(Min Heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  • key(부모 노드) ≤ key(자식 노드) 인 완전 이진 트리
  • 루트 노드에 가장 작은 값이 있다.
• 최대힙(Max Heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • key(부모 노드) ≥ key(자식 노드) 인 완전 이진 트리
  • 루트 노드에 가장 큰 값이 있다.

그래프 (Graph)

• 정점(Vertex)과 간선(Edge)로 이루어진 데이터 구조
• 탐색 방법에는 깊이 우선 탐색(DFS, Depth First Search)와 너비 우선 탐색(BFS, Breadth First Search)이 있다.
• 인접리스트나 인접 행렬로 구현할 수 있다.
• 장점 : 새로운 요소들의 추가/삭제에 용이하고, 구조의 응용이 가능하다.
• 단점 : 데이터 간의 충돌이 일어날 수 있다.
• 그래프의 종류로 방향/무방향 그래프, 가중치 그래프, 연결/비연결 그래프, 사이클 또는 비순환 그래프 등이 있다.

방향 그래프(Direct Graph) & 무방향 그래프(Undirected Graph)

• 방향 그래프(Directed Graph)
• 무방향 그래프(Undirected Graph)

가중치 그래프(Weighted Graph)

• 가중치 그래프(Weighted Graph)

연결 그래프(Connected Graph) & 비연결 그래프(Unconnected Graph)

• 연결 그래프(Connected Graph)
• 비연결 그래프(Disconnected Graph)

사이클(Cycle) & 비순환 그래프(Acyclic Graph)

• 사이클(Cycle)
• 비순환 그래프(Acyclic Graph)

그래프와 트리의 차이점

출처 - https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

해시 테이블 (Hash Table)

• Key와 Value를 한 쌍으로 저장하는 자료구조
• 평균적으로 충돌이 고려하지 않았을 때, 빠른 탐색속도 O(1)을 갖는다.
• Key를 Hash 함수에 적용하여 나온 결과 값을 인덱스로 하여 해당 인덱스에 Value를 집어 넣는다.
• 장점 : Key를 이용하여 Value를 빠르게 검색할 수 있고, 데이터의 중복을 쉽게 확인할 수 있다.