> For the complete documentation index, see [llms.txt](https://byulseop-til.gitbook.io/sinheeseop_til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://byulseop-til.gitbook.io/sinheeseop_til/cs-computer-science/datastructure/_.md).

# 자료구조 개념서

```
순서대로 읽으면 알아서 이해되게끔 구성하였다. 
```

## \[자료구조] 나만의 4단계 정의법

자료구조는 거창한 게 아니다. 나는 이를 **\[문제 정의 → 가치 판단 → 설계 → 구현]** 의 4단계 흐름으로 정의한다.

#### 1단계 : 상황에 필요한 기능을 정의한다 (Requirements)

* **질문:** "무엇(What)을 해야 하는가?"
* **설명:** 구현 방법은 고민하지 않고, 필요한 기능만 나열한다.
* **예시:** 유통기한 관리를 위해 "먼저 들어온 게 먼저 나가야(FIFO)" 한다.

#### 2단계 : 핵심 가치를 판단한다 (Core Value & Type)

* **질문:** "데이터의 성격과 중요한 성능은 무엇인가?"
* **설명:** 1단계 기능에 제약조건을 더해 **데이터의 형태(Type)** 를 결정한다.
* **예시:**
  * "난 맨 앞에서만 꺼낼 거야(순차적)" → **선형(Linear) 구조** 필요.
  * "데이터 간의 상하 관계가 필요해" → **트리(Tree) 구조** 필요.
  * "키 값으로 바로 찾아야 해" → **해시(Hash) 구조** 필요.

#### 3단계 : 설계도를 짠다 (Logical Design)

* **질문:** "어떤 규칙(Rule)으로 데이터를 배치할 것인가?"
* **설명:** 2단계에서 정한 형태에 구체적인 자료구조 개념을 적용한다.
* **예시:**
  * (트리 선택 시) "자식을 2명만 낳는 **이진 트리** 로 가자."
  * (해시 선택 시) "충돌 나면 리스트로 묶는 **체이닝** 방식을 쓰자."

#### 3.5단계 : 고오급 설계도 (Specific Algorithm)

* **설명:** 조건이 더 까다로운 경우, 특정 알고리즘을 추가한다.
* **예시:**
  * 그냥 이진 트리인데... "부모가 무조건 커야 해" → **힙(Heap)**
  * 그냥 이진 트리인데... "좌우 균형을 계속 맞춰야 해" → **레드블랙트리**

#### 4단계 : 물리적 구현 (Physical Implementation)

* **질문:** "메모리에 실제로 어떻게 저장할 것인가?"
* **설명:** 가장 근본인 **배열(Array) vs 연결(Linked)** 중 하나를 선택해 코드로 옮긴다.
* **예시:**
  * "힙(3.5단계)을 만들 건데, 빈틈이 없으니 **배열 기반**이어야겠네?" → `ArrayList`로 구현.
  * "트리인데 구멍이 많으니 **연결 기반**이어야겠네?" → `Node` 클래스로 구현.

#### 종합 정리

가장 중요한 건 **"연결이냐, 배열이냐"** 의 차이를 명확하게 아는 것이다. 우리가 2단계(가치 판단)에서 내린 결론(예: 검색 속도가 중요함)에 따라 4단계의 구현 방식이 결정된다.

* **예시:** 중복 없음 + 순서 필요 없음 + **검색 속도 생명** (가치 판단)
  * → **해시(3단계)** 설계를 선택
  * → **배열 기반(4단계)** 구현을 선택 (`HashSet`)

### 자료구조 핵심 개념 5가지

이 생태계를 이해하기 위해 꼭 알아야 할 5가지 용어다.

1. **추상 자료형 (ADT)**
2. **자료구조 (Data Structure)**
3. **구현체 (Implementation)**
4. **배열 기반 (Array)**
5. **연결 기반 (Linked)**

#### 왜 핵심인가?

1. 추상 자료형과 자료구조를 차이를 알아야 자료구조 생태계를 이해하게 된다.\
   이해를 못하면 암기로 가야하며 암기를 하면 응용이 어렵다.
2. 모든 자료구조에 무조건 들어가는 핵심이 딱 저 두개(배열, 연결)로 만들어진다.\
   배열기반과 연결기반의 차이만 정확하게 알아도 앞으로 배우는 자료구조를 금방 파악 할 수 있다.

#### 1. ADT란? (1\~2 단계)

**"추상 자료형 (Abstract Data Type)"** 우리가 구현할 자료구조의 \*\*기능 명세서(Interface)\*\*다.

* "어떻게(How)" 구현할지는 관심 없고, "무엇(What)"을 할지만 정의한다.
* **예시:** "넣으면 쌓이고, 꺼내면 맨 위에게 나온다."
* *( 참고 : 스택(Stack)의 경우 구조가 단순해서 ADT 이름 자체가 자료구조 이름처럼 쓰이지만, 본질은 '기능 명세'다. )*

#### 2. 자료구조란? (3\~3.5 단계)

**"데이터 구조 (Data Structure)"** ADT에서 정의한 기능을 효율적으로 수행하기 위한 **구체적인 방법론(Methodology)** 이다.

* ADT를 만족시키기 위해 논리적으로 데이터를 어떻게 배치할지 설계한 것이다.
* **예시:** 힙, 이진 트리, 해시 테이블 등.
* *(이들도 뜯어보면 결국 배열 또는 연결을 응용해서 만든 규칙일 뿐이다.)*

#### 3. 구현체란? (4 단계)

**"구현 클래스 (Implementation Class)"** 실제 프로그래밍 언어로 물리적 저장 방식(배열/연결)까지 결정하여 코딩한 결과물이다.

* **예시:** 자바의 `java.util.Stack`, `TreeMap(레드블랙으로 구현)`, `LinkedList` 등.

> \*\* \[중요] Stack 으로 알아보는 자료구조의 본질\*\*
>
> 우리는 `다른 ADT 인 Deque 를 활용하여 만든 ArrayDeque`\
> 또는 `LinkedList`나 `ArrayList`등 이러한 구현체로 가져다가 스택처럼 쓸 수 있다.\
> 하지만 `LinkedList`를 스택이라 부르지 않는 이유는 무엇일까?\
> 또 `이렇게 다른 ADT 와 자료구조, 구현체로 스택을 사용 할 수 있는 이유`는 무엇일까?
>
> * **스택(Stack)** 은 "LIFO 방식으로 동작하라"는 **기능명세서(ADT)** 이기 때문이다.
>
> **즉, ADT 를 따르고 성능 문제가 없다면, 내부는 `ArrayList`든 `LinkedList`든 어떤 구현체를 사용해도 되며 또는 `다른 방법론(자료구조)`를 사용해도 상관없다.**