Home > Algorithm > 2024 > πŸ“¦[DS,Algorithm] 자료ꡬ쑰 μ†Œκ°œ

πŸ“¦[DS,Algorithm] 자료ꡬ쑰 μ†Œκ°œ
DataStructure Algorithm

1️⃣ 자료ꡬ쑰(Data Structure)

자료ꡬ쑰(Data Structure)λŠ” 데이터λ₯Ό 효율적으둜 μ €μž₯ν•˜κ³  κ΄€λ¦¬ν•˜λ©°, 이λ₯Ό 톡해 데이터λ₯Ό 효율적으둜 μ ‘κ·Όν•˜κ³  μˆ˜μ •ν•  수 μžˆλ„λ‘ ν•˜λŠ” 체계적인 λ°©λ²•μž…λ‹ˆλ‹€.

μžλ£Œκ΅¬μ‘°λŠ” μ•Œκ³ λ¦¬μ¦˜μ˜ μ„±λŠ₯을 μ΅œμ ν™”ν•˜κ³  ν”„λ‘œκ·Έλž¨μ˜ νš¨μœ¨μ„±μ„ ν–₯μƒμ‹œν‚€λŠ” 데 μ€‘μš”ν•œ 역할을 ν•©λ‹ˆλ‹€.

κΈ°λ³Έ κ°œλ….

μžλ£Œκ΅¬μ‘°λŠ” 데이터λ₯Ό μ €μž₯ν•˜λŠ” 방식과 데이터λ₯Ό μ‘°μž‘ν•˜λŠ” 방법을 μ •μ˜ν•©λ‹ˆλ‹€.

μ΄λŠ” 데이터λ₯Ό μ–΄λ–»κ²Œ λ°°μ—΄ν•˜κ³ , μ ‘κ·Όν•˜κ³ , μˆ˜μ •ν•˜κ³ , μ‚­μ œν• μ§€λ₯Ό κ·œμ •ν•˜λŠ” κ·œμΉ™κ³Ό λ°©λ²•μ˜ μ§‘ν•©μž…λ‹ˆλ‹€.

μ£Όμš” λͺ©μ .

  1. 효율적인 데이터 μ €μž₯ 및 μ ‘κ·Ό.
    • 데이터λ₯Ό 효율적으둜 μ €μž₯ν•˜μ—¬ λΉ λ₯΄κ²Œ μ ‘κ·Όν•˜κ³  검색할 수 μžˆλ„λ‘ ν•©λ‹ˆλ‹€.
  2. 데이터 μˆ˜μ • 및 μ‚­μ œ 용이.
    • 데이터λ₯Ό μ‰½κ²Œ μˆ˜μ •ν•˜κ³  μ‚­μ œν•  수 μžˆλ„λ‘ ν•©λ‹ˆλ‹€.
  3. μ•Œκ³ λ¦¬μ¦˜ μ΅œμ ν™”.
    • μ•Œκ³ λ¦¬μ¦˜μ˜ μ„±λŠ₯을 μ΅œμ ν™”ν•˜κ³  μ‹€ν–‰ μ‹œκ°„μ„ λ‹¨μΆ•μ‹œν‚΅λ‹ˆλ‹€.

