자료 구조
데이터를 정리하는 것이다.
데이터를 어떻게 정리하냐(어떤 데이터 구조를 사용하냐)에 따라서 어플리케이션의 속도에 영향을 준다.
검색,읽기, 삽입, 삭제 4개가지 상황을 염두하고 데이터 구조를 보고 적절히 사용해야 한다.
Array배열
| reading | 🟢 | index값을 통해 간단히 값을 가져올 수 있다. |
| searching | 🔴 | 배열에서 값을 찾으려면 하나하나 체크하는 과정을 거쳐야 함으로 좋은 방법이 아니다. 이런 식으로 처음부터 끝까지 순차적으로 검색해야하는 것을 "Linear Search 선형 검색"이라고 한다. |
| add | 🟡 | 배열에 여분의 공간이 있을때, 맨 마지막에 값을 추가하는건 문제가 없다. 하지만 처음이나 중간에 값을 추가하거나 남아있는 공간이 없을 경우에는 기존의 값들이 이동하거나 복사까지 해야서 단계가 늘어난다. |
| delete | 🟡 | add와 마찬가지로 마지막요소가 삭제된다면 가장 베스트이다. 하지만, 중간이나 첫번째 요소가 삭제된다면 기존 값들의 이동이 일어나 단계가 늘어난다. |
Hash Table
key와 value로 이루어졌다. array와 비교해보자
만약 해당 배열에서 name이 pizza의 가격을 알아내려 한다고 해보자.
선형검색을 통해 하나 하나 배열의 name을 검사해서 pizza인 값의 price를 가져와야 한다.
만약 pizza가 100개의 요소중 100번째라면 100번의 step을 거쳐야 함으로 Linear Time. 즉, O(n)이다.
hash를 사용해서 작성하면 이렇다.
바로 key가 pizza인 것을 찾아서 value를 가져오면 된다.
pizza가 몇번째에 있던, 그 외에 tea, juice를 가져오던 상관없이 step은 1회 발생하기에 Constant Time. 즉, O(1)이다.
hash가 유용할 때
배열에 특정 값이 있는지 확인하고 싶을 때, array라면 선형검색으로 하나하나 체크해야하지만, hash에서는 배열[찾는것] 이렇게 바로 찾을수 있다.
hash가 더 빠른이유
Hash Table에는 array구조가 있다.
작동방식은 Hash Function에 내가 찾는 key를 넣는다. 해시함수가 돌려준 숫자로 내부의 array를 검색해서 value를 찾는 것이다.
hash 충돌 (Collision)
hash가 같은 경우 해시함수가 돌려준 숫자가 동일하다.
hash table내부에 같은 index를 가진 array가 생기면서 내부에서 선형검색을 한다. 그래서 언제나 상수시간은 아니다.
충돌이 있을수도 있고, 그 경우 선형검색을 해야하기 때문이다.
추상적 자료구조(ADT)
프로그램 언어가 아닌 일종의 "규칙"이다. 이런 추상적 자료구조(ADT : Abstract Data Type)라고 부른다.
코르도 정의 된 것이 아니라, 행동양식으로 구성된 것이다.
스택 (Stack)
팬케이크처럼 가장 나중에 쌓은 걸 가장 먼저 먹게된다.
즉, 가장 나중의 것을 가장 먼저 처리하는 것이다.
LIFO - Last In, First Out
예를 들면, 웹서핑을 할때 뒤로가기를 하면 맨 마지막 기록을 차근히 불러오는 경우가 있다.
큐 (Queue)
줄서기처럼 가장 먼저의 것을 가장 먼저 처리하는 것이다.
FIFO - First In, First Out
출처