자료구조
프로그래밍을 하며 데이터들을 그저 배운대로 List, Map 컬렉션만 사용하고 있었습니다.
기계처럼 사용하는 것이 아닌 더 효율적인 방법에 대한 학습을 위해 자료구조에 대해 정리해봤습니다.
자료구조
데이터의 묶음을 저장하고 사용하는 방법을 정의한 것을 자료구조라고 합니다.
자료구조는 데이터를 체계적으로 저장하고 효율적으로 활용하기 위해 사용됩니다.
자료구조에는 여러 종류가 있으며 크게 선형 구조와 비선형 구조로 나눌 수 있습니다.
선형 구조
- 배열(리스트)
- 연결 리스트
- 스택
- 큐
- 덱
비선형 구조
- 그래프
- 트리
배열(리스트)
배열은 가장 기초적인 자료구조로 번호와 각 번호에 대응하는 데이터로 이루어져 있습니다. 일반적인 배열은 같은 종류의 데이터의 집합으로 순차적으로 저장됩니다.
번호가 존재하기 때문에 데이터를 효율적으로 탐색할 수 있다는 장점이 있지만 메모리 크기가 고정되어 있고 데이터를 추가하거나 삭제, 정렬하는 방식이 비효율적입니다.
연결 리스트
연결 리스트는 데이터와 포인터를 포함한 각 노드가 연결되어 있는 형태의 자료구조입니다.
노드의 포인터는 다음 또는 이전 노드의 메모리 주소를 참조하고 있습니다.
class Node<T> {
Node prev; // 이전 노드
Node next; // 다음 노드
T data;
}
연결 리스트의 종류는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있습니다.
번호로 탐색할 수 있는 배열과 달리 포인터를 통해 차례대로 메모리 주소를 찾아가야 하기 때문에 느리지만, 메모리의 크기가 동적이며, 데이터 추가/삭제의 빠른 처리속도를 보장합니다.
스택
스택은 데이터를 순서대로 쌓는 자료구조로 항상 끝에서만 자료를 넣거나 빼는 LIFO 구조로 되어 있습니다.
특정 위치에서만 데이터를 넣고 뺄 수 있기 때문에 제한된 자료구조라고도 합니다.
스택은 위와 같은 특징 덕분에 데이터의 추가와 삭제가 O(1)로 굉장히 빠른 처리속도로 이뤄집니다.
반대로 제한된 자료구조이기 때문에 특정 위치의 값을 가져오거나, 여러 개의 데이터를 동시에 처리할 수는 없습니다.
큐
큐 또한 제한된 자료구조 중 하나로 먼저 넣은 데이터가 먼저 나오는 FIFO 구조를 취하고 있습니다.
나중에 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이며 이름에서 알 수 있다시피 메시지 큐, 우선순위 큐 등 광범위하게 사용되는 자료구조입니다.
큐는 선형 큐와 원형 큐로 나뉠 수 있습니다.
선형 큐는 위의 이미지와 같이 Back 과 Front 가 데이터의 추가/삭제마다 포인터를 이동하게 되는데,
데이터가 삭제될 때마다 쓸모없는 공간이 생긴다는 단점이 있습니다.
원형 큐는 선형 큐의 문제를 보완하는 형태로 포인터가 max 를 넘어가면 다시 0을 가리키게 하여
사용되지 않는 메모리 공간을 재사용할 수 있습니다.
덱
덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 제한된 자료구조로 큐와 스택을 합친 형태로 볼 수 있습니다.
덱은 설정에 따라 한쪽으로만 입력 가능한 Scroll, 한쪽으로만 출력 가능한 Shelf 형태로 사용할 수도 있습니다.
덱에서도 데이터의 추가/삭제가 O(1)이며 제일 앞과 뒤의 데이터 탐색도 O(1)만큼 발생합니다.
그래프
그래프는 정점과 간선으로 이루어진 자료구조입니다.
주요 키워드로 정점은 Vertex/Node 라고 하며 간선은 Edge 로 각 정점을 연결합니다.
차수는 Degree 로 정점에서 간선으로 연결된 인접 정점의 수를 뜻하고, 가중치 Weight 는 간선의 크기가 있는 경우 그 크기를 뜻합니다.
루프는 loop 라고 하며 특정 정점에서 시작해서 같은 정점으로 들어오는 간선을 말합니다.
방향 그래프와 무방향 그래프
그래프의 간선에는 방향성이 존재할 수 있습니다.
방향성이 없다면 무방향 그래프로 간선이 연결되어 있다면 양방향으로 갈 수 있습니다. (A, B) = (B, A)
반대로 방향이 존재한다면 일방 통행으로 이해하면 되겠습니다. <A, B> ≠ <B, A>
순환 그래프와 비순환 그래프
사이클은 임의의 한 정점에서 출발해 다시 돌아올 수 있는 경로를 말합니다.
그래프에서 사이클이 하나라도 존재한다면 순환 그래프, 사이클이 없으면 비순환 그래프라고 합니다.
완전 그래프와 연결 그래프
모든 서로 다른 두 정점 쌍이 간선으로 연결된 그래프를 완전 그래프라고 부릅니다.
완전 그래프는 모든 정점이 서로 연결되어 있으며 연결 그래프는 모든 임의의 두 정점이 연결되는 형태를 말합니다.
그 외로 특정 정점 쌍 사이에 경로가 존재하지 않는 비연결 그래프가 있습니다.
트리
트리도 간선과 정점으로 이루어진 자료구조로 그래프의 특별한 종류입니다.
트리는 하나의 정점인 루트 노드를 가지고 있고, 0개 이상의 자식 노드를 가지고 있습니다.
자식 노드 또한 0개 이상의 자식 노드를 가질 수 있으며 이러한 집합을 트리라고 합니다.
트리에서 가장 말단에 위치하는 노드는 리프라고 합니다.
트리는 무방향이면서 사이클이 없는 연결 그래프이고 정점이 V개라면 간선은 V-1개로 이루어집니다.
또 임의의 두 노드를 연결하는 simple path가 유일한 그래프라는 성질이 있습니다.
이진 트리
이진 트리는 각각의 노드가 최대 두 개의 자식노드를 가지는 트리의 형태입니다.
이진 트리의 순회는 중위 순회, 전위 순회, 후위 순회, 레벨 순회를 통해 전체 탐색을 할 수 있습니다.
이진 트리의 종류로는
- 루트 이진 트리 : 하나의 루트 노드, 최대 2개의 자식 노드
- 정 이진 트리 : 모든 내부 노드가 0개 또는 2개의 자식 노드
- 포화 이진 트리 : 모든 내부 노드가 2개의 자식 노드를 가지며 모든 말단 노드가 동일한 깊이 또는 레벨
- 완전 이진 트리 : 모든 내부 노드가 2개의 자식 노드를 가지며 말단 노드는 가능한 가장 왼쪽에 존재
- 무한 완전 이진 트리 : 모든 노드가 2개의 자식 노드
- 균형 이진 트리 : 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이(균형 인수)가 1 이하
- 변질 트리 : 각 부모 노드가 오직 한 개의 자식 노드를 가짐
가 있습니다.
이진 탐색 트리
이진 탐색 트리는 각 노드에 값이 존재하며 왼쪽 서브 트리는 해당 노드의 값보다 작은 노드, 오른쪽 서브 트리는 높은 값의 노드들로 이루어진 자료구조입니다.
이진 탐색 트리는 하위 서브 트리도 이진 탐색 트리여야 하며, 중복된 키를 허용하지 않기 때문에 효율적인 데이터의 탐색이 가능합니다.
댓글남기기