자료구조는 데이터를 효율적으로 저장하고 관리하며, 다양한 연산을 쉽게 수행할 수 있도록 설계된 구조를 말한다. 자료구조에는 Array, Linked List, Stack, Queue, Tree와 같은 다양한 종류가 이에 속하고 알고리즘 설계의 기초가 된다. 예를 들어 Tree를 기반으로 Binary Search Tree를 구현하여 데이터 검색 속도를 최적화하거나 그래프를 활용하여 최단 경로 계산(Dijkstra 알고리즘)을 수행하는 등 문제 해결의 핵심 역활을 한다.

자료구조 5인방

여러 자료구조가 있지만 그 중에 가장 기본이 되는 자료구조 5개가 있다.

자료구조 5인방

연결리스트(Linked List), 스택(Stack), 큐(Queue), 해시테이블(Hash), 힙(Heap)은 꼭 익혀야하는 기본적인 자료구조 5인방이다. 이 자료구조들은 다양한 문제를 해결하는데 적합한 특성을 가지고 있는데, 연결 리스트는 동적으로 데이터를 관리하는데 유리하고, 스택은 재귀적인 문제를 해결할때 자주 사용된다. 큐는 순차적으로 데이터를 처리해야하는 상황에서 유리하고 해시 테이블은 데이터를 빠르게 검색하거나 삽입할 수 있는 구조를 제공한다. 실제 서비스 중인 구조에서도 사용되는데 예를 들어 큐는 대기열로 활용하거나 해시 테이블은 캐싱으로 사용하는 등 다양한 분야에서 자료구조를 사용한다.

또한 이런 기본적인 자료구조들은 효율적인 알고리즘 설계의 기반이 되는데, 예를 들어 그래프 탐색 알고리즘에서 깊이 우선 탐색(DFS)는 스택을 너비 우선 탐색(BFS)는 큐를 사용하고, 데이터베이스의 인덱싱에서는 해시 테이블이 사용되어 대규모 데이터를 바르게 검색할 수 있도록 돕는다.

다양한 자료구조

기본 자료구조 외에도 특정 문제 유형을 해결하기 위해 설계된 다양한 자료구조가 있다.

  • 그래프(Graph)
  • 집합(Set)
  • 덱(Deque)
  • 우선순위 큐(Priority Queue)
  • 트라이(Trie)
  • 버퍼(Buffer)

이외에도 다양한 자료구조가 있는데, 자료구조인지 아닌지 구분하는 기분은 무엇일까?
자료구조는 단순히 데이터를 저장하는 방식뿐 아니라 데이터를 효율적으로 저장, 관리, 접근, 수정하는데 필요한 구조와 연산을 포함한다. 만약 자료구조인지 여부를 구분하고 싶다면 아래의 기준을 모두 충족하는지 확인해보자.

  1. 자료구조는 데이터를 특정 규칙이나 구조에 따라 저장한다.
  2. 데이터를 처리하는 기본적인 연산(삽입, 삭제, 검색, 갱신 등)이 명확하게 정의되어 있어야 한다.
  3. 데이터를 효율적으로 처리할 목적으로 설계되어 있어야 한다.

위 기준을 충족한다면 자료구조인지 여부를 판단할 수 있는데 예시를 들어보자.

  • Array는 자료구조인가? 아닌가?
    • 배열은 연속된 메모리 공간에 데이터를 저장하며, 인덱스를 통해 접근이 가능하다.
    • 인덱스를 기반으로 한 삽입, 삭제, 검색이 명확하게 정의되어 있다.
    • 특정 인덱스 접근은 O(1)으로 빠르고, 선형 데이터 처리에 적합하다.

결론적으로 배열은 자료구조로 볼 수 있다. 그렇다면 JSON은 자료구조일까?

  • JSON은 자료구조인가? 아닌가?
    • 데이터를 키-값 쌍으로 표현하지만, 저장 방식 자체가 아닌 데이터 교환 포맷이다.
    • 데이터 삽입, 삭제 등의 연산을 정의하지 않는다.
    • 데이터를 저장하거나 관리하기 위해 설계된 것이 아니라 데이터를 전달하는데 사용된다.

JSON은 자료구조처럼 보이지만 자료구조로 보기는 힘들다.

{
  "name": "Alice",
  "age": 30,
  "skills": ["Python", "Java"]
}

데이터를 키-값 쌍으로 표현하기도 하고 중첩 구조를 통해서 복잡한 데이터를 표현할 수 있기 때문에 Dictionary나 해시 테이블과 비슷하게 보여서 오해할 수 있다. 또한 JSON 데이터를 삽입, 삭제, 수정, 검색하는 작업이 가능하므로 더욱 더 자료구조처럼 느껴질 수 있다.

