도서 리뷰 시리즈 - 한 권으로 그리는 컴퓨터과학 로드맵

출처

블라드스톤 페헤이라 필루. 『한 권으로 그리는 컴퓨터과학 로드맵』. 박연오(역). 인사이트, 2018.

한 줄 리뷰

컴퓨터 과학에 대해 정말 쉽게 설명한 도서

4 데이터 취급하기

추상

추상은 세부사항을 생락하여, 복잡한 사물의 기능을 단순한 방식으로 다루기 위한 인터페이스입니다. 데이터 추상은 데이터 처리 과정의 세부사항을 감추어 줍니다. 데이터 추상들의 동작 원리를 알아보려면 먼저 데이터 유형에 관해서 확실히 이해해야 합니다.

데이터 유형

우리는 데이터를 문자열, 불(boolean), 수 등으로 구별합니다. 그 분류의 기준은 데이터로 수행해야할 연산을 기준으로 삼습니다.

특정 위치의 문자를 기준으로 쪼갤 수 있고, 대소문자 변환이 가능하고, 다른 문자를 덧붙일 수 있는 데이터 변수는 어떤 유형일까요? 바로 텍스트를 나타내는 문자열 유형입니다.

XOR,OR,AND 연산을 수행하거나 반전시킬 수 있는 데이터 변수는 어떤 유형일까요? True 또는 False를 값으로 가질 수 있는 불 유형이죠. 마찬가지로, 더하고, 나누고, 뺄 수 있는 변수는 수 유형입니다.

4.1 추상 데이터 유형: 데이터를 취급하기 위한 명세

추상 데이터 유형은 특정 데이터 유형에 필요한 연산이 무엇인지 정해 준 명세입니다. 데이터 변수를 조작하기 위한 인터페이스를 정의해 둠으로써 메모리 속에서 실제로 데이터를 정하고 연산하는 데 필요한 모든 세부사항을 감출 수 있습니다.

4.2 추상 데이터 유형의 종류

기본 데이터 유형

기본 데이터 유형이란 여러분이 사용하는 프로그래밍 언어에 내장되어 있어 외부 모듈을 불러오지 않고도 쓸 수 있는 것을 말합니다.

스택

스택은 항목을 더미처럼 쌓아 놓고 가장 위의 항목을 기준으로 작업을 수행하는 방식입니다. 스택과 같은 데이터 처리 방식을 LIFO(last in first out, 후입선출)라고 합니다. 스택을 구현하는 모듈은 최소한 push, pop 두 연산을 반드시 제공합니다.

큐

큐는 조회되는 항목은 언제나 큐의 가장 앞의 항목, 다시 말해 큐에 추가된 지 가장 오래된 항목입니다. 큐의 핵심연산은 enqueue, dequeue 두 연산입니다.

리스트

리스트는 항목의 순서를 자유롭게 재배열하거나 아무 위치에서나 항목을 추가, 제거하고 싶을 때 편리하게 사용됩니다. insert, remove, get, sort, slice, reverse 연산이 공통적으로 정의됩니다.

맵

맵은 두 객체를 각각 키 객체와 값 객체로 연관시켜 저장할 때 사용됩니다. set, delete, get과 같은 연산이 정의됩니다.

집합

집합은 고유한 항목들을 순서에 상관없이 모아둔 것입니다. add, list, delete 연산이 정의됩니다.

데이터 구조: 데이터를 실제로 취급하는 방법

데이터 구조는 컴퓨터의 메모리 속에서 데이터가 실제로 구조화되는 방식과 그 데이터에 접근하는 방식을 알려줍니다. 데이터 구조는 추상 데이터 유형을 실제 데이터 처리 모듈로 구현하는 데 필요한 방법입니다.

배열

배열은 메모리에 연속적인 공간을 할당하여 만듭니다. 배열 속에 저장하려는 항목은 그 메모리 공간 속에 순차적으로 기록합니다.

트리

트리는 연결 리스트와 마찬가지로, 메모리 칸을 이용해 정보를 저장합니다. 따라서 트리도 연속적인 물리적 메모리가 필요하지는 않습니다. 트리의 칸도 저장 대상 외에 다른 칸을 향한 포인터를 가집니다.

그래프

그래프는 트리와 유사한 데이터 구조입니다. 트리와 다른 점이라면 자식-부모 정점이라는 개념이 없으며, 따라서 루트 정점도 없다는 점입니다. 그래프에서는 데이터가 정점과 간선으로 자유롭게 배열될 수 있습니다.

해시 테이블

항목의 탐색을 O(1) 비용으로 수행할 수 있는 데이터 구조입니다. 해시 테이블을 이용하려면 대량의 연속적 메모리를 미리 할당해야 합니다. 이 점은 배열과 비슷합니다. 하지만 항목을 순차적으로 저장하지 않는 다는 게 배열과 다른 점입니다. 해시 테이블에서 항목이 자리잡는 위치는 해시 함수에 의해 정해집니다. 해시 테이블은 맵과 집합을 구현하는 데 자주 사용됩니다.