[Data Structures] 자료구조의 종류 (feat. ADT, Concrete Data Structure)

TL;DR

자료구조란
컴퓨터가 데이터를 효율적으로 저장, 탐색, 처리, 관리하기 위해 설계된
데이터 쌓는 구조를 말한다.

우리가 컴퓨터 공학에서 흔히 배우는 자료구조는

지난 세월동안
프로그래밍 업계에서 문제 해결을 위해 개발한
'데이터 활용 방법에 따른 주요한 설계도'라고 볼 수 있다.

우리는

'어떤 문제 때문에
데이터를 어떻게 연산할 필요가 생겼는지'

'그런 방식의 연산이 효율적으로 수행되기 위해
데이터는 어떻게 구조화되어야 하는지'

에 방점을 두고 학습하는 것이 중요하다.

추후 유사한 문제와 맞닥뜨렸을 때
효율적인 접근방식을 생각해내는 힘을 길러주기 때문이다.

 

우리가 살림을 위해
집에 각종 물건을 배치한 모습을 떠올려보자.

주방의 조리도구, 식기도구와 식자재부터 시작해서
거실에 있는 티비, 오디오, 소파, 장식장,
각 방에 있는 겉옷, 속옷, 장신구,
화장실에 있는 수건, 세정제, 청소 도구까지

각 물건이 쓰이는 용도와 양에 따라
수납하는 방식도 달라지고,
수납하는 공간도 달라진다.

컴퓨터 공학에서 말하는 자료구조를
살림에 빗대어 이해해보자면,

물건은 자료(data)이고,
물건을 수납하는 방식과 공간에 대한 고민의 결과가
자료구조(data structure)라고 볼 수 있다.

---

조금더 나아가 생각해보자.

우리가 집에서 살림을 하기 위해
처리하는 작업의 종류는 무척 다양하지만,
<요리>, <빨래>, <청소> 등으로 자주 실행되는 작업을 구분할 수 있다.

또,
각 작업을 완료하기 위해 거쳐야하는
작은 업무들을 정의할 수 있다.

ex) 빨래: 빨랫감을 모은다 -> 세탁기에 빨랫감과 세제와 유연제를 넣는다 -> 세탁이 되는 동안 건조대에서 완전히 마른 빨랫감을 걷는다 -> 세탁기 동작이 끝나면, 비어있는 건조대에 젖은 빨랫감을 널어 말린다.

또,
그 작은 업무들을 수행하는 데 쓰이는 물건들을
어디에 어떻게 수납해두는 것이
업무 수행의 효율성을 높이는지 고민할 수 있다.

ex) 빨래 바구니는 밝은 옷과 어두운 옷을 나누어 담기 위해 두개로 분리하고, 세탁기의 용량에 따라 그 크기를 결정한다. 세제와 유연제는 세탁기 옆에 손이 잘 닿는 곳에 하나씩 비치한다.

---

컴퓨터 과학의 자료구조도
이와 같은 컨셉으로 이해할 수 있다.

컴퓨터가 인간의 요청을 처리하기 위해
수행해야 할 작업은 엄청나게 많지만,

자주 처리하는 정형화된 작업들이 있다.

또
정형화된 작업들을 수행하는 데 필요한 데이터들을
효율적으로 저장하고 관리하는 방법이 있다.

여기서 정형화된 작업들은
다음과 같은 것이 있다.

- 데이터를 순차적으로 처리 하는 일
- 대량의 데이터에서 특정 항목을 빠르게 검색하는 일
- 가장 최근의 데이터를 제일 먼저 처리하는 일
- 여러가지 작업을 그 우선순위에 따라 처리하는 일
- 데이터 간의 관계가 복잡할 때 그 것을 분석하는 일

 

이때,
정형화된 각 작업을 완료하기 위해 거치게 되는 작은 업무들 중
'데이터를 어떻게 다룰 것인가'
곧, 데이터 연산의 방식을 정의한 자료구조 내의 개념이
추상 자료형 (ADT - Abstract Data Type)이다.

그리고,
이 데이터 연산의 방식을 구현하기 위해
'데이터를 어디에 어떻게 얼마나 저장할 것인가'
곧, 데이터의 구체적인 조직과 저장방식을 정의한 자료구조 내의 개념이
물리적 자료구조 (Concrete Data Structure)이다.

즉,
1. 해결해야 할 Task가 주어졌을 때 (ex.빨래)
2. Task 수행에 필요한 데이터 연산의 방식을 결정하고 (ex.빨랫감 담기, 세제 꺼내기)
3. 연산을 효율적으로 수행할 수 있는 데이터 저장 및 처리의 실체적 구조 (ex. 세탁실의 빨래 바구니, 세제 선반)를 선택하는 것이

자료구조의 본질이다.

---

빨래에서 벗어나,
인간이 컴퓨터에게 요청한 Task로 예를들어 보겠다.

1. Task: 인간이 크롬 웹 브라우저에서 '뒤로가기' 버튼을 눌러, 가장 최근에 방문했던 페이지로 돌아가기를 요청한다.
2. Abastract Data Type: Task 수행을 위해 페이지 히스토리 데이터를 저장하는데, 특히 데이터를 꺼낼 땐 가장 최근 방문한 페이지를 먼저 꺼내오는 방식이 필요하다.
3. Concrete Data Structure: ADT가 정의한 데이터 다루는 방식을 가장 효율적으로 실현시키기 위해, 순서에 따라 저장하고 꺼낼 수 있는, 순서가 있는 데이터 저장소를 조직한다.

위의 '뒤로가기 Task' 사례에서 쓰이는 ADT가 바로 Stack이며,
Stack이 정의한 연산 방식을 구체적으로 실현하는 데이터 구조가
Array나 Linked List이다.