하지만 JSON은 데이터를 저장하거나 전달할 때 사용하는 표현 방식이다. 주 목적은 데이터를 읽고 쓸 수 있도록 문자열 형태로 직렬화(Serialization)하는 것이다. 또한 JSON 자체는 데이터 조작하는 연산을 제공하지 않는다. 데이터를 조작하려면 딕셔너리와 같은 자료구조로 변환해야하며 데이터를 효율적으로 관리하기 설계된 자료구조가 아니다.

import json
json_data = '{"name": "Alice", "age": 30}'
data = json.loads(json_data)  # JSON을 dict로 변환
data["age"] = 31             # 수정
json_data = json.dumps(data) # 다시 JSON으로 변환

연산을 제공하는 것은 파싱된 딕셔너리이지 JSON 자체는 아니며, 연산이 끝난 후에는 다시 JSON 형식으로 직렬화하여 전송하기 때문에 자료구조라고 보기는 어렵다.

자료구조의 선형과 비선형

자료구조는 크게 두 가지로 선형 자료구조와 비선형 자료구조로 나눌 수 있다.

자료구조

선형구조(Linear)

자료를 구성하는 원소들을 하나씩 순차적으로 나열시킨 형태를 선형구조라고 한다. 각 데이터 항목은 바로 앞이나 뒤의 하나의 데이터 항목과 관련이 있다. 선형구조는 데이터를 목록 형태로 저장하고 관리하기 때문에 데이터 추가, 삭제, 탐색 등의 작업을 직관적이고 단순하게 수행할 수 있다.

  • 배열 (Array)
    • 배열은 고정된 크기를 가지고, 메모리 상에 연속적으로 할당된 데이터 항목의 집합이다.
    • 크기가 고정되어 있어 배열을 생성할 때 최대 크기를 미리 정해야 한다.
    • 배열의 각 요소는 인덱스를 통해 직접 적근할 수 있어, 접근 속도가 매우 빠르다.
      • 그러나 삽입/삭제는 느리다.
        • 배열이 연속된 메모리 공간에 데이터를 저장하기 때문에 삽입하거나 삭제할 때 데이터를 이동하는 추가 작업을 진행해야 한다.
        • 예 : 배열 [10,20,30,40] 에서 1번 인덱스에 15를 삽입한다면 30과 40을 한 칸씩 뒤로 이동시키고 해당 데이터를 삽입한다.
    • 배열은 차원의 수와 관계없이 모든 배열 구조를 포함하는 자료구조며, 차원이 높아질수록 데이터의 구조가 복잡해지지만, 본질적으로 연속된 메모리 블록에서 데이터를 배치한다는 동일한 원칙을 따른다. array
  • 연결 리스트(Linked List)
    • 연결리스트는 데이터 항목(노드)이 포인터를 통해 순차적으로 연결된 구조다.
    • 각 노드는 데이터와 다음 노드를 가르키는 포인터로 구성된다.
    • 연결 리스트는 동적으로 크기가 변할 수 있어, 실행 시간에 데이터 항목의 추가나 삭제가 자유롭다.
      • 그러나 데이터 접근이 느리다.
    • 연결 리스트는 여러 종류가 있다.
      • 단일 연결 리스트(Singly Linked List)
      • 이중 연결 리스트(Doubly Linked List)
      • 원형 연결 리스트(Circular Linked List)

linkedlist

  • 스택(Stack)
    • 스택은 LIFO(Last In, Fisrt Out)방식이다
    • 데이터를 추가하는 작업을 ‘푸시(push)’, 스택에서 데이터를 제거하는 작업을 팝(pop)이라고 한다.
    • 스택은 함수의 호출과 반환, 깊이 우선 탐색(DFS)등에 사용된다.

stack

  • 큐(Queue)
    • 큐는 FIFO(Fisrt In First Out)방식이다
    • 큐에 데이터를 추가하는 작업을 인큐(enqueue), 데이터를 제거하는 작업을 디큐(dequeue)라고 한다.
    • 큐는 버퍼, 너비 우선 탐색(BFS)등에 사용된다.
      queue

비선형구조(NonLinear)

