Data Structure

유웅조·2020년 1월 8일

data structure 자료구조

Data structure

자료구조란 무엇인가??

백앤드 API의 핵심은 데이터의 처리이다. 데이터를 처리하기 위해서는 데이터를 수집하고 저장해야 하는데, 어떻게 하면 효율적으로 저장할 수 있을까?

만약 사과가 있는데 이것을 저장해야 한다. 그렇다면 어디에 저장하는 것이 좋을까? 그것은 목적에 맞게 달라질 것이다. 오랫동안 들고 다닐 것인지, 자주 꺼내 먹을 것인지, 갈아 먹을 것인지 등등...

자료구조의 종류가 여러가지가 있는 것은 여러가지의 목적에 맞게 데이터를 사용하기 위해서이다.

자료구조의 분류

Primitive : INTEGER, FLOAT, STRING, BOOLEAN

일반적으로 자료구조라고 한다면 Non Primitive: Array, List: Linear: Stack, Que, Non Linear: Tree, Tuple Dictionary Set, File 를 말한다.

Array(배열)

주로 이용하는 자료구조 중에 하나이다.
자료들을 쭉 나열한 것이라고 볼 수 있다. 실제 메모리(메모리는 빠르다. 하지만 용량이 크지 않다. 그래서 저장을 해야할 때는 하드 디스크에 저장을 한다. 자료구조는 메모리에서 사용된다) 상에서 물리적으로 바로 옆에 저장이 된다. 그렇기 때문에 순서가 생긴다. 즉, Index가 생긴다는 의미이다.
Index를 알고 있다면 해당 자료에 곧바로 접근할 수 있다. 또, Index가 있기 때문에 slice를 사용할 수 있다. 자료를 자른다는 의미이다.
Array를 생성할 때, 중간에 다른 메모리가 끼여 있으면 안되기 때문에 항상 일정 분량의 메모리를 차지하고 있다. Default Size가 보통 정해져 있다. C와 같은 언어에서는 다 지정하게 되어 있다. Python도 C-Array를 사용할 수는 있다.
만약 이미 할당되어 있는 Array의 크기보다 더 큰 Size의 자료를 저장하고자 할 때, Array Resizing이 일어난다. 이것은 높은 비용을 발생시키기 때문에 만약 Resizing이 자주 일어날 것 같은 자료라면, 애초에 Array를 사용하면 안된다.
Array의 중간에 있는 자료를 지우게 될 경우, 뒤에 있는 모든 자료들을 물리적으로 이동시켜야 하기 때문에 비효율적일 수 있다. 만약 추가, 삭제가 빈번하게 일어난다면 Array를 사용하지 않는 것이 좋다.

Multi Dimensional Array
Array의 요소가 Array가 되는 것이다. 바둑판, 매트릭스와 같은 2D, 2차원의 자료들에 많이 사용된다. 특정 메모리를 읽어들이는 것과 Index를 찾아 조회하는 것이 거의 비슷하기 때문에 굉장히 빠르고 효율적이다.

언제 쓰면 좋은가

순차적인 데이터를 저장할 때
특정요소를 빠르게 읽어야 할 때
데이터의 사이즈가 자주 변하지 않을 때

Tuple(튜플)

배열과 마찬가지로 순차적으로 저장하는 자료구조이다.
한번 바꾸면 변경할 수가 없다. (Immutable)
주로 2, 3개의 소규모 데이터를 저장할 때 쓰인다.
좌표를 나타낼 때 많이 쓰인다. class를 만들어 쓰는 것보다 효율적이다.

두개 이상의 값을 함수에서 반환할 때 쓰일 수 있다.

def test:
    return ('a', 8)

s, n = test()
# s == 'a'
# n == 8

파이썬에는 네임드 튜플 같은 것도 있다(Named Tuple).

Set

배열과 달리 순서가 없다.
고로 Index가 없다.

중복된 값이 허용되지 않는다.

