1. 정의
a) 자료구조란?
- 대량의 데이터를 효율적으로 관리하기 위해, 데이터를 저장 및 정렬하는 방식을 말한다.
- 데이터를 어떤 방식으로 저장하고 정렬하느냐에 따라 추출 방식 등 데이터를 처리 및 조작하는데 필요한 코드가 달라진다.
2. 자료구조 (Data Structure)
a) 배열(Array)
https://wikidocs.net/22958
- 한가지 데이터 타입의 데이터를 순차적으로 저장 및 정렬하는 자료구조
- 각 데이터마다 index를 부여하여 데이터 검색에 용이(장점)
- 배열은 크기가 고정적(단점)
- 데이터가 삭제되면 배열 전체의 데이터를 재정렬(단점)
b) 큐(Queue)
https://galid1.tistory.com/483
- FIFO(First In, First Out)방식으로 데이터를 저장 및 정렬하는 자료구조
- FIFO방식으로 인해 데이터 삭제시, 재정렬이 필요없다.
- 운영체제(OS)에서 프로세스 스케쥴링 방식을 구현하기 위해 사용된다.
c) 스택(Stack)
- 이름처럼 데이터를 쌓는 방식(LIFO)으로 데이터를 저장 및 정렬하는 자료구조
- LIFO방식으로 인해, 구현이 단순하여 쉽다.(장점)
- LIFO방식으로 인해, 데이터의 저장 및 검색 속도가 빠르다.(장점)
- 저장될 수 있는 데이터의 최대개수를 미리 정해야한다. 즉, 저장공간의 낭비가 발생한다.(단점)
- 프로세스 실행구조의 기본으로 사용되는 자료구조
d) 연결리스트(Linked List)
https://beginnersbook.com/2013/12/linkedlist-in-java-with-example/
- 배열(Array)의 단점이 보완된 형태의 자료구조로, 크기가 가변적인 배열(장점)
- 크기의 가변성을 구현하기 위해 노드와 포인터를 사용하여 데이터를 저장 및 연결한다.
- 노드(Node): 데이터의 저장단위로, 데이터 값과 포인터(주소값)를 한 쌍으로 구성한다.
- 포인터(Pointer): 각 노드의 위치정보(주소값)을 의미한다.
- 포인터를 위한 저장공간이 따로 필요(단점)
- 포인터를 이용해 연결노드를 찾는 시간이 필요하다.(접근속도가 느리다)
- 데이터가 삭제하면 삭제된 데이터의 이전과 다음 데이터의 연결을 재구성해야한다.(단점)
e) 이중연결리스트(Double Linked List)
- 이중연결리스트는 이전과 다음 데이터의 주소값을 갖고 있는 연결리스트다.
- 연결 리스트와는 다르게, 한 방향이 아니라 앞뒤 양방향으로 검색이 가능하다.(장점)
f) 해시테이블(Hash Table)
- Key와 Value를 한 쌍으로 저장하는 자료구조
- Key를 Hash함수로 연산하여 나온 결과 값(해시값, 해시주소)으로 Value를 찾는 방식을 사용한다.
- Key를 이용하여 Value를 빠르게 검색할 수 있다.(장점)
- 특정 데이터의 중복을 쉽게 확인할 수 있다.(장점)
- 저장공간을 많이 필요로 한다(단점). 그러므로 해시테이블은 공간과 탐색시간을 맞바꾼 기법이라고 표현한다.
- 해시테이블의 빠른 검색능력의 이점으로 인해, 해시값의 중복확률을 줄이기 위해 해시테이블의 저장공간을 크게 잡아서 사용한다는 의미다.
- 해시값 충돌을 해결하기 위해 다양한 해시함수 및 해시충돌 알고리즘을 사용한다.
- Chaining 기법: Open Hashing기법 중 하나로, 해시테이블의 저장공간 이외의 공간을 활용하는 기법이다. 만약 해시충돌이 발생하면, 연결리스트를 사용하여 데이터를 추가로 연결시키는 저장방법이다.
- Linear Probing 기법: Close Hashing기법 중 하나로, 해시테이블의 저장공간 안에서 추돌을 해결하는 기법이다. 만약 해시충돌이 발생하면, 해시값(해시주소)을 이용하여 해시테이블 내부의 빈자리를 찾아 저장하는 기법이다.
g) 트리(Tree)
- 노드(Noe)와 브랜치(Branch)를 이용하여 구성한 자료구조로, 사이클이 없는 것이 특징이다.
- 트리를 기반한 이진트리를 이용하여 탐색 알고리즘 구현에 자주 사용된다.
h) 이진트리(Binary Tree) & 이진탐색트리(Binary Search Tree)
- 이진트리는 하나의 노드에서 파생되는 브랜치가 최대 2개인 트리구조를 말한다.
- 이진탐색트리는 이진트리를 기반하여, 반드시 좌측에 위치한 노드가 우측에 위치한 노드보다 작은값을 가진다는 규칙있는 트리구조를 말한다.
- 이진탐색트리의 특성으로, 특정 데이터를 검색하는데 용이하지만, 구현이 복잡하다.
i) 힙(Heap)
- 트리구조를 기반으로한 자료구조로, 데이터에서 최대값과 최소값을 빠르게 찾기위해 고안된 완전이진트리(Complete Binary Tree)다.
- 완전이진트리란, 데이터가 트리에 삽입될 때 왼쪽 노드를 우선 채우는 규칙을 갖고있는 이진트리다.
- 힙의 루트노드에 최대값이 위치하면 최대힙(Max Heap), 최소값이 위치하면 최소힙(Min Heap)으로 분류된다.
댓글