μ£Όμš” μ’…λ₯˜.

  1. λ°°μ—΄(Array)
    • κ³ μ •λœ 크기의 μ—°μ†λœ λ©”λͺ¨λ¦¬ 곡간에 데이터λ₯Ό μ €μž₯ν•©λ‹ˆλ‹€.
    • 인덱슀λ₯Ό μ‚¬μš©ν•˜μ—¬ 데이터에 λΉ λ₯΄κ²Œ μ ‘κ·Όν•  수 μžˆμŠ΅λ‹ˆλ‹€.
  2. μ—°κ²° 리슀트(Linked List)
    • 각 μš”μ†Œκ°€ 데이터와 λ‹€μŒ μš”μ†Œλ₯Ό κ°€λ¦¬ν‚€λŠ” 포인터λ₯Ό ν¬ν•¨ν•©λ‹ˆλ‹€.
    • 동적 크기 쑰절이 κ°€λŠ₯ν•˜λ©° μ‚½μž…κ³Ό μ‚­μ œκ°€ μš©μ΄ν•©λ‹ˆλ‹€.
  3. μŠ€νƒ(Stack)
    • ν›„μž…μ„ μΆœ(LIFO, Last In First Out) λ°©μ‹μœΌλ‘œ λ™μž‘ν•©λ‹ˆλ‹€.
    • 데이터λ₯Ό μ‚½μž…ν•˜λŠ” push와 μ‚­μ œν•˜λŠ” pop 연산을 κ°€μ§‘λ‹ˆλ‹€.
  4. 큐(Queue)
    • μ„ μž…μ„ μΆœ(FIFO, First In First Out) λ°©μ‹μœΌλ‘œ λ™μž‘ν•©λ‹ˆλ‹€.
    • 데이터λ₯Ό μ‚½μž…ν•˜λŠ” enqueue와 μ‚­μ œν•˜λŠ” dequeue 연산을 κ°€μ§‘λ‹ˆλ‹€.
  5. 트리(Tree)
    • 계측적 ꡬ쑰λ₯Ό 가지며, λ…Έλ“œμ™€ μ—μ§€λ‘œ κ΅¬μ„±λ©λ‹ˆλ‹€.
    • 이진 트리, 이진 탐색 트리, AVL 트리 λ“± λ‹€μ–‘ν•œ ν˜•νƒœκ°€ μžˆμŠ΅λ‹ˆλ‹€.
  6. κ·Έλž˜ν”„(Graph)
    • λ…Έλ“œ(정점)와 에지(κ°„μ„ )둜 κ΅¬μ„±λœ 자료ꡬ쑰둜, λ‹€μ–‘ν•œ 관계λ₯Ό ν‘œν˜„ν•  수 μžˆμŠ΅λ‹ˆλ‹€.
    • λ°©ν–₯ κ·Έλž˜ν”„, 무방ν–₯ κ·Έλž˜ν”„ 등이 μžˆμŠ΅λ‹ˆλ‹€.
  7. ν•΄μ‹œ ν…Œμ΄λΈ”(Hash Table)
    • ν‚€-κ°’ μŒμ„ μ €μž₯ν•˜λ©°, ν•΄μ‹œ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•˜μ—¬ 데이터에 λΉ λ₯΄κ²Œ μ ‘κ·Όν•  수 μžˆμŠ΅λ‹ˆλ‹€.
    • 좩돌 ν•΄κ²° λ°©λ²•μœΌλ‘œ 체이닝과 개방 μ£Όμ†Œλ²•μ΄ μžˆμŠ΅λ‹ˆλ‹€.

μ‘μš© 사둀.

μžλ£Œκ΅¬μ‘°λŠ” λ°μ΄ν„°λ² μ΄μŠ€, 운영체제, λ„€νŠΈμ›Œν¬, 인곡지λŠ₯, κ²Œμž„ 개발 λ“± λ‹€μ–‘ν•œ λΆ„μ•Όμ—μ„œ μ€‘μš”ν•œ 역할을 ν•©λ‹ˆλ‹€.
μ μ ˆν•œ 자료ꡬ쑰의 선택은 ν”„λ‘œκ·Έλž¨μ˜ μ„±λŠ₯κ³Ό νš¨μœ¨μ„±μ„ 크게 ν–₯μƒμ‹œν‚¬ 수 μžˆμŠ΅λ‹ˆλ‹€.


2️⃣ 자료ꡬ쑰의 λΆ„λ₯˜

1️⃣ μ„ ν˜• 자료ꡬ쑰(Linear Data Structure)

μ„ ν˜• 자료ꡬ쑰(Linear Data Structure)λŠ” 데이터 μš”μ†Œλ“€μ΄ 순차적으둜 λ°°μ—΄λœ ꡬ쑰λ₯Ό μ˜λ―Έν•©λ‹ˆλ‹€.

이 μžλ£Œκ΅¬μ‘°μ—μ„œλŠ” 데이터 μš”μ†Œλ“€μ΄ 직선 ν˜•νƒœλ‘œ μ—°κ²°λ˜μ–΄ 있으며, 각 μš”μ†ŒλŠ” ν•œ λ‹€μŒ μš”μ†Œλ‚˜ 이전 μš”μ†Œμ™€ μ—°κ²°λ˜μ–΄ μžˆμŠ΅λ‹ˆλ‹€.

