[Python] 5. 파이썬 자료구조 기초

학습내용

자료구조(Data structure)

 자료구조는 효율적인 접근과 수정을 가능하게 하는 자료의 집합을 의미하며, 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것을 말한다. 어떤 자료구조가 있는지 간단히 살펴보기만 하는 수준으로 알아보자.

스택(Stack)	셋(Set)
큐(Queue)	트리(Tree)
리스트(List)	그래프(Graph)
해시(Hash)

 

스택(Stack)

• 순서대로 데이터가 쌓이고, 역순으로 데이터가 나가는 것.
• 영어로 'First in, last out.'라 부름. 늦게 들어온 것이 먼저 나가는 구조.
• 웹페이지 뒤로가기 등에서 사용되고 있음.

큐(Queue)

• 들어온 순서대로 나가는 것. 스택과 반대되는 개념이라고 볼 수 있다.
• 선착순 관련된 것에서 모두 사용된다. ex) 티켓팅, 수강신청, 쿠폰, 은행 번호표 등.

리스트(List)

• 리스트는 각 엘리먼트가 서로 연결되어 있는 구조로 엘리먼트를 중간에 편집할 수 있다.
  ㄴ 큐나 스택은 전체 혹은 많은 부분을 갈아 엎어야 한다.
• 리스트는 스택, 큐처럼 활용도 가능하다.
• 리스트는 강력하나 각각의 엘리먼트를 연결하는 선에서 비용이 발생하게 된다.
• 리스트는 메모리 상에 인접하게 저장되지 않기에 수많은 데이터를 메모리 사용량, 탐색시간 등이 늘어난다.
  ㄴ 이런 부분은 작은 데이터에서는 느낄 수 없다.
• 위 그림과 같은 single linked list는 역순 탐색이 불가능하다.

• 위 그림과 같은 double linked list는 역순 탐색이 가능하다.
• 정렬, 수정, 삽입, 삭제 등 거의 대부분에서 아주 강력한 자료구조이다.

해시(Hash)

• 해시는 리스트의 단점을 보완한 key-value 값으로 데이터를 저장하는 자료구조로, 리스트가 약한 검색 부분을 강화했다.
• 10으로 나눈 나머지(%10)를 hash function이라 했을 때.
  • 100을 10으로 나눈 나머지 값이 0인 '100'과 '50'이 '0'에 저장된다.
  • 100을 10으로 나눈 나머지 값이 1인 '11'이 1에 저장된다.
  • 나머지 데이터도 위와 같이 저장된다.
• 위의 과정을 거쳐 검색속도를 높였다. 특히, 버킷 수를 1000개, 10000개로 늘리면 검색속도를 더 높일 수 있다.
• 검색속도는 O(n)(n번을 탐색해야한다)으로 표현.
• 해시는 자료가 순서대로 저장되지 않는다.

셋(Set)

• 셋은 집합. 합집합, 차집합, 교집합 등을 구현한 자료구조.
• 두 집합 간의 중복된 값을 제거하거나 합치거나 하기 위해 만들어진 순서없는 자료구조.

트리(Tree)

• 위 그림은 이진트리(binary tree)로 자신보다 작은 값은 왼쪽, 자신보다 큰 값은 오른쪽으로.
• 깊이가 곧 검색 시간이며 'log2에 N'이 된다.
• 해시보다는 느리다

그래프(Graph)

• 그래프는 정점(Vertex)간의 관계를 표현하는 조직도이다.
• 데이터가 저장되는 정점(노드, node), 노드간의 관게를 나타내는 간선으로 이루어져있다.

느낀 점

 하나하나씩 뜯어보며 공부할 필요가 있어보인다. 얼핏 보면 간단해 보이지만 구글링 해서 각 자료구조를 살펴보면 상당히 방대하고 다양한 내용을 찾아볼 수 있기에 추후 책과 구글링을 통해 공부하도록 해야겠다.