---

여기서 의문,
ADT가 정의한 데이터 연산 방식을 구현하기 위해
어떤 Concrete Data Structure가 가장 적합할지는
어떻게 판단하나?

세탁실이 좁고, 빨랫감의 양도 적고, 색상이 다양하지 않으면
빨래 바구니를 하나만 두는 게 효율적일 것이고

그 반대의 경우라면,
빨래 바구니를 몇가지로 구분해 비치하는 게 효율적일 것이다.

이처럼 Task를 수행하는 환경의 특성에 따라
Stack을 구현하는데 쓰이는 효율적인 실체적 데이터 구조는
Array가 될 수도 있고, Linked List가 될 수도 있다.

---

오랜세월동안
컴퓨터 공학의 세계에는
앞서 말한 정형화된 Task가 정리되었으며,

각 Task를 수행하는 과정에서
데이터를 가장 효율적으로 관리할 수 있는 방법론(Abstract Data Type, Concrete Data Structure)에 해당하는
몇가지 사례들이 도출되었다.

그것이 우리 프로그래머가
자료구조 책을 읽거나, 문제를 풀 때 나오는 항목들이다.

나는
다양한 종류의 Abstrack Data Type과 Concrete Data Structure를 이해하기 위해서는
그것이 쓰이는 목적인 Task를 함께 알고 있어야
추후 직접 활용시 도움이 될 거라고 생각하기에

이 Task, ADT, CDS를 함께 정리해보고자 한다.

---

Task	Abstract Data Type	Concrete Data Structure	Practical Example
- 함수 호출 - 실행 취소 기능 - 수식의 평가	<Stack> - 주요 규칙 : Last-In-First-Out - 주요 연산 push) 맨 위에 새 요소 추가 pop) 맨 위의 요소 제거 후 반환 top/peek) 맨 위 요소 반환 isEmpty) 스택이 비었는지 확인	<Array> - 데이터를 연속적으로 저장하여, 각 자리의 index로 데이터 순서를 확인 <Linked List> - 각 데이터(node)에 바로 다음 데이터의 위치 정보(pointer)를 함께 저장하여 데이터 순서를 확인	- 브라우저의 뒤로가기 기능
- 데이터의 순차적 처리 - 작업 대기열 관리 - 버퍼	<Queue> - 주요 규칙 : First-In-First-Out - 주요 연산 enqueue) 맨 끝에 새 요소 추가 dequeue) 맨 앞의 요소 제거 후 반환 front) 맨 앞의 요소 반환 isEmpty) 큐가 비었는지 확인	<Array> <Linked List> 위 내용과 같음	- 프린터 작업 대기열 - 고객 서비스 대기열
- 우선순위에 따른 데이터 처리	<Priority Queue> - 주요 규칙 : 대기하고 있는 일을 우선순위에 따라 처리하기 - 주요 연산: insert) 우선순위에 따른 새 요소 추가 extractMax/Min) 우선순위가 가장 높/낮은 요소 제거 후 반환 peek) 우선순위 제일 높은 요소 반환 isEmpty) 우선순위 큐가 비었는지 확인	<Heap> - 계층적 데이터 구조를 띄는 완전 이진 트리(Complete Binary Tree) 중에서도, 최대/최소 값에 대한 특정한 나열 규칙을 가진 구조 - Tree형태로 구조화된 틀에서, Root부터 가장 마지막 Leaf가 뻗어나갈때, 각 가지가 뻗어나가는 지점인 node에 우선순위 정보를 저장	- 운영체제의 작업 스케줄링 - 데이터 패킷 라우팅 - 응급실 환자 대기열
- 유일한 값의 저장	<Set> - 주요 규칙 : 중복을 허용하지 않는 유일한 데이터 집합을 관리하기 - 주요 연산 add) 이미 존재하는 요소는 추가하지 않음 contains) 특정 요소를 포함하는지 확인	<Hash Table> - 최종적으로는 데이터를 Array 구조에 저장하는 형태. 이를 위해 key를 정형화된 index로 변환하는 해시함수를 적용함. <Binary Search Tree> - 학습 후 추가 예정	- 멤버십 테스트 (중복ID) - 집합 연산
- key를 통해 데이터에 빠르게 접근	<Map/Dictionary> - 주요 규칙 : {key:value} 쌍의 데이터를 저장하고 관리하기 - 주요 연산 put) key, value를 추가하되, 같은 key의 경우 value를 업데이트 get) 주어진 key에 해당하는 value를 검색 hasKey) 특정 key를 포함하는지 확인	<Hash Table> - 위와 같음 <Adelson-Velsky and Landis Tree> - 학습 후 추가 예정	- JSON - Python의 Dictionary type
- 복잡한 관계 및 네트워크 표현	<Graph> - 주요 규칙 : Node와 Edge로 데이터의 관계를 표현하기 - 주요 연산 addVertext) 새로운 노드 추가 addEdge) 두 노두 연결 엣지 추가 getAdjacentNodes) 특정 노드에 인접한 노드들을 반환 isConnected) 두 노드의 연결 여부 확인	<Adjacency List> - 학습 후 추가 예정 <Adjacency Matrix> - 학습 후 추가 예정	- 소셜 네트워크 - 지도 상의 경로 찾기

 

---

여기까지,

컴퓨터 공학에서 말하는 자료구조를
내 머릿속에 구조화하기 위해

대략적인 개요를 그려보았다.

앞으로는 각 ADT를 구현하기 위한 Concrete Data Structure는
구체적으로 어떻게 작성하는지
차근차근 공부할 계획이다.