μ„ ν˜• 자료ꡬ쑰의 μ£Όμš” νŠΉμ§•μΈ 데이터 μš”μ†Œλ“€μ΄ ν•œ μ€„λ‘œ λ°°μ—΄λ˜μ–΄ μžˆλ‹€λŠ” 점 μž…λ‹ˆλ‹€.

μ£Όμš” μ„ ν˜• 자료ꡬ쑰λ₯΄λŠ” λ°°μ—΄, μ—°κ²° 리슀트, μŠ€νƒ, 큐 등이 μžˆμŠ΅λ‹ˆλ‹€.

μ£Όμš” μ„ ν˜• 자료ꡬ쑰.

  1. λ°°μ—΄(Array)
    • μ •μ˜ : λ™μΌν•œ νƒ€μž…μ˜ 데이터 μš”μ†Œλ“€μ΄ μ—°μ†λœ λ©”λͺ¨λ¦¬ 곡간에 μ €μž₯λ˜λŠ” μžλ£Œκ΅¬μ‘°μž…λ‹ˆλ‹€.
    • νŠΉμ§• : κ³ μ •λœ 크기λ₯Ό 가지며 인덱슀λ₯Ό 톡해 데이터에 λΉ λ₯΄κ²Œ μ ‘κ·Όν•  수 μžˆμŠ΅λ‹ˆλ‹€.
    • μ˜ˆμ‹œ : μ •μˆ˜ν˜• λ°°μ—΄, λ¬Έμžμ—΄ λ°°μ—΄ λ“±.
  2. μ—°κ²° 리슀트(Linked List)
    • μ •μ˜ : 각 데이터 μš”μ†Œκ°€ λ…Έλ“œλ‘œ κ΅¬μ„±λ˜κ³ , 각 λ…Έλ“œλŠ” 데이터와 λ‹€μŒ λ…Έλ“œλ₯Ό κ°€λ¦¬ν‚€λŠ” 포인터λ₯Ό ν¬ν•¨ν•˜λŠ” μžλ£Œκ΅¬μ‘°μž…λ‹ˆλ‹€.
    • νŠΉμ§• : 동적 크기 쑰절이 κ°€λŠ₯ν•˜λ©° μ‚½μž…κ³Ό μ‚­μ œκ°€ μš©μ΄ν•˜μ§€λ§Œ, 인덱슀λ₯Ό ν†΅ν•œ 접근은 배열보닀 λŠλ¦½λ‹ˆλ‹€.
    • μ’…λ₯˜ : 단일 μ—°κ²° 리슀트, 이쀑 μ—°κ²° 리슀트, μ›ν˜• μ—°κ²° 리슀트 λ“±.
  3. μŠ€νƒ(Stack)
    • μ •μ˜ : ν›„μž…μ„ μΆœ(LIFO, Last In First Out) λ°©μ‹μœΌλ‘œ λ™μž‘ν•˜λŠ” μžλ£Œκ΅¬μ‘°μž…λ‹ˆλ‹€.
    • νŠΉμ§• : 데이터 μ‚½μž…(push)κ³Ό μ‚­μ œ(pop)이 ν•œμͺ½ λμ—μ„œλ§Œ μ΄λ£¨μ–΄μ§‘λ‹ˆλ‹€.
    • μ‚¬μš© 사둀 : ν•¨μˆ˜ 호좜 μŠ€νƒ, μ—­μˆœ λ¬Έμžμ—΄ 처리 λ“±.
  4. 큐(Queue)
    • μ •μ˜ : μ„ μž…μ„ μΆœ(FIFO, First In First Out) λ°©μ‹μœΌλ‘œ λ™μž‘ν•˜λŠ” μžλ£Œκ΅¬μ‘°μž…λ‹ˆλ‹€.
    • νŠΉμ§• : λ°μ΄ν„°μ˜ μ‚½μž…(enqueue)은 ν•œμͺ½ 끝(후단)μ—μ„œ, μ‚­μ œ(dequeue)λŠ” λ°˜λŒ€μͺ½ 끝(전단)μ—μ„œ μ΄λ£¨μ–΄μ§‘λ‹ˆλ‹€.
    • μ’…λ₯˜ : μ›ν˜• 큐, μš°μ„ μˆœμœ„ 큐, 덱(Deque) λ“±.
    • μ‚¬μš© 사둀 : 운영 체제의 μž‘μ—… μŠ€μΌ€μ€„λ§, ν”„λ¦°ν„° λŒ€κΈ°μ—΄ λ“±.

