JS로 배우는 자료구조와 알고리즘 3: 자료구조와 ADT

6 min readJun 23, 2018

이 글은 O’Reilly의 Data Structure And Algorithms With Javascript를 정리한 글입니다. 그리고 도입부의 자료구조의 근본에 대한 설명은 제 주관적인 정리입니다.

자료구조란?

“JS로 배우는 자료구조와 알고리즘 2 : Array 자료구조 (1)”에서 자료구조에 대한 근본적인 설명이 없는것 같아, 자료구조가 과연 무엇인지 생각해보겠습니다.

컴퓨터 과학에서 자료구조란, 데이터의 효율적인 접근(efficient Access)*을 위해서 조직되는 자료 저장 구조이다.
— Wikipedia, “Data Structure”

보통 접근(Access)은 일상적으로는 “가까이 다가감.” 라는 의미입니다. 그래서 “어떤 주체가 데이터에 다가가는 거지?” 하는 물음을 만듭니다. 그래서 단순하게, “데이터를 생성, 읽기,삭제, 수정 하는 모든 과정”으로 생각할 수 있습니다. 자바스크립트의 경우에는 변수를 다루는 것으로 해석할 수 있습니다. 효율적(Efficient)이라 함은, 알고리즘의 효율성(Algorithmic efficiency)의 준말이며, 최대한 적은 수행시간과 메모리 공간 사용을 가지는 특성을 가지고 있습니다.

따라서 자료구조는 “언제든 꺼내 볼 수 있는 수납공간” 이라고 생각할 수 있겠지요. 그 수납공간에는 특수한 목적으로 사용되는 경우 그 형태가 바뀌기도 할겁니다.

이전편의 Array 자료구조의 경우 거의 모든 고급언어가 Built-in으로 지원합니다. 보편적으로 가장 많이 사용하는 자료구조이기 때문입니다.

JAVA : int[] a = {1,2,3};
C, C++ : int a[3] = {1,2,3};
JS, Python, Ruby : a = [1,2,3];
PHP : $a = array(1,2,3);
Go : a:= [3]float64{ 1,2,3 };

따라서 Array 자료구조를 적절히 응용하여, 다른 자료구조를 만들 수 있습니다. 그래서 Array의 사용에 대해 미리 주의를 기울여 숙지할 필요가 있습니다.

추상 데이터 타입(ADT)

추상적(Abstract)이라는 의미는 좁은 의미에서는, 어떤 자료구조에 대해 세부적인 부대사항을 제거하고, 핵심적인 부분과 기능만을 표시하는 것입니다. 어떤 아이디어가 있을때, 아이디어의 세부적인 내용을 자르고 핵심적으로 어떤 자료와 기능이 필요한지 정리하여 더 구체화 시키는 것을 추상화(Abstraction)이라고 합니다.

추상데이터타입(ADT)는 자료형(Data Type)을 추상적으로 정의하는 것을 의미합니다. 보통 두부분으로 구성하는데, 다음과 같습니다.

데이터의 선언
연산의 선언

예를 들면 정수를 의미하는 Integer라는 자료형이 있다고 합시다. 정수의 구성요소는 실제 값이 들어가는 데이터와 정수를 가지고 할 수 있는 연산인 사칙연산(+,-,*,/) 과 나누기연산(%) 이 존재할겁니다.

자료형 Integer 
{
    데이터 : (-INT_MAX ~ 0 ~ INT_MAX](표현가능한 최댓값)내의 정수.
    연산:
        더하기 - ADD(X,Y) : return (X+Y)
        빼기 - SUB(X,Y) : return (X-Y)
        곱하기 - MUL(X,Y) : return (X*Y)
        나누기 - DIV(X,Y) : if(Y==0) return ERROR, else return (X/Y)
        나머지 - MOD(X,Y) : if(Y==0) return ERROR, else return (X%Y)
}

이렇게, 어떤 자료형이나 자료구조를 구현할때, ADT는 그에 대한 설계도 라고 생각할 수 있습니다. 위의 설계도를 사용하여 어떤 언어이든, 정의하여 사용할 수 있습니다.

자바스크립트의 경우, 객체지향 언어이기 때문에 보통 ADT를 객체로 구현합니다. 위의 ADT를 JS로 구현한다면…

function Integer(X){
    //멤버변수
    this.data = X;
    //메소드
    this.ADD = ADD;
    this.SUB = SUB;
    this.MUL = MUL;
    this.DIV = DIV;
    this.MOD = MOD;
}
Integer.prototype.ADD(X,Y) { return X+Y; }
Integer.prototype.SUB(X,Y) { return X-Y; }
Integer.prototype.MUL(X,Y) { return X*Y; }
Integer.prototype.DIV(X,Y) { if(Y==0) return null; else return X/Y; }
Integer.prototype.ADD(X,Y) { if(Y==0) return null; else return X%Y; }

완벽하지는 않지만 이렇게 구현이 가능합니다. 실제 JS에서 숫자를 다룰때 사용하는 Number 자료형의 경우는 더욱 복잡합니다.

Number 자료형
[데이터(속성이라고 함.)]
  - MAX_VALUE : 표현가능 최대값.
  - MIN_VALUE : 표현가능 최솟값.
  - NaN : Not A Number, 즉 Number자료형이 아니다.
  - NEGATIVE_INFINITY : 음수로 표현할 수 있는 가장 작은 값.
  - POSITIVE_INFINITY : 양수로 표현할 수 있는 가장 큰 값.
[메소드]
  + toExponential() : 어떤 수를 지수표현법으로 바꾼다. (ex : 2.534e+0)
  + toFixed(X) : 소수점 뒤에 X자리만 허용한다. (고정소수점표기)
  + toLocaleString(X) : 어떤 정수를 특정 언어의 표현으로 바꾼다. 아랍어의 경우 ar-EG.
  + toPrecision() : 숫자를 표현하는 문자열을 고정소수점표기나 지수표기로 변환.
  + toString() : 숫자를 문자열로 바꾼다. (ex : 123 => "123")
  + valueOf() : 숫자를 Number의 인스턴스로 선언한 경우, 그 숫자값을 반환.

실제 자주사용되는 메소드는 Number.prototype.toString() 으로 문자열처리에 자주 사용합니다.

정리

자료구조란, 데이터의 효율적인 접근(efficient Access)을 위해서 조직되는 자료 저장 구조이다.
Array 자료구조의 경우 거의 모든 고급언어가 Built-in으로 지원합니다.
추상데이터타입(ADT)는 자료형(Data Type)을 추상적으로 정의하는 것을 의미합니다. 데이터의 선언과 연산의 선언으로 이루어집니다.
JS에서는 ADT를 객체로 구현할 수 있습니다. 데이터의 경우 멤버변수(속성)로, 연산의 경우 메소드로 정의합니다.

JS로 배우는 자료구조와 알고리즘 3: 자료구조와 ADT

자료구조란?

추상 데이터 타입(ADT)

정리

Written by XJB