Part2. 5-1, 2 여러가지 자료구조에 대해 알아봅시다.

자료구조란 무엇인가?

• 프로그램에서 사용할 많은 데이타를 메모리 상에서 관리하는 여러 구현방법들
• 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨
• 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음
• 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 중요함

 

자료구조에는 어떤 것들이 있나?

 *  한 줄로 자료를 관리하기 (선형 자료구조 :  배열, 연결 리스트, 스택, 큐)
 *  선형 자료구조는 앞뒤의 요소가 1 대 1의 관계이다.  (1 대 다 ,  다 대 다 의 관계도 있다.)

 

배열 (Array) :  선형으로 자료를 관리, 정해진 크기의 메모리르 먼저 할당받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같음
                         배열은 중간에 비어 있으면 안 된다 ,  논리적인 위치와 물리적인 위치가 같다.

 

 

---

 

연결 리스트 (LinkedList) :  선형으로 자료를 관리, 자료가 추가될 때마다 메모리를 할당 받고, 자료는 링크로 연결됨.
                                            자료의 물리적 위치와 논리적 위치가 다를 수 있다
                                            배열은 처음부터 개수를 정하고 시작하지만 연결 리스트는 필요할 때 하나씩 할당 받는다
                                            링크가  C나 C++에서는 포인터이고,  자바에서는 객체의 주소, 참조변수를 가리키도록 하면 된다.
                                            자료 삽입, 삭제 연산은 배열보다 빠르지만 ,  자료를 찾는 것(검색)은 배열보다 느리다

 

 

---

 

스택 (Stack) :  가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료 구조 (Last In First Out)

                         (바둑, 장기에서 무르기 기능을 구현할 때  스택을 사용하면 좋다)

 

 

---

 

큐 (Queue) :  가장 먼저 입력 된 자료가 가장 먼저 출력되는 자료 구조 (First In First Out)
                       자료는 리어에서만 추가되고 프런트에서만 꺼낼 수 있다.
                       추가는  enqueue ,  삭제는  dequeue
                       큐를 배열로 구현한다고 하면  프런트에서 자료가 계속 빠질 때  자료들을 앞으로 당기지 않고 그 상태에서 프런트의                         위치를 바꾸다 보면  앞쪽이 비어서 메모리가 낭비되기 때문에  원형 큐로 구현하는 경우들도 있다.
                        둥그렇게 하면 계속 빈 공간을 채워가면서 쓰기 때문이다.

 

 

---

 

트리 (Tree) :  부모 노드와 자식 노드간의 연결로 이루어진 자료 구조

이진 트리 (binary tree) :  부모노드에 자식노드가 두 개 이하인 트리

 

 

완전 이진 트리(Complete Binary Tree) : 노드가 왼쪽부터 채워지고, 마지막 레벨을 제외하고 모든 노드가 채워져 있는 이진 트리

 

포화 이진 트리 (Perfect Binary Tree) :  꽉 찬 이진 트리

 

 

힙(Heap)  :  힙 조건을 만족하는 완전 이진 트리

 

힙 조건 :  2가지 경우가 있다.

               (1)  부모 노드의 값  >=   자식 노드의 값  (최대 힙 ,  Max heap)

               (2)  부모 노드의 값  <=   자식 노드의 값  (최소 힙 ,  Min heap)

               각각의 부모 노드가 모두 이걸 충족해야 한다,  루트 노드 값이 최대or최소고  아래로 내려갈수록  작아지거나 커지는 구조

 

Heap정렬에 활용 할 수 있다
Heap 정렬이란  Root를 하나씩 꺼내면  Tree에서 다시 가장 큰 값을 Root로 만들어서 바꾸는데(Reordering)
Root를 계속 꺼내면 큰 수부터 쭉 값이 꺼내지면서 정렬이 되는데 그것을 Heap 정렬이라고 한다.
우선순위 큐는  Heap을 사용해서 구현을 한다. (Heap을 이용하면 가장 우선순위가 높은 얘를 꺼낼 수가 있기 때문)

---

이진 검색 트리 (binary search tree)

 

이진 검색 트리에서는 값이 중복될 수 없다 ,  자료(key : 유일한 값)의 중복을 허용하지 않음

왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가짐

 

검색을 목적으로 만들어진 트리이다.

자료를 검색에 걸리는 시간이 평균 log(n) 임

 

중위순회 (inorder traversal) :  left를 보고 그 다음 부모 노드를 보고 right를 보는 방식

inorder traversal 탐색을 하게 되면 자료가 정렬되어 출력됨

 

jdk 클래스 :  TreeSet, TreeMap (Tree로 시작되는 클래스는 정렬을 지원 함)

 

---

 

그래프 (Graph) :  정점과 간선들의 유한 집합  G = (V, E)

• 정점(vertex) : 여러 특성을 가지는 객체, 노드(node)
• 간선(edge) : 이 객체들의 연결 관계를 나타냄.  링크(link)라고도 함
• 간선은 방향성이 있는 경우와 없는 경우가 있음
• 그래프를 구현하는 방법 : 인접 행렬(adjacency matrix) ,  인접 리스트(adjacency list)
• 그래프를 탐색하는 방법 : BFS(bread first search) ,  DFS(depth first search)

 

---

 

해싱 (Hashing) :  파이썬의 딕션너리

 *  자료 검색을 위한 자료 구조 ,  검색하는 속도가 굉장히 빠르다

 *   키(key)에 대한 자료를 검색하기 위한 사전(dictionary) 개념의 자료 구조

 *   key는 유일하고 이에 대한 value를 쌍으로 저장

 *   index = h(key) :  해시 함수가 key에 대한 인덱스를 반환해줌,  해당 인덱스 위치에 자료를 저장하거나 검색하게 됨

 *  해시 함수에 의해 인덱스 연산이 산술적으로 가능 O(1)
 *  해시 함수에 의해서 정해지는 인덱스는 내가 데이터를 넣은 순서랑은 무관해서 나중에 꺼내봤을 때
     내가 넣었던 순서랑 전혀 다르게 데이터가 꺼내질 수 있다.

 *  value가 여러 개일 수 있기 때문에 충돌(콜리전)이 발생할 수 있다. 가장 먼저 해시 함수를 어떻게 만드냐가 중요하고
     이를 더 잘 해결하기 위해 쓰는 것이 해시테이블이다.

 *  저장되는 메모리 구조를 해시테이블이라 함

 *  jdk 클래스 : HashMap, Properties

 

 

해시 테이블
 *  예를 들어 나머지가 23인 value 들이 있다고 하면  해시테이블에서는 같은 value가 들어왔을 때  옆에다가 저장한다.

 *  이때 슬롯에 같이 있는 얘네들을 시노님(동의어) 라고 한다.

 *  밑에 예시처럼 배열로 만들 수 있는데  이렇게 배열로 만들면 안 쓰는 공간도 많이 생기기 된다

     그래서 버킷이 크고 슬롯이 크게 되면 오버헤드가 너무 많기 때문에  연결 리스트를 활용한 체이닝 방식을 사용한다.

 

 

체이닝 (연결리스트를 활용한 해시 테이블)

연결리스트를 활용하여 필요할 때마다 할당 받는다
배열처럼 안 쓰는 공간이 발생하거나  더 많이 써야 되는데 슬롯이 부족한 경우는 없어진다
구현은 배열보다 복잡하다