μ„ ν˜• 자료ꡬ쑰의 νŠΉμ§• 및 μž₯단점.

  • νŠΉμ§•.
    • 순차적 접근이 κ°€λŠ₯ν•˜λ©°, 데이터λ₯Ό μ°¨λ‘€λŒ€λ‘œ μ²˜λ¦¬ν•  λ•Œ μœ λ¦¬ν•©λ‹ˆλ‹€.
    • λ©”λͺ¨λ¦¬μ—μ„œ μ—°μ†μ μœΌλ‘œ λ°°μΉ˜λ˜λ―€λ‘œ 인덱슀λ₯Ό 톡해 직접 μ ‘κ·Όν•  수 μžˆμŠ΅λ‹ˆλ‹€.(λ°°μ—΄μ˜ 경우)
  • μž₯점.
    • κ°„λ‹¨ν•˜κ³  κ΅¬ν˜„μ΄ μš©μ΄ν•©λ‹ˆλ‹€.
    • λ°μ΄ν„°μ˜ μ‚½μž…κ³Ό μ‚­μ œκ°€ νŠΉμ • 쑰건 ν•˜μ— 효율적일 수 μžˆμŠ΅λ‹ˆλ‹€(예: μŠ€νƒ, 큐)
  • 단점
    • 데이터 크기에 따라 λ©”λͺ¨λ¦¬ λ‚­λΉ„κ°€ λ°œμƒν•  수 μžˆμŠ΅λ‹ˆλ‹€(λ°°μ—΄μ˜ 경우).
    • νŠΉμ • μš”μ†Œ μ ‘κ·Όμ΄λ‚˜ μ‚½μž…/μ‚­μ œ μ‹œ μ„±λŠ₯이 μ €ν•˜λ  수 μžˆμŠ΅λ‹ˆλ‹€(μ—°κ²° 리슀트의 경우)

마무리.

μ„ ν˜• μžλ£Œκ΅¬μ‘°λŠ” 데이터가 순차적으둜 μ—°κ²°λ˜μ–΄ μžˆμ–΄ 순차적 μ²˜λ¦¬μ— μ ν•©ν•˜λ©°, ν”„λ‘œκ·Έλž¨μ˜ λ‹€μ–‘ν•œ λΆ€λΆ„μ—μ„œ μ‚¬μš©λ˜λŠ” 기초적인 μžλ£Œκ΅¬μ‘°μž…λ‹ˆλ‹€.


2️⃣ λΉ„μ„ ν˜• 자료ꡬ쑰(Non-linear Data Structure)

λΉ„μ„ ν˜• 자료ꡬ쑰(Non-linear Data Structure)λŠ” 데이터 μš”μ†Œλ“€μ΄ 계측적 λ˜λŠ” κ·Έλ¬Ό ν˜•νƒœλ‘œ λ°°μ—΄λœ ꡬ쑰λ₯Ό μ˜λ―Έν•©λ‹ˆλ‹€.

이 μžλ£Œκ΅¬μ‘°μ—μ„œλŠ” 데이터 μš”μ†Œλ“€μ΄ 순차적으둜 λ°°μ—΄λ˜μ§€ μ•Šκ³ , ν•˜λ‚˜μ˜ μš”μ†Œκ°€ μ—¬λŸ¬ μš”μ†Œλ“€κ³Ό 연결될 수 μžˆμŠ΅λ‹ˆλ‹€.

μ£Όμš” λΉ„μ„ ν˜• μžλ£Œκ΅¬μ‘°λ‘œλŠ” 트리(Tree)와 κ·Έλž˜ν”„(Graph)κ°€ μžˆμŠ΅λ‹ˆλ‹€.

