TIL - 자료구조 (Data Structure)

자료구조란?

데이터를 알맞은 구조에 넣어서 효율적으로 관리하는 데이터관리에 있어서 하나의 구조이다. 노트북을 쇼핑백에 넣는 것 보단 노트북가방에 넣어 들고다닐 때 생기는 편의성이 더 큰 것 처럼, 데이터의 성격에 따라 알맞은 자료구조를 사용하는 것은 시스템의 작동 기능을 좌우한다.

자료구조의 분류

• Primitive Data Structure : integer, string, boolean
• Non-primitive Data Structure : list(array), tuple, set

자료구조의 분류 중 Non-primitive Data Structure를 보통 자료구조라 한다.

우리가 데이터를 자료구조를 사용하여 선언하면, 메모리상에는 선언한 자료구조에 담긴 데이터가 올라가 공간을 차지한다.

그렇다면 튜플형태의 자료구조인 (1,2)와 (1,2)가 두개가 있다면

(1,2) == (1,2)

는 성립할까?

정답은 False이다. 모든 객체는 메모리의 부모클레스에 의해서 정의되고 메모리최상우 메모리의 부모클래스는 각 객체의 해쉬값을 주소로 가지기 때문에 두개의 객체는 실재로 같을지라도 다른 메모리상의 주소를 부여받기 때문에 같은 값일지라도 엄밀히 같지는 않다.

그렇다면 클래스의 경우는 어떨까?

class Car(object):
  def __init__(self, model, color, company, speed_limit):
    self.color = color
    self.company = company

audi = Car(red, audi)
audi = Car(red, audi)
이렇게 두개의 Car클래스 객체가 정의되어 메모리상에 올라가면 메모리 최상위 부모클래스에 의해 각각의 다른 주소를 부여받을 것이다. 하지만 부모클래스의 성질을 물려받아도 현재 위치의 클래스에서 두 객체가 같다고 정의해주면 완벽하게 같은 객체가 되어

> Car(red, audi) == Car(red, audi)
True

가 성립한다.
즉, 클래스는 자식클래스에서 어떻게 정의하느냐에 따라 바뀔여지가 있다.

이러한 메모리상의 객체의 성질을 알고 자료구조의 종류에 대해 알아보자.

Array

python에서는 list라고 하고 실재로 값이 메모리상에 저장될 때 바로옆에 저장된다. 같은 공간의 바로옆에 데이터가 저장되기 때문에 인덱싱이 가능하며 몇번째의 데이터를 빼오는 것이 가능하다. 인덱싱이 가능하기 때문에 구간을 읽어오는 슬라이싱도 가능하다. 배열은 한번생성하면 일정공간이 메모리에 할당된다.

단점

• 데이터가 순서대로 빈공간 없이 붙어있어야 하기 때문에 데이터 열 중간의 엘리먼트를 삭제하면 삭제된 엘리먼트 뒤의 값을 하나씩 땡겨야 한다. 삭제 된 곳을 비워 둘수 없기 때문이다.
• 데이터 열 중간에 엘리먼트를 사입하면 해당 인덱스 뒤에 있는 값을 전부 하나의 인덱스씩 뒤로 밀어야 한다. python에서 list의 매서드인 append를 가장 많이 사용하는 이유이다.
• 한번 생성하면 일정공간이 메모리에 할당 되며 그 공간이 다 차지않고 방치되면 메모리 사용의 비효율을 가져온다.
• 메모리상 배열에 할당된 공간이 다 찰 경우 메모리 공간을 재할당해야한다(리스트 리사이징). 예를들어 100의공간을 전부 사용하고 101번째 데이터를 넣는경우 이 공간의 데이터를 복사하고, 다시 200의 공간을 만들어 1부터 100까지의 데이터를 붙혀넣기 하고 101번째 데이터를 생성한다. 이와같은 비싼 오퍼레이션은 메모리사용의 비효율을 가져온다.

그렇다면 배열은 언제사용 할까?

• 순차적인 데이터를 저장할 때
• 어떤 특정요소를 빠르게 읽어야 할 때 : 인덱싱이 가능하기 때문에 데이터를 읽어오는 시간이 짧다
• 전체 데이터의 사이즈가 어느정도 정해 져 있을 때
• 요소를 중간에 삭제하거나 넣지 않아도 될 때

Tuple

리스트와 비슷하게 순차적으로 데이터를 저장하는 배열 구조로 되어 있지만 일반적으로 2~5개의 작은 단위의 엘리먼트를 저장하기 위해 사용한다.

굳이 튜플을 쓰지않고 배열에 작은 단위의 엘리먼트를 저장 할 수도 있지만 튜플은 한번 집어넣으면 수정이 되지 않기 때문에 값이 고정된다.
주로 (1,2), (x,y)와 같이 좌표에 사용된다. 만약 튜플을 사용하지 않는다면 class를 만들어 클래스 객체를 만들어줘야 하는 번거로움이 있기 때문에 파이썬에서는 튜플을 자주 사용한다.

Set

Set 자료구조는 3가지 특징을 가진다.

• array가 가지는 특징인 순서가 없다.
• 중복된 값을 허용하지 않는다.
• 새로운 값을 넣었을 때 메모리에 같은값이 있으면 저장되어있는 값을 치환한다.

그렇다면 set은 왜 이러한 특징을 가질까?

