[Data Structure] 자료구조

 

<정의>

  - 현실을 프로그래밍으로 표현하는 것

  - 집을 짓는데 필요한 건축자재. (모래, 시멘트, 벽돌 등)

  => 건축 자재(자료구조)로 건축하는 과정 == Algorithm(알고리즘)

 

<활용>

  - big size data를 효율적으로 관리

 

---

 

<종류>

1. 배열 (Array)

  - 여러 data를 하나의 이름으로 grouping하여 관리하기 위한 data structure

  - 관리할 data가 많아졌을 때 사용 (data가 2개인데 배열을 쓴다...?)

  - data를 넣는대로 index를 부여

  - array는 크기가 정해져 있으며, array 요소의 index는 변화하지 않는다.(ex. 젠가 - 중간에 뭐가 빠져도 나머지는 그대로)

 

2. 리스트 (List)

  - 배열의 고정된 index가 아닌, 빠진 부분을 빈틈없이 data를 메우는 data structure

 

2-1. 배열 리스트 (Array List)

  - 메모리 저장 공간에서 서로 다닥다닥 붙어서 저장됨(그만큼 찾는건 빠름)

  - 배열 + 리스트 의 조합. data 추가&삭제가 느리지만, 검색은 빠르다(index).

 

2-2. 연결 리스트(Linked List)

  - 메모리 저장 공간에 빈 공간 아무 곳에나 넣어버림(그만큼 넣는건 빠름). 위치만 무작위다. 각 요소는 연결되어 있음

  - 각 연결 지점(요소)는 node (vertex라고도 부름)

  - Node는 Data Field 와 Link Field 로 구성됨.
     => Data Field : 요소 정보 저장
     => Link Field : 다음 node의 연결 정보 저장

  - data 추가&삭제는 빠르지만, arraylist에 비해 검색은 느리다(index 없음).

  - 만약 3번째 요소를 찾는다면 첫번째 연결 요소부터 타고 올라가 찾아야 함.

 

3. 스택 (Stack)

  - 배열이 수직으로 쌓인 형태(여러개가 쌓인 팬케이크)

  - 맨 위부터 넣고, 맨 위부터 뺌

  - LIFO : Last In First Out

 

4. 큐 (Queue)

  - FIFO : First In First Out

  - 번호표 개념-pipe 형태. 순서대로 넣고(뒤부터 들어감), 가장 앞부터 뺌

  - 활용? 선입 선출 개념이 필요한 서비스 (은행의 대기 시스템, 연말정산 시스템 등)

 

5. 그래프 (Graph)

  - Node와 간선 사이의 연결 형태

  - Graph는 순환구조가 있고, Tree는 없다. 즉, 어느 부분이든 abc 세개의 Node가 모두 연결되어 빙글빙글 돌 수 있으면 순환구조다.

  - 굳이 세 Node일 필요는 없고 10개가 원 형태를 만들어 빙글빙글 돌면 Graph임 (graph ==서울 전철 2호선, tree == 분당선)

  - 활용? 빠른 경로 찾기 : 서울 지하철 노선도를 예시로 사용자가 출발 지점에서 도착 지점으로 어떻게 가는지 파악

  - 자세한건 아래 <참조.6> 을 보자

 

6. 트리 (Tree)

  - Node가 연결 구조로, 수직 계층인 parent-child 형태와 수평 계층인 left-right로 구성된 나무 모양

  - 맨 위가 root 고, 바닥이 leaves임. 선형구조(lenear) 아님

  - 활용? data를 계층 구조로 쓸 때. (ex. Computer의 File System-C폴더 안에 뭐뭐, 그 내용물인 system32 안의 뭐뭐...)

  - 다른 자료 구조와 비교하여 data 입력&삭제&탐색 모두 middle rate(속도)

 

7. 딕셔너리 (Dictionaries)

  - 파이썬에선 Dictionary, 타언어에선 Associative Arrays 라고 불림

  - Map, HashTable 등이 있음

  - 범위 내에서 index된 순서(sequence)를 가지는 다른 자료구조와 달리, 이 친구는 불변형의 keys를 index로 함

  - Key-Value 가 짝패(pair)로 활동함.  {key, value} 대충 이런 형태

 

---

 

<참조 1> http://www.kmooc.kr/courses/course-v1:YeungnamUnivK+YU216002+2018_01/course/

<참조 2> https://www.youtube.com/watch?v=Nk_dGScimz8 

<참조 3> https://opentutorials.org/module/1335

<참조 4> https://docs.python.org/3/tutorial/datastructures.html

<참조 5> https://www.geeksforgeeks.org/binary-tree-set-1-introduction/

<참조 6> http://math.ewha.ac.kr/~jylee/Finite/TextBook-2017/Chap10.pdf