μ£Όμš” λΉ„μ„ ν˜• 자료ꡬ쑰.

  1. 트리(Tree)
    • μ •μ˜ : λ…Έλ“œμ™€ κ·Έ λ…Έλ“œλ“€μ„ μ—°κ²°ν•˜λŠ” κ°„μ„ μœΌλ‘œ κ΅¬μ„±λœ 계측적 μžλ£Œκ΅¬μ‘°μž…λ‹ˆλ‹€. νŠΈλ¦¬λŠ” 루트 λ…Έλ“œμ—μ„œ μ‹œμž‘ν•˜μ—¬ μžμ‹ λ…Έλ“œλ‘œ λΆ„κΈ°ν•˜λ©°, 사이클이 μ—†μŠ΅λ‹ˆλ‹€.
    • νŠΉμ§• : νŠΈλ¦¬λŠ” 계측적 관계λ₯Ό λ‚˜νƒ€λ‚΄λ©°, 각 λ…Έλ“œλŠ” 0개 μ΄μƒμ˜ μžμ‹ λ…Έλ“œλ₯Ό κ°€μ§ˆ 수 μžˆμŠ΅λ‹ˆλ‹€.
    • μ’…λ₯˜ :
      • 이진 트리(Binary Tree) : 각 λ…Έλ“œκ°€ μ΅œλŒ€ 두 개의 μžμ‹ λ…Έλ“œλ₯Ό κ°€μ§€λŠ” νŠΈλ¦¬μž…λ‹ˆλ‹€.
      • 이진 탐색 트리(Binary Search Tree) : μ™Όμͺ½ μžμ‹μ€ λΆ€λͺ¨λ³΄λ‹€ μž‘κ³ , 였λ₯Έμͺ½ μžμ‹μ€ λΆ€λͺ¨λ³΄λ‹€ 큰 값을 κ°€μ§€λŠ” 이진 νŠΈλ¦¬μž…λ‹ˆλ‹€.
      • κ· ν˜• 이진 트리(Balanced Binary Tree) : AVL 트리, λ ˆλ“œ-λΈ”λž™ 트리 λ“±κ³Ό 같이 높이가 κ· ν˜•μ„ 이루도둝 μœ μ§€λ˜λŠ” νŠΈλ¦¬μž…λ‹ˆλ‹€.
      • νž™(Heap) : μ™„μ „ 이진 트리의 μΌμ’…μœΌλ‘œ, μ΅œλŒ€ νž™κ³Ό μ΅œμ†Œ νž™μ΄ μžˆμŠ΅λ‹ˆλ‹€.
      • 트라이(Trie) : λ¬Έμžμ—΄μ„ μ €μž₯ν•˜κ³  λΉ λ₯΄κ²Œ κ²€μƒ‰ν•˜κΈ° μœ„ν•΄ μ‚¬μš©λ˜λŠ” νŠΈλ¦¬μž…λ‹ˆλ‹€.
  2. κ·Έλž˜ν”„(Graph)
    • μ •μ˜ : 정점(Vertex)λ“€κ³Ό 이 정점듀을 μ—°κ²°ν•˜λŠ” κ°„μ„ (Edge)λ“€λ‘œ κ΅¬μ„±λœ μžλ£Œκ΅¬μ‘°μž…λ‹ˆλ‹€.
    • νŠΉμ§• : κ·Έλž˜ν”„λŠ” λ°©ν–₯ κ·Έλž˜ν”„(Directed Graph)와 무방ν–₯ κ·Έλž˜ν”„(Undirceted Graph)둜 λ‚˜λˆŒ 수 있으며, 사이클이 μ‘΄μž¬ν•  수 μžˆμŠ΅λ‹ˆλ‹€.
    • μ’…λ₯˜ :
      • λ°©ν–₯ κ·Έλž˜ν”„(Directed Graph) : 간선에 λ°©ν–₯성이 μžˆλŠ” κ·Έλž˜ν”„μž…λ‹ˆλ‹€.
      • 무방ν–₯ κ·Έλž˜ν”„(Undirected Graph) : 간선에 λ°©ν–₯성이 μ—†λŠ” κ·Έλž˜ν”„μž…λ‹ˆλ‹€.
      • κ°€μ€‘μΉ˜ κ·Έλž˜ν”„(Weighted Graph) : 간선에 κ°€μ€‘μΉ˜κ°€ λΆ€μ—¬λœ κ·Έλž˜ν”„μž…λ‹ˆλ‹€.
      • λΉ„κ°€μ€‘μΉ˜ κ·Έλž˜ν”„(Unweighted Graph) : 간선에 κ°€μ€‘μΉ˜κ°€ μ—†λŠ” κ·Έλž˜ν”„μž…λ‹ˆλ‹€.