Set의 자료형 또한 하부의 기본은 어레이로 되어있다. 그리고 값을 해시화해서 저장한다.
예를들어 set이라는 자료형으로 123이라는 값을 저장할때 123은 해시값으로 치환되고 특정 수로 나눈 나머지 값을 메모리상의 공간에 저장된다. 결국은 어레이형태로 저장되긴하지만 주소를 해시값으로 가지고있기 때문에 array와 같이 순서를 가지고 있지 않다. 하나의 해시값을 가진 주소에는 하나의 값만 들어가야 하기 때문이다.(해시값의 특징상 하나의 값은 하나의 해시값을 가진다.) 그리고 메모리상에 같은 해시값이 들어오면 저장되어 있는 값을 치환한다. 이 때문에 중복을 허용하지 않는다.

하지만 set자료형도 결국 array를 바탕으로 하기 때문에 set을 선언하는 즉시 데이터를 저장할 수 있는 공간이 메모리상에 생성되고, 밑단에 값이 찰수록 해시값을 특정수로 나눈 나머지값(set value의 주소)이 중복될 확률이 올라가기 때문에 리사이징을 해야한다. 보통 밑단의 array가 70%정도 찼을 때 리사이징 한다.

Dictionary

딕셔너리 역시 저장 원리의 기본은 배열이다. 배열 위에 로직을 올려서 딕셔너리 형태를 만든 것이다.
Key를 해시화해서 주소로가지고, Value를 저장하는 해시 테이블형태로 저장된다. 해시값을 주소로 가지기 때문에 중복된 Key를 가질 수 없다. 같은 키가 들어오면 이전에 저장했던 Key를 치환한다.

Key와 Value를 묶어서 저장하기 때문에 Key에 대한 설명이 필요 한 경우 dictionary를 사용한다.

Stack & Queue

Stack

• First In First Out(FILO)
  접시를 쌓는다고 생각해보자. 접시위로 쌓고 제일처음에 쌓은 1층 접시를 빼게되면 쌓은 탑이 무너진다. 그래서 우리는 맨 마지막에 쌓은 접시부터 순차적으로 접시를 뺀다. Stack자료구조도 마찬가지로 제일 마지막에 들어간 데이터부터 사용한다. 로직의 밑에 배열을 두고 나중에 넣은 데이터를 먼저 나오도록 한다.

• 함수를 호출하면 스텍형태로 쌓인다. 제일 마지막페이지로 돌아가는 브라우저의 뒤로가기 기능을 생각해보면 이해하기 쉽다.

Queue

• First In First Out(FILO)
  Stack과는 반대로 먼저 줄을 서는 사람이 먼저 입장하는 줄을 서는 경우를 생각해보자. 로직의 가장 밑단에 배열을 두고 먼저넣은 데이터를 먼저나오게 정의한다.

• 순서중에서도 우선순위가 있는 경우 Priority Queue를 사용한다. 예를들어 윈도우 OS에서는 우선순위가 있는 중요한 프로세스부터 먼저 실행되고 다른 프로세스가 실행된다

Tree

여러개의 Tree자료구조가 있지만 2진트리가 가장 많이 사용된다.

위의 2진트리의 저장 프로세스를 알아보자

1. 13이들어온다.
2. 처음들어온 13이 기준이되어 13보다 작은 8이 왼쪽에 저장되고, 13보다 큰 17이 오른쪽에 저장된다.
3. 11이 들어와 17보다는 8보다는 크지만 8에 더 가깝기 때문에 8의 오른쪽이 저장된다.
4. 15가 들어와 8보다는 크고 17보다는 작지만 17에 더 가깝기 때문에 17의 왼쪽에 저장된다.

이런식으로 값이 이전에 들어온값에 영향을 받아 저장된다.
2진트리로 저장을 할 경우 값을 찾을 때 편리하다. 위의 경우 6을 찾아야 할 경우 처음들어온 13부터 순차적으로 들어온 모든 값을 다 확인해야 겠지만 2진트리의 경우 먼저 들어왔고 이전값과 연결된 13, 8, 1을 확인하면 6일 찾을 수 있다.
그래서 2진트리에서 값을 찾기 위해서는 logN번의 look-up을 거치면 된다.

숫자가 아니라도 함수로서 들어온 값의 기준을 정해주면 2진트리를 사용할 수 있다.

Linked List

말그대로 연결된 리스트 자료형을 말한다. 배열 자료형은 메모리상에서 물리적으로 바로옆에 저장되어 있기 때문에 데이터가 생성 될 때 물리적인 공간확보를 해야하고 공간을 다 차지하면 리사이징을 해야한다.

이러한 문제의식 때문에 Linked List가 등장한다.
먼저 들어온 데이터가 그 다음 데이터를 참조하기 때문에 메모리상에 물리적으로 같은 공간에 저장 될 필요가 없다. 메모리상의 빈공간에 저장될 것이기 때문에 리사이징 문제를 고민할 필요도 업어진다.

하지만 link list의 경우 클래스형태로 만들어야 하기 때문에 만들 때 부터 메모리를 많이 차지하기 때문에 효율성이 없다는 평가를 받는다

컴퓨터사이언스에서는 silver bollet은 없다는 말이 있다. 즉, 시간 아니면 메모리를 희생해야 한다는 것이다. 데이터구조를 잘 이해하고 상황에 맞게 사용하자.