자료 구조 1 - 자료 구조란? ADT? 데이터 추상화?

자료 구조 포스트 보러가기

0. Prerequisite

이번 포스트에서는 자료구조란 무엇인지를 알아보고 추상 데이터 타입(Abstract data type, ADT)과 그 예시, 데이터 추상화란 무엇인지에 대해서 다룰 예정이다.

다루는 주제의 특성상 각 자료구조의 알고리즘을 기술할 필요가 있기 때문에 코드에 대한 이해가 필수적이다.

수도(pseudo)코드를 기준으로 기술하겠지만 필요에 따라 파이썬, C++, JAVA등의 다양한 언어를 사용해서 기술할 예정이다.

1. Data structures(자료 구조)

자료 구조란 데이터를 조직하고 저장하고 연산을 수행하는 하나의 수단이다.

여기서 말하는 연산을 수행한다는 것은 저장된 데이터에 접근하는 것, 저장된 데이터를 업데이트 하는 것, 특정 데이터를 찾는 것, 새로운 데이터를 추가하는 것, 기존의 데이터를 삭제하는 것 등을 말한다.

자료 구조의 예시는 아래와 같다.

---

• Record(레코드)
  • 레코드는 필드라고 불리는 서브아이템들을 저장하는 자료 구조이다. C언어에서의 구조체, 데이터베이스에서의 행 등이 그 예시이다.
  • 위에서 C언어의 구조체를 예시로 들었으니 구조체로 설명해보겠다.

    struct student{
      int student_id;
      int grade;
      char* department;
    }
    

  • 위의 예시에서 student를 레코드라고 부르고 student_id, grade, department를 필드라고 부른다.

---

• Array(배열)
  • 배열은 위치 인덱스를 갖고 직접 접근이 가능한 데이터들을 저장하는 자료 구조(리스트)이다.
    위치 인덱스로 각각의 데이터에 접근이 가능한 구조이기 때문에 대부분의 프로그래밍 언어는 각각의 데이터의 주소를 순차적으로 할당하는 방식으로 구현하고 있다.

    struct student student_array[3] = { \
      {1, 4.0, "computer science"}, \
      {2, 4.1, "biology"}, \
      {2, 4.3, "economics"}
      };
    

  • 위의 예시를 보면 student_array에 세 개의 student를 저장하고 있다. 각각의 데이터는 0번부터 시작해서 1, 2번의 인덱스를 부여받게 되어 데이터를 인덱스로 바로 접근할 수 있게 한다.

List(리스트)는 순서를 가지는(선형) 자료구조를 통칭하여 말한다. 따라서 배열은 리스트의 한 종류라고 말할 수 있다.

---

이 아래부터는 다룰 내용이 많아 따로 포스팅 할 때 자세히 다루도록 하겠다.

• Linked List(연결 리스트)
  • 연결 리스트는 노드라고 불리우는 데이터들을 저장하는 자료 구조(리스트)이다.
  • 여기서 노드란 데이터와 더불어 다음 노드로의 포인터 정보를 갖고 있는 객체를 말한다.
• Binary Tree(이진 트리)
  • 이진 트리는 트리의 일종으로 왼쪽 자식, 오른쪽 자식 총 두 개의 자식까지만 가질 수 있는 트리를 말한다. (아직 트리란 무엇인지 다루지 않았기 때문에 이런게 있구나 하고 넘어가면 되겠다.)
• Hash table(해시 테이블)
  • 해시 테이블은 각각의 데이터를 특정 위치(값)에 매핑해놓는 방식으로 데이터를 저장하는 자료 구조(테이블)을 말한다.

그 밖에 힙(heap), 그래프(graph)등의 자료 구조가 있지만 이는 추후 포스트에서 자세히 다루도록 하겠다.

이와 같이 자료 구조는 매우 다양하다. 따라서 우리는 목적에 맞게 최적화된 자료 구조를 선택해야만 한다.

그 목적에 맞는 자료 구조를 선택하는 기준 중에 하나가 바로 알고리즘의 효율성이다. 데이터를 단순히 저장만 해놓는 것이 아니고 각종 연산을 필요로 하기 때문에, 이 알고리즘의 효율성을 바탕으로 자료 구조를 선택함이 옳다고 할 수 있다.

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

추상 데이터 타입 다른 말로 추상 자료형이라고도 한다.

말 그대로 자료형인데 그 형식이 추상화 되어 있어서 내부 구현은 감춰져 있다.

사용자가 알 수 있는 것은 “데이터를 맨 뒤에 삽입하라”와 같은 사전에 사용자에게 제공되는 연산들 뿐이다.

