> [!abstract] Introduction > 자료구조란 무엇일까요? 이 글에서는 PDT(Primitive Data Type), UDT(User-Defined Type), 그리고 ADT(Abstract Data Type)가 무엇이며, 이 세 가지가 어떻게 자료구조*Data Structure*라는 개념을 구성하는지 알아봅니다. ## PDT — 원시 자료형 PDT(Primitive Data Type)는 프로그래밍 언어 수준에서 데이터를 담기 위한 가장 기본적인 형태의 자료형을 말한다. C를 예시로 들자면, `int`, `char`, `double`, `float` 등이 PDT에 속한다. PDT는 프로그래밍 언어를 구성하는 여러 요소 중 하나이며, 제거될 수 없다. PDT의 핵심적인 특징은 다음과 같다. - **언어에 내장**되어 있다. 사용자가 별도로 정의할 필요 없이 언어 자체가 제공한다. - **하드웨어와 직접 대응**한다. `int`는 CPU 레지스터 크기에, `float`는 IEEE 754 부동소수점 표준에 각각 대응된다[^ieee-754]. - **크기가 고정**되어 있다. 예를 들어 C의 `int`는 대부분의 플랫폼에서 4바이트다. PDT만으로는 현실 세계의 복잡한 데이터를 표현하기 어렵다. 학생 한 명의 정보를 다루려면 이름(`char[]`), 학번(`int`), 학점(`double`)을 하나의 단위로 묶어야 하는데, PDT만으로는 이 묶음을 표현할 수 없다. 이 한계를 해결하는 것이 UDT다. ## UDT — 사용자 정의 자료형 UDT(User-Defined Type)는 C의 `struct`[^struct]나 C++·Java·Python 등의 `class`처럼, 프로그래밍 언어의 문법적 지원을 통해 사용자가 임의로 만든 자료형을 의미한다. PDT와 달리 프로그래밍 언어의 필수 요소가 아니며, 프로그래밍 언어 **위에** 구현된 개념에 가깝다. ```c /* C의 UDT 예시: 학생 구조체 */ typedef struct { char name[50]; int student_id; double gpa; } Student; ``` 위 코드에서 `Student`는 PDT인 `char`, `int`, `double`을 조합하여 만든 UDT다. UDT는 PDT들을 조합해서 새로운 자료형을 **구현**하는 수단이다. 담겨지는 데이터의 규칙이나 그 데이터를 다루는 연산은 UDT의 관심사가 아니다. 이 설계를 담당하는 것은 바로 ADT다. ## ADT — 추상 자료형 ADT(Abstract Data Type)는 프로그래밍 언어와 독립적인 개념으로, **자료들과 그 자료들에 대한 연산**을 정의한 명세*specification*다. "무엇을*what* 할 수 있는가"는 정의하지만 "어떻게*how* 하는가"는 정의하지 않는다. 객체지향 프로그래밍의 추상 클래스*abstract class*나 인터페이스*interface*와 밀접한 개념이다. [[Stack|스택]]*Stack*의 ADT를 예로 들어보자. ``` ADT Stack 데이터: 원소들의 순서 있는 모음 연산: push(x) — 원소 x를 꼭대기에 추가 pop() — 꼭대기 원소를 제거하고 반환 peek() — 꼭대기 원소를 제거하지 않고 반환 is_empty() — 스택이 비어 있으면 True 제약: LIFO — 가장 나중에 들어간 원소가 가장 먼저 나옴 ``` 이 명세에는 배열을 쓸지, [[연결 리스트]]를 쓸지에 대한 언급이 전혀 없다. ADT는 구현과 분리된 **계약**이다. 같은 ADT라도 구현 방법에 따라 성능이 달라지며, 이것이 자료구조를 공부하는 핵심 이유 중 하나다. 같은 방식으로, [[Queue]]의 ADT는 "FIFO 정책에 따라 `enqueue`와 `dequeue`를 지원한다"로, [[Priority Queue]]의 ADT는 "우선순위가 가장 높은 원소를 먼저 꺼내는 `insert`와 `extract-min`을 지원한다"로 각각 정의된다. ## 자료구조의 탄생 — PDT, ADT, UDT의 관계 ![[pdtAdtUdt.svg]] 세 개념의 관계를 정리하면 다음과 같다. 1. **ADT로 설계한다.** 어떤 문제를 해결하기 위해, 데이터의 모습과 필요한 연산을 추상적으로 정의한다. "LIFO 정책으로 동작하는 스택이 필요하다"는 것이 ADT 수준의 결정이다. 2. **UDT로 구현한다.** ADT의 명세를 특정 프로그래밍 언어의 문법을 사용하여 코드로 옮긴다. C에서는 `struct`와 함수 포인터로, Python에서는 `class`로 구현한다. 3. **PDT가 기초를 이룬다.** 아무리 복잡한 자료구조라도, 그것을 구성하는 가장 밑바닥의 재료는 프로그래밍 언어가 제공하는 원시 자료형이다. 이 관계를 하나의 흐름으로 표현하면, **ADT(무엇을) → UDT(어떻게) → PDT(무엇으로)** 라는 추상화 단계가 된다. 추상적인 아이디어에서 출발하여 구체적인 코드로 내려오는 과정이 곧 자료구조를 만드는 과정이다. ### ADT와 구현의 분리가 중요한 이유 같은 ADT라도 구현 방법에 따라 각 연산의 시간 복잡도[^time-complexity]가 달라진다. [[Priority Queue]]를 예로 들면 이 차이가 명확하게 드러난다. | 구현 방법 | `insert` | `extract-min` | |-----------|----------|---------------| | 비정렬 배열 | $O(1)$ | $O(n)$ | | 정렬 배열 | $O(n)$ | $O(1)$ | | [[Heap\|이진 힙]] | $O(\log n)$ | $O(\log n)$ | "우선순위가 가장 높은 원소를 먼저 꺼낸다"라는 ADT는 동일하지만, 이진 힙 구현은 삽입과 추출 모두 $O(\log n)$으로 균형 잡힌 성능을 제공한다. ADT와 구현을 분리해서 생각할 수 있어야 문제에 맞는 최적의 자료구조를 선택할 수 있다. ## 자료구조의 분류 자료구조는 데이터 간의 관계에 따라 크게 **선형 자료구조**와 **비선형 자료구조**로 나뉜다. **선형 자료구조**는 원소들이 일렬로 나열되어 각 원소가 최대 하나의 이전 원소와 하나의 다음 원소를 가진다. [[배열]], [[연결 리스트]], [[Stack]], [[Queue]]가 여기에 속한다. **비선형 자료구조**는 원소들 사이에 계층적 또는 망상 관계가 존재한다. [[Tree]]는 하나의 부모에 여러 자식이 연결되는 계층 구조이고, [[Graph]]는 임의의 노드 쌍 사이에 간선이 존재할 수 있는 가장 일반적인 구조다. ``` 자료구조 ├── 선형 자료구조 │ ├── 배열 │ ├── 연결 리스트 │ ├── Stack (LIFO) │ └── Queue (FIFO) │ └── Priority Queue → Heap으로 구현 └── 비선형 자료구조 ├── Tree │ ├── Binary Tree │ ├── Heap (완전 이진 트리 + 힙 속성) │ └── B+ Tree └── Graph └── Connected Component ``` 이 분류는 절대적인 것이 아니라 관점에 따라 달라질 수 있다. 예를 들어 [[Heap]]은 트리 구조이지만 배열로 구현되며, [[Hashing|해시 테이블]]은 배열과 연결 리스트를 모두 사용한다. 중요한 것은 분류 자체가 아니라, 각 자료구조가 **어떤 연산을 효율적으로 지원하는가**를 이해하는 것이다. --- ## 참고 자료 & 더보기 ### 참고 자료 - Kamran, A. (2022) *전문가를 위한 C* (박지윤, Trans.; 1st edn). 한빛미디어. - Cormen, T. H. et al. (2022) *Introduction to Algorithms*. 4th edn. Cambridge, MA: MIT Press. ### 더보기 - [[Stack]] — LIFO 정책의 선형 자료구조 - [[Queue]] — FIFO 정책의 선형 자료구조 - [[Priority Queue]] — 우선순위 기반의 추상 자료형 - [[Heap]] — 우선순위 큐의 대표적 구현 [^ieee-754]: IEEE 754 — 부동소수점 산술 연산의 국제 표준. `float`(단정도, 32비트)와 `double`(배정도, 64비트)의 비트 배치와 연산 규칙을 정의한다. [^struct]: `struct` — C 언어에서 여러 자료형의 변수를 하나의 단위로 묶는 사용자 정의 자료형. [[구조체(C)]] 참조. [^time-complexity]: 시간 복잡도(*time complexity*) — 입력 크기 $n$에 대해 알고리즘이 수행하는 연산 횟수의 증가율을 나타내는 척도. Big O 표기법($O$)으로 표현한다.