λΉ„μ„ ν˜• 자료ꡬ쑰의 νŠΉμ§• 및 μž₯단점.

  • νŠΉμ§• :
    • 계측적 λ˜λŠ” λ„€νŠΈμ›Œν¬ ꡬ쑰λ₯Ό λ‚˜νƒœλ‚΄λŠ” 데 μ ν•©ν•©λ‹ˆλ‹€.
    • λ³΅μž‘ν•œ 관계λ₯Ό ν‘œν˜„ν•  수 있으며, 데이터 μš”μ†Œ κ°„μ˜ λ‹€λŒ€λ‹€ 관계λ₯Ό μ²˜λ¦¬ν•  수 μžˆμŠ΅λ‹ˆλ‹€.
  • μž₯점 :
    • λ°μ΄ν„°μ˜ 계측적 ꡬ쑰λ₯Ό μ‰½κ²Œ ν‘œν˜„ν•  수 μžˆμŠ΅λ‹ˆλ‹€(트리).
    • λ³΅μž‘ν•œ μ—°κ²° 관계λ₯Ό 효과적으둜 λͺ¨λΈλ§ν•  수 μžˆμŠ΅λ‹ˆλ‹€(κ·Έλž˜ν”„).
    • νŠΉμ • μœ ν˜•μ˜ 탐색, μ •λ ¬, 데이터 μ••μΆ•, λ„€νŠΈμ›Œν¬ λΌμš°νŒ… 등에 μœ μš©ν•©λ‹ˆλ‹€.
  • 단점 :
    • κ΅¬ν˜„κ³Ό 관리가 μ„ ν˜• μžλ£Œκ΅¬μ‘°λ³΄λ‹€ λ³΅μž‘ν•  수 μžˆμŠ΅λ‹ˆλ‹€.
    • νŠΉμ • μž‘μ—…(예: 트리의 κ· ν˜• μœ μ§€, κ·Έλž˜ν”„ 탐색 λ“±)μ—μ„œ 좔가적인 μ•Œκ³ λ¦¬μ¦˜μ΄ ν•„μš”ν•©λ‹ˆλ‹€.

마무리.

λΉ„μ„ ν˜• μžλ£Œκ΅¬μ‘°λŠ” 데이터가 λ‹¨μˆœνžˆ 순차적으둜 λ°°μ—΄λ˜μ§€ μ•Šκ³ , λ³΅μž‘ν•œ 관계λ₯Ό λ‚˜νƒ€λ‚΄λŠ” κ²½μš°μ— μ‚¬μš©λ©λ‹ˆλ‹€.

예λ₯Ό λ“€μ–΄, 파일 μ‹œμŠ€ν…œμ˜ 디렉터리 ꡬ쑰, λ°μ΄ν„°λ² μ΄μŠ€ 인덱슀, μ†Œμ…œ λ„€νŠΈμ›Œν¬μ˜ μ‚¬μš©μž 관계 등이 λΉ„μ„ ν˜• 자료ꡬ쑰λ₯Ό ν™œμš©ν•˜λŠ” μ‚¬λ‘€μž…λ‹ˆλ‹€.


2️⃣ 자료ꡬ쑰의 κ΅¬ν˜„.

1️⃣ 좔상 μžλ£Œν˜•(Abstract Data Type, ADT)

μžλ°” ν”„λ‘œκ·Έλž˜λ°μ—μ„œμ˜ 좔상 μžλ£Œν˜•(Abstract Data Type, ADT)은 λ°μ΄ν„°μ˜ 논리적 ꡬ쑰와 이λ₯Ό μ‘°μž‘ν•˜λŠ” 연산듀을 λͺ…ν™•ν•˜κ²Œ μ •μ˜ν•œ κ°œλ…μž…λ‹ˆλ‹€.