따라서 사용자는 내부 구현 방식을 알 필요도 없이 자료형을 사용할 수 있게 된다.

예를 들어, 리스트는 순서가 있는 데이터를 저장하는 대표적인 ADT이다. 이때 리스트에는 데이터 삽입, 삭제, 검색 등의 연산을 제공한다.

그리고 보통 리스트는 배열이나 연결 리스트같은 자료구조로 구현 되어 있다.

추상 자료형의 예시는 아래와 같다.

• List(리스트)
  • 순서가 있는 데이터를 저장하는 ADT
  • 보통 배열, 연결 리스트로 구현 되어 있다.
• Dynamic array(동적 배열)
  • 기존의 배열과는 달리 크기가 변하는 배열형 ADT
  • 보통 배열로 구현 되어 있다.
• Stack(스택)
  • Top이라고 불리는 오직 한 곳에서만 데이터의 삽입 삭제가 가능한 ADT
  • 보통 연결 리스트로 구현 되어 있다.
• Queue(큐)
  • 데이터의 삭제는 리스트의 앞(front), 데이터의 추가는 리스트의 뒤에서만 가능한 ADT
  • 보통 연결 리스트로 구현 되어 있다.
• Deque(덱)
  • 앞 뒤 모두에서 데이터의 추가와 삭제가 가능한 ADT
  • 보통 연결 리스트로 구현 되어 있다.
• Bag(백)
  • 중복을 허락하여 데이터를 저장하고 데이터에 순서가 필요 없는 ADT
  • 보통 배열, 연결 리스트로 구현 되어 있다.
• Set(집합)
  • 중복을 허락하지 않고 데이터에 순서가 필요 없는 데이터를 저장하는 ADT
  • 보통 이진 탐색 트리, 해시 테이블로 구현 되어 있다.
• Priority queue(우선순위 큐)
  • 큐의 일종으로 각 데이터는 우선순위가 존재하고 낮은 우선순위의 데이터보다 높은 우선순위의 데이터가 front에 있는 ADT
  • 보통 힙(heap)으로 구현 되어 있다.
• Dictionary(딕셔너리, 또는 Map)
  • (키, 값)이 한 쌍이 되는 방식으로 데이터를 저장하는 ADT
  • 보통 이진 탐색 트리, 해시 테이블로 구현 되어 있다.

이 밖에도 다양한 ADT가 존재하며 상황에 맞는 ADT를 사용하는 것이 권장된다.

보통 이 ADT들은 프로그래밍 언어의 표준 라이브러리에 모두 저장 되어 있다.

Python에서는 python standard library,
C++에서는 standard template library(STL),
Java에서는 java collection framework(JCF)에 저장 되어 있다.

3. Data Abstraction(데이터 추상화)

데이터 추상화란 자료형의 논리적 속성과 그 구현을 분리해놓는 것을 말한다.

클라이언트(일반적인 프로그래머)가 사용하는 자료형은 위에서 분리된 논리적 속성인 것이다.

데이터 추상화를 다른말로 “데이터 캡슐화”라고도 한다.

따라서 구현의 방식이 어떻게 되든 제공되는 논리적 속성에는 변함이 없다.

하나의 예를 들어보자면, 바로 C언어의 int형이 되겠다.

int형을 보면 단순히 정수를 저장하는 자료형 정도로만 인식하고 있겠지만(물론 이게 맞긴 하지만, 설명을 위해 이렇게 표현했다.) 그 내부에는 아주 복잡한 구현들이 존재한다.

가령 int형의 최댓값, 최솟값이 사전에 정의 되어 있고 +, -, *, / 등의 다양한 연산자들의 그 결과가 어떻게 계산되는지에 대해서도 사전에 구현 되어 있는 것이다.

여기에서 나아가 단순한 자료형 외에 여러 자료 구조를 추상화 한 것이 ADT라고 할 수 있겠다.

ADT의 목적은 다양한 자료 구조를 기본 자료형 처럼 다룰 수 있도록 기능을 제공하는 것이라고 볼 수 있다.

후기) 다시 공부하는 마음가짐으로 자료 구조에 대해서 포스팅을 시작했는데요… 처음 공부할 때가 아니기 때문에 어느정도까지 설명해야하는지 감을 잡기가 참 어렵네요… 자료 구조 포스팅을 하는 간간히 알고리즘 포스팅도 진행할 예정인데, 포스트를 단독으로 이해할 수 있도록 설명을 해보겠습니다. 읽어주셔서 감사합니다.

오타 혹은 잘못된 정보가 있다면 댓글 이메일 등등으로 알려주시면 감사하겠습니다. (꾸벅)