cs 지식/자료구조 및 알고리즘

#1. 자료구조의 기초

subindev 2025. 1. 13. 17:13

🎈 1. 자료구조의 기초

자료구조란 무엇인가?

 

 

자료구조(Data Structure)는 개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법을 말합니다. 각각의 자료구조에는 장단점이 있으므로 어떤 자료구조가 최선일지는 해결하고자 하는 문제의 종류와 어떤 부분을 우선적으로 최적화할지에 따라 달라질 수 있습니다. 그러므로 다양한 자료구조의 장단점을 살펴보며 애플리케이션을 만들 때 어떤 자료구조를 사용하는 것이 최선일지 판단해야 합니다. 

 

프로그래밍이란 결국 알고리즘을 작성하고, 그에 맞는 자료구조를 선택하는 것이므로 자료구조를 충분히 이해하지 못한다면 결코 좋은 개발자가 될 수 없습니다. 그래서 파스칼을 개발한 스위스의 컴퓨터 과학자 니클라우스 비르트는 ‘알고리즘 + 자료구조 = 프로그램’이라는 유명한 말을 남기기도 했습니다.

 

 

🧩 2. 자료구조의 분류

🎭 단순 vs 복합 자료구조

  • 단순 자료구조(Primitive Data Structures): 기본적인 데이터 타입으로, 프로그래밍 언어에서 제공하는 형태입니다. 예를 들어, int, float, char 같은 원시 데이터 타입들이 여기에 속합니다.
  • 복합 자료구조(Non-Primitive Data Structures): 단순 자료구조들을 조합하거나 연관시켜서 보다 복잡한 형태로 데이터를 저장하는 자료구조입니다. 배열, 리스트, 스택, 큐, 트리, 그래프 등이 이에 해당합니다.

자료구조는 또한 데이터를 어떻게 배치하고 처리할지에 대한 "구조"를 정의합니다. 예를 들어, 배열은 데이터를 순차적으로 저장하는 구조이고, 링크드 리스트는 데이터를 연결된 노드 형식으로 저장하는 구조입니다. 각 자료구조는 특정한 데이터 처리 요구를 만족하도록 설계되며, 효율성을 고려하여 선택됩니다.

 

🎨 추상 데이터 타입(Abstract Data Type, ADT)

추상 데이터 타입(ADT)은 자료구조를 추상화하여 정의하는 개념입니다. ADT는 데이터와 이 데이터를 처리할 수 있는 연산을 정의하는데, 구체적인 구현은 언어에 따라 달라질 수 있습니다. 즉, ADT는 특정 자료구조가 제공해야 하는 기능들을 개념적으로 정의하는 것으로, 자료구조는 그 정의된 기능을 실제로 구현하는 방법입니다.

  • 추상화: ADT는 그 자체로 구체적인 자료구조가 아니며, 단지 데이터와 그 데이터에 대해 수행할 수 있는 연산을 정의한 "청사진"입니다. 예를 들어, 리스트라는 ADT는 데이터를 삽입하고 삭제하는 연산을 제공하지만, 이 리스트가 배열로 구현될 수도 있고, 연결 리스트로 구현될 수도 있습니다.
  • 연산: ADT는 해당 데이터가 지원해야 하는 연산들을 정의합니다. 예를 들어, **리스트(List)**라는 ADT는 삽입(Insert), 삭제(Remove), 검색(Find) 등의 연산을 지원해야 하며, 그 구현 방식은 달라질 수 있습니다. 예를 들어, 배열을 이용한 리스트 구현에서는 배열의 인덱스를 사용하여 데이터를 관리하지만, 연결 리스트를 이용한 구현에서는 포인터를 사용하여 데이터를 관리합니다.

추상 데이터 타입의 예시

1. 스택(Stack)

  • 스택은 후입선출(LIFO, Last-In-First-Out) 방식으로 데이터를 처리하는 ADT입니다.
  • 스택에는 주로 push(삽입), pop(삭제), peek(가장 위의 원소 확인) 등의 연산이 정의됩니다.
  • 구체적인 구현으로는 배열이나 연결 리스트를 사용할 수 있습니다. 스택의 핵심은 "마지막에 들어온 데이터가 먼저 나간다"는 특성을 유지하는 것입니다.

2. 큐(Queue)

  • 큐는 선입선출(FIFO, First-In-First-Out) 방식으로 데이터를 처리하는 ADT입니다.
  • 큐에는 enqueue(삽입), dequeue(삭제), front(앞의 원소 확인) 등의 연산이 정의됩니다.
  • 큐는 배열이나 연결 리스트로 구현할 수 있으며, 순차적으로 데이터가 처리되어야 하는 문제에서 유용합니다.

3. 리스트(List)

  • 리스트는 데이터를 순차적으로 저장하는 자료구조로, 삽입, 삭제, 탐색 등의 연산이 가능합니다.
  • 리스트의 구체적인 구현은 배열이나 연결 리스트로 할 수 있으며, 리스트의 크기나 삽입/삭제의 효율성에 따라 선택이 달라집니다.

4. 트리(Tree)

  • 트리는 데이터를 계층적으로 저장하는 자료구조로, 부모와 자식 관계를 정의합니다.
  • 이진 트리, 이진 탐색 트리, AVL 트리 등 여러 형태로 구현할 수 있으며, 각 트리는 효율적인 탐색이나 삽입/삭제 연산을 위해 설계됩니다.
  •  

자료구조와 추상 데이터 타입의 관계

  • 자료구조는 데이터를 저장하고 처리하는 구체적인 방식(구현)을 뜻합니다. 자료구조는 ADT를 구현하는 방법 중 하나입니다.
  • **추상 데이터 타입(ADT)**은 데이터를 처리하는 방법을 정의하는 개념적이고 이론적인 청사진입니다. ADT는 자료구조가 반드시 구현해야 할 기능을 명세하는 것에 불과합니다.

예를 들어, 리스트를 구현한다고 할 때, 리스트라는 ADT는 "데이터를 순차적으로 삽입하고, 특정 데이터를 찾아낼 수 있는 기능"을 요구합니다. 그 리스트를 구현할 때, 배열을 이용할 수도 있고, 연결 리스트를 사용할 수도 있습니다. 즉, 배열이나 연결 리스트는 ADT를 구현하는 두 가지 방법일 뿐입니다. ADT는 이 두 가지 자료구조를 추상화하고, 그 동작만을 정의하는 것입니다.

 

 

🟡 3. 자료구조의 중요성

  • 효율성: 자료구조의 선택은 프로그램의 성능에 큰 영향을 미칩니다. 예를 들어, 데이터 삽입/삭제가 빈번한 경우 연결 리스트가 적합할 수 있으며, 데이터 검색이 중요한 경우 해시 테이블이 적합할 수 있습니다.
  • 문제 해결 능력 향상: 자료구조를 잘 이해하면 문제를 더 효율적으로 해결할 수 있는 능력이 생깁니다. 예를 들어, 스택을 이용한 후위 표기법 계산, 큐를 이용한 너비 우선 탐색, 트리를 이용한 데이터 탐색 등의 문제를 빠르고 정확하게 해결할 수 있습니다.
  • 자료구조와 추상 데이터 타입의 관계를 잘 이해하고, 각 자료구조가 해결하려는 문제를 명확히 파악하는 것이 중요합니다. 이를 통해 문제의 특성에 맞는 자료구조를 선택하고, 최적화된 알고리즘을 설계할 수 있습니다.

 

출처 : [한빛출판네트워크] 채널.H - https://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS2832062046