자료구조
- 프로그램에서 사용할 많은 데이타를 메모리 상에서 관리하는 여러 구현방법들
- 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨.
- 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음.
- 여러 자료구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 중요함.
자료구조에는 어떤 것들이 있나?
- 한줄로 자료 관리(선형 자료 구조)
1.배열(Array): 선형으로 자료를 관리, 정해진 크기의 메모리를 먼저 할당받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같음
-> 검색이 빠르다.
2.연결 리스트(LinkedList): 선형으로 자료를 관리, 자료가 추가 될때마다 메모리를 할당 받고, 자료는 링크로 연결됨. 자료의 물리적 위치와 논리적 위치가 다를 수 있음.
-> 데이터 추가, 삭제가 빠르다.
3.스택(Stack): 가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료 구조(Last In First Out)
4.큐(Queue): 가장 먼저 입력된 자료가 가장 먼저 출력되는 구조(First In First Out)
- 트리(Tree 비선형 자료 구조): 부모 노드와 자식 노드간의 연결로 이루어진 자료 구조
1.힙(heap): Priority queue를 구현 (우선 큐)
- Max heap: 부모 노드는 자식 노드보다 항상 크거나 같은 값을 갖는 경우
- Min heap: 부모 노드는 자식 노드보다 항상 작거나 같은 값을 갖는 경우
->heap정렬에 활용 할 수 있음.
2.이진 트리(binary tree): 부모노드에 자식노드가 두 개 이하인 트리
3.이진 검색 트리(binary search tree)
- 자료(key)의 중복을 허용하지 않음.
- 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가짐.
- 자료를 검색에 걸리는 시간이 평균 log(n)임
- inorder traversal 탐색을 하게 되면 자료가 정렬되어 출력됨
-
그래프(Graph): 정점과 간선들의 유한 집합 G = (V, E)
-
해싱 (Hashing): 자료를 검색하기 위한 자료 구조
