Data Structure

Yerin·2020년 1월 8일
0

리눅스를 만든 리누스 토발즈는 알고리즘과 데이터구조만 알면 프로그래밍할 수 있다는 말을 했다..

데이터 구조?

데이터를 담고 활용하고 효과적으로 처리하기 위해 데이터 구조가 필요하다.
어떤 자료구조를 선택하냐에 따라 코드의 가독성이나 performance가 달라지기 때문이다.

ex) 사과를 백팩에 가지고 다닐것인지, 캐리어에 가지고 다닐것인지에 따라 편리함이 달라진다.

Array

  • sequence (순서)
    인덱스가 있는 이유는 순서가 있기 때문이고 순서가 있는 이유는 메모리에 차례대로 저장이 되어서이다. 인덱싱, 슬라이싱 가능.

  • Multi dimentional array
    매트릭스, 체스판 등
    메모리 효과적이고 젤 빠르다. 바로 옆에 붙어있고 인덱스를 통해 어떤 특정 메모리를 읽어들일 수 있다. 메모리옆에 순차적으로 입력된다.

  • 단점
    항상 메모리가 순차적으로 이어져있어야 해서(유지되어서) 요소를 삭제하면 삭제된 요소로부터 뒤에 있는 모든 요소들을 앞으로 한칸씩 이동시켜야해서 느려진다.

  • Array resizing
    한번에 메모리 할당하는 점 때문에.

Tuple

순차적으로 데이터 저장하지만 리스트와 다르게 수정할 수 없다. (immutable)
2-5개 사이의 elements로 주로 만든다. ex) 좌표
보다 간단하게 데이터를 표현할 수 있다. (효율성 up)
함수에서 리턴값을 하나보다 더 리턴하고 싶을때
코드만 보면 , 값에 대한 필드명이 없어서 확실치 않을때가 있다는 단점.
that's why there's 'named tuple'. 마치 class처럼 쓸 수 있다.

Set

여러개의 나열된 자료들을 저장. 하지만 순서가 없다. 인덱스가 없다.
중복된 값이 허용되지 않는다. 해쉬기반.

>>>my_set={1,2,3,4,5,1,2}
>>>my_set
{1,2,3,4,5}

ex) 전화번호 중복제거, 주민번호, 차번호판

set - look up이 빠르다
해쉬값 구한 다음에 해쉬값 해당하는 인덱스 찾아가서 본다.
순서가 없기 때문에 빠르게 찾을 수 있다.

Dictionary/HashMap

순서가 없다. key가 해쉬기반인 자료구조. 그렇기 때문에 중복된 key 가 있을 수 없다.
중복된 키가 들어오면 새로운값으로 치환됨.

Stack

접시 쌓는것. first out last in (filo)
마지막으로 저장한 데이터가 처음으로 읽힌다.
ex) 브라우저의 뒤로가기

class Stack:
   def __init__(self):
     self._stack = []

   def push(self, data):
     self._stack.append(data)

   def pop(self):
     if len(self._stack) == 0:
       return None

     data = self._stack[-1]
     del self._stack[-1]

     return data

   def peek(self):
     if len(self._stack) == 0:
       return None

     data = self._stack[-1]

     return data
     

Queue

First in First out 줄서는것

class Queue:
    def __init__(self):
        self._queue = []

    def push(self, data):
        return self._queue.append(data)

    def pop(self)
        if len(self._queue) == 0:
            return None

        return self._queue.pop()

    def peek(self):
        if len(self._queue) == 0:
            return None

        return self[0]
        

Tree

가장기본적인게 binary tree
탐색이 array보다 빠르다.
array O(N)
Tree O(logN)
중복된 값을 넣을 수 있다는 점이 세트와 다르다.
array에다 하는데 로직을 많이 넣는다.

profile
졸꾸 !!!

0개의 댓글