TIL #45. Data Structure(session)

ceres·2020년 3월 12일
0

TIL

목록 보기
17/34

(20/3/12)

자료구조를 왜 써야하는가?

맥북을 쇼핑백에 넣을 수 있지만, 넣지 않음 -> 안전성
맥북을 캐리어에 넣을 수 있지만, 넣지 않음 -> 과함
보통 백팩에 넣음 -> 적합한 곳에 넣음

자료도 똑같다 적합한 곳에 넣어야함
코딩은 알고리즘과 자료구조로 이루어져있다.

자료구조의 분류

Primitive

자료구조이지만, 보통 자료구조라고 생각하지 않음.

Non-Primitive

  • Array/ List (배열)
    • 가장 많이 사용되는 자료구조
    • 사용: 이미지 배열, 상품 리스트, 값보다 순서가 중요할 때 사용
    • 다차원으로 사용할 수 있다. 리스트 내에 리스트가 존재할 수 있다.
    • 장점
      • indexing: 배열의 가장 큰 특징. 실제 메모리에 저장 될 때 물리적으로 옆으로 저장이되기 때문에 순서가 있다. 순서가 있기 때문에 index가 있다. index는 0부터 시작한다. index를 통해 불러오고 싶은 값만 뽑아서 가지고 올 수 있다. slicing 등도 가능하다.
    • 단점
      • 중간에 삽입/삭제를 해야하는 경우는 비용이 많이 든다. 그 뒤의 배열을 당기거나 밀어야 하기 때문이다.
    • resizing : 처음에 확보한 사이즈를 초과하면, 더큰 새로운 사이즈를 확보하고 전의 데이터를 모두 옯겨야한다. 사이즈를 예측하기 어려운 자료는 배열이 맞지 않다.
  • Tuple
    • 있는 언어도 있고, 없는 언어도 있다. 자바스크립트는 없다.
    • 짧은 수의 element를 저장할 목적으로 사용한다. ex) 1-5개 정도
      • tuple 내 수정이 불가능 하다. (array의 경우 0번째, 1번째 등 수정이 가능하다.
      • 간단한 데이터를 표현할때 사용한다.
      • ex) [(1,2), (2,4)] : 괄호가 tuple, 대괄호가 list
      • 튜플이 없으면 list와 class를 사용하면 되기 때문에 없는 언어도 있다.
  • Set
    • array, list 처럼 순열 자료구조임
      • 순서가 없음. 집어 넣은 순서로 나온다는 보장 없음
      • 중복된 값이 없다. 중복된 값이 들어오면 새로운 값이 기존 값을 대신한다.(replace)
        예) 값을 넣으면 hash함수 처리를 한 후(hash값 213값이 나옴) hash값은 연산해서 index번호를 정하고 그 공간에 값을 저장한다. 같은 값을 넣으면 hash 함수 처리한 값이 동일하기 때문에, 공간도 동일하다. 새로운 값이 기존 값을 대체하기 떄문에 중복값이 존재하지 못한다.
    • hash 값이 나오면 그 값을 연산(나누기) 해서 나온 값을 메모리 index값 으로 여기고 해당 메모리에 값을 할당한다.
      • 메모리 index 값이 동일한데, 가지고 있는 값이 다르다면 hash 충돌
    • 메모리에 공간이 없을수록 hash충돌이 잦을 것.
      • 보통 메모리가 70% 찼을 때 hash를 resizing 한다.
      • 탐색속도 O(1) : 세트 크기에 상관없이 찾는 속도 같음. hash 값 찾으면 바로 값 찾을 수 있으니까.
  • Dictionary
    • 변수 = {key:value}, jason 형식
      • dictionary 대신 calss를 사용해도 되지만, 코드를 짜야하기 때문에, 간단한 것은 dictionary 사용
    • field에 대한 설명이 필요할 때 사용
      • 중복된 값 저장 안됨 (key값 중복되면 나중 값으로 덮어쓰기=치환=replace 함)
        cf) tuple은 hash 함수 사용
  • 값이 replace 될 때, 기존 값과 현재 치환되는 값을 구분을 어떻게 할까?
    • ex) '1'=='1' 결과는 true
      • ex) cord(1,2)==cord(1,2) 결과는 false.
        이유: 메모리 주소값이 다르기 때문. 그러나 개발자가 같게 만들 수 있음.
        how? 최상위 부모에서 x,y값 같다고 정의해줌? eq함수로 정의해준다고 함.
        이거 모르겠어 class를 만들면 최상위 부모를 상속받는
  • Stack
    • FILO (Fisrt in Last Out) 접시 쌓는 경우
      • 밑단에서는 배열 사용
      • 사용: 함수를 호출할 때, 뒤로가기 버튼
        나중에 들어간게 가장 먼저 호출되어야함
    • 무한루프 일어나면 stack크기보다 들어가는 값이 많아짐. 이때 에러남
  • Queue
    • FIFO (Fisrt In First Out) 줄서기
      • 밑단에는 배열을 사용함. 배열에 로직을 붙여서 먼저 들어온 애가 먼저 나가는 구조를 만든것.
      • 줄서는 중간에 새치기를 하는 경우도 있다-> 우선순위가 있는 Queue = Priority Queue
      • Priority Queue: 긴급한 일 부터 처리하는 큐
  • Tree
    • 다양한 tree가 존재함. 예) 이진트리 : 작은값 오른쪽 , 큰 값 왼쪽
    • 탐색속도를 줄일 수 있음 (list의 경우 최악의 경우 사이즈 만큼 탐색하게 됨 )(N)번)
      • 최악의 경우 O(logN) 번 탐색
      • 탐색을 많이 하는 자료를 트리구조로 사용하게 됨
    • 세트의 경우 탐색속도가 더 빠름 ex)O(1) 그럼에도 Tree를 사용하는 이유는?
      트리는 들어오는 순서가 어느정도 보장이 됨. 세트는 아예 순서가 없음
      예) 1 < 4, "A"<"C" 숫자순서, 알파벳 순서로 트리 구조가 만들어지기 때문.
      • 정렬이 된 자료는 트리구조가 의미가 없다. 그냥 list임
  • Linked List
    • list는 물리적으로 순차적으로 연결되어있기 때문에, 물리적인 공간을 만들어줘야함.
      그것을 극복한 것이 linked list
      • 참조 : 바로 옆에다 저장하지 않고 다른 곳에 저장해도 참조해 놓으면 연결됨. (순서가 생김)
    • 효율성이 떨어짐. 순서대로 숫자를 저장하는 경우, 참조를 사용하면 숫자 10개를 저장하는 것이 아니라, class 10개를 저장하는 것이됨. 메모리를 많이 사용해야한다.

0개의 댓글