데이터 항목이 계층적이거나 그래프 형태로 구성되어, 한 항목이 여러 개의 다른 항목과 연결될 수 있는 자료구조를 말한다. 복잡한 데이터 관게를 모델링하고 표현하기에 적합하고, 데이터 간에 일대일(One-to-One), 일대다(One-to-Many), 다대다(Many-to-Many)와 같은 관계가 있을 때 비선형 구조를 사용한다.

  • 트리(Tree)
    • 트리는 계층적인 구조를 가진 자료구조, 노드(Node)와 이 노드들을 연결하는 간선(Edge)으로 구성된다.
    • 트리의 가장 상위에 있는 노드를 루트(Root)노드라고 하고, 루트 노드에서부터 시작하여 분기하면서 여러 개의 자식 노드를 가질 수 있다.
    • 트리는 여러 종류가 있다.
      • 이진 트리(Binary Tree) : 각 노드가 최대 2개의 자식을 가짐
      • 이진 탐색 트리(Binary Search Tree) : 정렬된 데이터 저장
      • 힙(Heap) : 최대/최소 우선 순위

tree

  • 그래프(Graph)
    • 그래프는 노드들이 간선으로 연결된 구조를 가진 자료구조다.
    • 그래프는 방향이 있거나 없을 수 있고, 네트워크 모델링, 소셜 네트워크, 웹 페이징 링크 구조 등 다양한 문제에 사용한다.
    • 그래프는 여러 특징이 있다.
      • 방향 그래프 : 간선에 방향이 있음
      • 무방향 그래프 : 간선에 방향이 없음
      • 가중치 그래프 : 간선에 가중치가 있음

graph

  • 힙(Heap)
    • 힙은 완전 이진 트리의 일종으로, 힙 속성을 만족하는 트리 기반의 자료구조다.
    • 힙은 주로 우선순위 큐를 구현하는데 사용된다.

max-and-min-heap

  • 해시(Hash)
    • 데이터를 키-값(key-value)쌍으로 저장하며 키를 해시 함수를 통해 특정 메모리 위치(버킷)에 매핑한다.
    • 데이터 접근이 빠르다.
    • 충돌 관리가 필요하다(체이닝, 오픈 어드레싱)
    • 데이터베이스 인덱스나 캐싱 시스템 등에서 사용한다.

hash-tabl

🫨 자료구조를 선형(linear)와 비선형(non-linear)으로 나누는 이유는 무엇일까?
이렇게 나누는 이유는 데이터를 표현하고 처리하는 방식의 차이를 명확히하고 문제의 특성에 맞는 구조를 선택하도록 돋기 위해서며 이 구분은 자료의 구조적 특징과 연산 방식을 기반으로 한다.

  • 선형 자료구조
    • 데이터가 일직선으로 배치
    • 요소 간 관계가 1:1
      • 배열, 연결 리시트, 스택, 큐
      • 예시 : 작업을 순서대로 처리해야 하는 상황에 적합함.
        • 작업 스케줄링, 함수 호출 관리, 대기열
  • 비선형 자료구조
    • 데이터가 계층적이거나 복잡한 방식으로 연결
    • 요소 간 데이터가 1:N 또는 N:N
      • 트리, 그래프, 힙
      • 예시 : 데이터 간 복잡한 관계를 표현해야 하는 상황에 적합함.
        • 최단 경로 탐색, SNS 친구 추천

그럼 선형과 비선형 자료구조에 맞지 않게 사용하면 얼마나 비효율적일까? 특정 도시 간의 최단경로를 배열로 저장한다고 가정해보자. 모든 도로 정보를 반복적으로 확인하며 가능한 경로를 계산해야한다. 최악의 경우 O(n!) 시간 복잡도가 필요하다.

roads = [
    {"start": "A", "end": "B", "distance": 5},
    {"start": "A", "end": "C", "distance": 10},
    {"start": "B", "end": "C", "distance": 3},
    {"start": "C", "end": "D", "distance": 2}
]

배열은 도로 간 연결 관계를 명시적으로 나타내지 못하고, 가능한 모든 경로를 탐색해야 최단 경로를 계산할 수 있기 때문에 선형 자료구조를 사용한다면 비효율적일 수 밖에 없다. 이런 경우 비선형 자료구조인 그래프를 사용하여 도로 정보를 정점(Vertex)와 가중치(Weight)를 가진 간선(Edge)로 표현하여 각 도로의 연결 상태를 명확히 표현한다.

A --5-- B
 \     /
 10   3
  \   /
   C --2-- D

그래프를 사용하면 다익스트라 알고리즘이나 벨만-포드 알고리즘 등으로 최단 경로를 효율적으로 계산할 수 있다.
결론적으로 자료구조를 선형과 비선형으로 나누는 이유는 데이터를 처리하는 효율성에 있고, 이러한 차이를 이해하고 적절히 활용하면 문제 해결에서 큰 성능 차이를 만들 수 있다.