ADTλŠ” κ΅¬ν˜„ μ„ΈλΆ€ 사항을 숨기고, 데이터와 μ—°μ‚°μ˜ μΈν„°νŽ˜μ΄μŠ€λ₯Ό 톡해 μ‚¬μš©μžμ—κ²Œ 좔상적인 μˆ˜μ€€μ—μ„œ 데이터 μ‘°μž‘μ„ μ œκ³΅ν•©λ‹ˆλ‹€.

즉, ADTλŠ” 데이터가 μ–΄λ–»κ²Œ μ €μž₯되고 κ΅¬ν˜„λ˜λŠ”μ§€μ— λŒ€ν•œ μ •λ³΄λŠ” 감좔고, 데이터와 μƒν˜Έμž‘μš©ν•˜λŠ” λ°©λ²•λ§Œμ„ μ •μ˜ν•©λ‹ˆλ‹€.

μ£Όμš” κ°œλ…

  1. 좔상화(Abstraction)
    • ADTλŠ” 데이터λ₯Ό μΆ”μƒν™”ν•˜μ—¬ λ°μ΄ν„°μ˜ μ‹€μ œ κ΅¬ν˜„κ³Ό λ…λ¦½μ μœΌλ‘œ μ‚¬μš©λ  수 μžˆλ„λ‘ ν•©λ‹ˆλ‹€.
    • μ‚¬μš©μžλŠ” λ°μ΄ν„°μ˜ μ €μž₯ λ°©μ‹μ΄λ‚˜ μ—°μ‚°μ˜ κ΅¬ν˜„ 방법을 μ•Œ ν•„μš” 없이, ADTκ°€ μ œκ³΅ν•˜λŠ” μΈν„°νŽ˜μ΄μŠ€λ₯Ό 톡해 데이터λ₯Ό μ‘°μž‘ν•  수 μžˆμŠ΅λ‹ˆλ‹€.
  2. μΈν„°νŽ˜μ΄μŠ€(Interface)
    • ADTλŠ” 데이터 νƒ€μž…κ³Ό 이λ₯Ό λ‹€λ£¨λŠ” 연산듀을 μΈν„°νŽ˜μ΄μŠ€λ₯Ό 톡해 μ •μ˜ν•©λ‹ˆλ‹€.
    • μžλ°”μ—μ„œλŠ” μΈν„°νŽ˜μ΄μŠ€(Interface) ν‚€μ›Œλ“œλ₯Ό μ‚¬μš©ν•˜μ—¬ ADT의 연산을 μ •μ˜ν•  수 μžˆμŠ΅λ‹ˆλ‹€.
  3. μΊ‘μŠν™”(Encapsulation)
    • ADTλŠ” 데이터와 연산을 ν•˜λ‚˜μ˜ λ‹¨μœ„λ‘œ λ¬Άμ–΄ μΊ‘μŠν™”ν•©λ‹ˆλ‹€.
    • 데이터λ₯Ό 직접 μ ‘κ·Όν•˜μ§€ μ•Šκ³ , μ •μ˜λœ 연산을 ν†΅ν•΄μ„œλ§Œ μ ‘κ·Όν•  수 μžˆλ„λ‘ ν•˜μ—¬ 데이터 무결성을 보μž₯ν•©λ‹ˆλ‹€.

μžλ°”μ—μ„œμ˜ ADT μ˜ˆμ‹œ

λ‹€μŒμ€ μžλ°”μ—μ„œ μŠ€νƒ(Stack) ADTλ₯Ό μ •μ˜ν•˜κ³  κ΅¬ν˜„ν•˜λŠ” μ˜ˆμ‹œμž…λ‹ˆλ‹€.

μŠ€νƒ μΈν„°νŽ˜μ΄μŠ€ μ •μ˜