my_set = { 1, 2, 3, 1, 2 }
my_set
# (1, 2, 3)
for n in my_set:
    print(n)
# 1
# 2
# 3

새로운 값이 넣었을 때, 이미 해당 값과 똑같은 값이 있다면 기존의 값을 치환해버린다.
자동자 번호판, 주민번호, 전화번호부 등에 사용될 수 있다.

Big O Notation O(N**2) 의 경우 Set를 사용하면 훨씬 효율적일 수 있다.

그렇다면 Set는 왜 순서가 없을까?
- 배열은 순서가 있고, Index가 있을 수 있도록 바로 옆에 저장된다.
- Set는 메모리 상에서 어떻게 저장되나
  - 예를 들어, 1을 저장한다고 가정한다.
  - hashing을 통해 1을 해싱하고 메모리 상의 버켓에 1을 저장한다.
  - 뒤이어 2를 저장할 경우, 2를 해시값에 해당하는 메모리 버켓에 저장한다.
  - 만약 1을 다시 저장해야 한다면, 1을 해싱한 뒤, 해시값에 해당하는 메모리 버켓에 저장한다. 다시 말해, 이미 있는 1을 치환해버리는 것이다.
  - 그렇다면 해시값에 해당하는 메모리는 어떻게 설정되는 것일까?
  - 세트도 결국엔 배열로 구성되어 있다. 해시값을 메모리의 크기로 나누고, 그것을 메모리 안에서 인덱스로 사용한다.
  - 만약 해시 / 메모리 크기 가 같은 자료가 있다면? 그것을 해시 충돌이라고 한다. Hash Collision이라고 한다.
  - 파이선의 경우에는, 해시 충돌을 피하기 위해, 해시의 비트 값을 나눠서 계산해서 Index로 사용한다. 그리고 메모레 크기가 거의 다 찰 경우 알아서 Resizing을 한다.
Set는 조회가 빠르다. 만약 특정값을 찾고 싶고, Index를 모른다면, 배열의 경우 처음부터 모두 조회해야 한다. O(N) Set는 해당 값의 해시값을 구한 뒤에, 그 값을 Index로 이용해서 값을 바로 찾아낼 수 있다. O(1)

HashMap(Dictionary)

Key : Value 의 형태로 저장하는 자료구조이다.
해시 기반의 자료구조이기 때문에 순서가 없다.
중복된 키로 저장할 수 없다. 만약 중복된 값이 키로 들어온다면 기존의 값을 Set처럼 치환해 저장된다.

Stack

Stack은 쌓는다는 개념과 비슷하다.
Last In First Out
마지막으로 들어가면 먼저 나온다.
예를 들어, 브라우저의 뒤로가기

Queue

First In First Out
예를 들어, 레스토랑에서 줄서기
우선 순위 Queue라는 것도 있다. 예를 들어, 우선 순위가 있는 자료라면, 먼저 Out한다.
우선 순위 Queue의 예로는 운영 체제의 프로세스가 있다. 예를 들어, 중요한 업데이트가 있다면 현재 CPU가 어떤 프로그램을 사용 중이던 간에 업데이트를 먼저 실행시킬 수 있다.

Stack & Queue 직접 구현해보기

Tree Structure

거꾸로 되어 있는 나무 형태를 말한다.
Binary Decision을 사용한다. 예를 들어, Root로 7이 있다면, 3은 7의 왼쪽, 0는 7의 오른쪽으로 간다. 뒤이어 8이 올 경우 => 7의 오른쪽, 9의 왼쪽으로 간다.
이것을 사용하는 이유는?? 탐색이 매우 빠르기 때문이다. 예를 들어, 8을 찾는다면 각각의 노드와 일치하는지를 검사하고, 만약 다르다면 큰지, 작은지만 검사하면 다음 노드로 넘어간다. Array보다 훨씬 빠르다. O(Log N)

유웅조

이전 포스트

Scope & Closure for Javascript

다음 포스트