public interface Stack<T> {
    void push(T item); // μŠ€νƒμ— μ•„μ΄ν…œμ„ μΆ”κ°€
    T pop(); // μŠ€νƒμ—μ„œ μ•„μ΄ν…œμ„ μ œκ±°ν•˜κ³  λ°˜ν™˜
    T peek(); // μŠ€νƒμ˜ 맨 μœ„ μ•„μ΄ν…œμ„ λ°˜ν™˜(μ œκ±°ν•˜μ§€ μ•ŠμŒ)
    boolean isEmpty(); // μŠ€νƒμ΄ λΉ„μ–΄ μžˆλŠ”μ§€ 확인
    int size(); // μŠ€νƒμ˜ 크기 λ°˜ν™˜
}

μŠ€νƒ κ΅¬ν˜„

import java.util.ArrayList;
import java.util.List;

public class ArrayListStack<T> implements Stack<T> {
    private List<T> list = new ArrayList<>();
    
    @Override
    public void push(T item) {
        list.add(item);
    }
    
    @Override
    public T pop() {
        if (isEmpty()) {
            throw new RuntimException("Stack is empty");
        }
        return list.remove(list.size() - 1);
    }
    
    @Override
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return list.get(list.size() - 1);
    }
    
    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }
    
    @Override
    public int size() {
        return list.size();
    }
}

μ„€λͺ…

  • β€˜Stack<T>β€˜ μΈν„°νŽ˜μ΄μŠ€λŠ” μŠ€νƒ ADT의 연산을 μ •μ˜ν•©λ‹ˆλ‹€. 이 μΈν„°νŽ˜μ΄μŠ€λŠ” β€˜push’, β€˜pop’, β€˜peek’, β€˜isEmpty’, β€˜size’ λ©”μ„œλ“œλ₯Ό ν¬ν•¨ν•©λ‹ˆλ‹€.

  • β€˜ArrayListStack<T>β€˜ ν΄λž˜μŠ€λŠ” β€˜Stack<T>β€˜ μΈν„°νŽ˜μ΄μŠ€λ₯Ό κ΅¬ν˜„ν•©λ‹ˆλ‹€. 이 ν΄λž˜μŠ€λŠ” β€˜ArrayList’ λ₯Ό λ‚΄λΆ€ 데이터 ꡬ쑰둜 μ‚¬μš©ν•˜μ—¬ μŠ€νƒ 연산을 κ΅¬ν˜„ν•©λ‹ˆλ‹€.
  • β€˜push’ λ©”μ„œλ“œλŠ” μŠ€νƒμ— μ•„μ΄ν…œμ„ μΆ”κ°€ν•©λ‹ˆλ‹€.
  • β€˜pop’ λ©”μ„œλ“œλŠ” μŠ€νƒμ—μ„œ 맨 μœ„μ˜ μ•„μ΄ν…œμ„ μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.
  • β€˜peek’ λ©”μ„œλ“œλŠ” μŠ€νƒμ˜ 맨 μœ„ μ•„μ΄ν…œμ„ μ œκ±°ν•˜μ§€ μ•Šκ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.
  • β€˜isEmpty’ λ©”μ„œλ“œλŠ” μŠ€νƒμ΄ λΉ„μ–΄ μžˆλŠ”μ§€ ν™•μΈν•©λ‹ˆλ‹€.
  • β€˜size’ λ©”μ„œλ“œλŠ” μŠ€νƒμ˜ 크기λ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.

이 μ˜ˆμ‹œμ—μ„œ β€˜Stack<T>β€˜ μΈν„°νŽ˜μ΄μŠ€λŠ” μŠ€νƒ ADTλ₯Ό μ •μ˜ν•˜κ³ , β€˜ArrayListStack<T>β€˜ ν΄λž˜μŠ€λŠ” 이 ADTλ₯Ό κ΅¬ν˜„ν•œ κ²ƒμž…λ‹ˆλ‹€.

μ‚¬μš©μžλŠ” β€˜ArrayListStack’ 의 λ‚΄λΆ€ κ΅¬ν˜„μ„ μ•Œ ν•„μš” 없이 β€˜Stack’ μΈν„°νŽ˜μ΄μŠ€λ₯Ό 톡해 μŠ€νƒ 연산을 μ‚¬μš©ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

μ΄λŠ” ADT의 μ£Όμš” μž₯점 쀑 ν•˜λ‚˜μΈ κ΅¬ν˜„μ˜ 독립성을 잘 λ³΄μ—¬μ€λ‹ˆλ‹€.