Array(배열)의 특징에 대해서 설명
배열은 특정 크기만큼 연속된 메모리 공간에 데이터를 저장하는 자료구조입니다. 연속된 메모리 공간에 데이터들이 나열되어 있기 때문에 첫 주소만 알면 다른 위치도 쉽게 알수 있습니다. 또한 크기가 고정적, 제한적이며 논리적 저장 순서와 물리적 저장 순서가 일치하게 됩니다.
Array(배열)의 검색, 삽입, 삭제에 대해서 설명
검색시 인덱스를 통해 직접 접근이 가능하기 때문에 시간 복잡도는 O(1)로 상수시간이 됩니다. 삭제와 삽입의 경우 삭제한 인덱스보다 큰 인덱스를 가진 원소들을 옮겨주는 비용이 들어 시간 복잡도 O(n)의 시간이 걸리게 되며 삽입의 경우도 마찬가지 입니다.
삽입 삭제의 경우 데이터가 많을 때 비효율적이기 때문에, Linked List를 사용하게 됩니다.
LinkedList의 특징
배열과는 다르게 연속된 메모리 공간에 저장되어 있지 않습니다. 메모리 공간상 고유한 노드로 존재하고 있으며, 자신 앞 뒤 데이터에 대한 주소를 기억하고 있습니다.
검색시 LinkedList는 연속된 메모리 공간에 존재하지 않고 모두 떨어져 있기 때문에 순차적으로 찾는 순차 접근(Sequential Access)를 지원합니다.
삽입 삭제가 빈번하다면 LinkedList를 사용하는 것이 좋습니다.
LinkedList의 검색, 삽입, 삭제에 대해서 설명
검색시 요소에 접근할 때 순차적으로 검색하며 찾아야 하기 때문에, 특정 요소에 접근할 때 시간 복잡도는 O(n)이 됩니다. 삽입과 삭제시 새로운 요소에 할당된 메모리 위치 주소가 LinkedList의 이전 요소에 저장됩니다.
O(1)의 시간 복잡도로 가능할 때는 맨 앞 또는 맨 뒤의 노드에 삽입,삭제할 때이며, 중간에 삽입,삭제를 하게 되면 해당 노드를 찾아가는 동안 O(n)의 시간 복잡도를 갖게 되며, 삽입 삭제의 시간 복잡도 까지 계산하면 결국 O(n)의 시간 복잡도를 갖게 됩니다.
삽입 삭제가 빈번하다면, LinkedList를 사용하는 것이 시간 복잡도상 Array보다 우위에 있다. 하지만 검색이 빈번하게 이루어진다면, Array가 LinkedList보다 우위에 있다.
ArrayList(배열 리스트)
삽입과 삭제시 내부적으로 데이터를 관리해 데이터의 추가/삭제를 위해서 임시 배열을 생성해 데이터를 복사하는 방법을 사용합니다. (다른 데이터를 복사해야 하기 때문에 O(n)의 시간복잡도를 갖고 있음)
검색시 인덱스를 갖고 있어 한 번에 참조가 가능해 데이터 검색에 유리합니다. (index기반이기 때문에 O(1)의 시간 복잡도를 갖고 있음) 원소에 대해 빠르게 접근 할 수 있고, 원소들이 메모리에 연속적으로 배치해 있어 CPU Cache효율도 더욱 높습니다.
대량의 자료를 추가,삭제 하는 경우 그만큼 데이터 복사가 많이 발생해 성능 저하가 일어나게 됩니다. 또한, 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 존재해야 합니다.
Stack과 Queue
Stack은 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는(LIFO)되는 구조적 특징을 갖고 있습니다.
Queue는 가장 먼저 삽입된 자료가 가장 먼저 삭제되는(FIFO) 구조적 특징을 갖고 있습니다.
둘의 가장 큰 차이점은 데이터를 삭제할 때 있습니다. Stack은 가장 마지막에 추가됐던 데이터를 삭제하고, Queue는 가장 처음으로 삽입된 데이터를 삭제합니다.
priorityQueue(우선순위 큐)
우선순위 큐의 특징은 가장 우선순위가 높은 데이터를 먼저 꺼내기 위한 자료구조 입니다. 내부는 Heap인 완전 이진 트리로 구현되어서 우선순위 큐의 시간 복잡도는 O(logN)이 됩니다.
힙으로 구현된 이진 트리는 모든 정점이 자신의 자식 요소 보다 우선순위가 높다는 성질을 가지고 있습니다. 이 성질을 통해 삽입과 삭제 연산을 모두 O(logN)으로 수행할 수 있습니다.
Heap
Heap의 특징은 완전 이진 트리입니다. 모든 노드에 저장된 값들은 자식 노드들의 값보다 우선순위가 크거나 같습니다. 즉, 루트노드에 우선순위가 높은 데이터를 위치시키는 자료구조 입니다. 최대힙, 최소힙은 완전 이진 트리 이면서 루트 노드로 올라갈 수록 저장된 값이 커지거나 작아지는 구조입니다.
그렇다면, 왜 연결리스트나 배열로 구현하지 않을까?
배열(Array)로 구현, 우선 순위가 가장 높은 순서대로 배열의 가장 앞부분부터 넣는다면, 우선순위가 높은 데이터를 반환하는데는 index를 이용하면 되므로 어렵지 않습니다. 다만, 우선순위가 중간인 데이터가 삽입되는 과정에서 뒤의 데이터까지 index를 모두 밀어야하는 단점 때문에 특정 경우에 시간 복잡도의 편차가 심하게 되기 때문입니다.
연결리스트(LinkedList)으로 구현, 우선순위가 높은 데이터의 반환은 배열과 마찬가지 이지만, 연결 리스트 또한 삽입과정에서 배열과 마찬가지로 그 위치를 찾아야 하기 때문에 최악의 경우 맨 끝까지 가야하기 때문입니다.
힙(Heap)으로 구현, 삭제나 삽입 과정에서 모두 부모 자식간의 비교만 이루어집니다. 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 개수는 2배 증가하여 비교 연산 횟수는 1회 증가하게 됩니다. 삭제나 삽입 모두 최악의 경우 O(logN)의 시간 복잡도를 갖기 때문에 더욱 안정성이 있습니다.
Hash Table(해시 테이블)
해시함수(HashFunction)로 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말합니다.
HashTable은 Key/Value로 데이터를 저장하고 빠르게 데이터를 검색할 수 있는 자료구조 입니다. 내부 배열을 사용하며, Key값에 해시함수(HashFunction)를 적용해 배열의 고유한 index를 생성해 데이터를 저장합니다. 또한, 적은 리소스로 많은 데이터를 효율적으로 관리하며, index에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입,삭제를 빠르게 수행가능합니다.
Hash Table와 Array(배열)의 검색 속도는 O(1)로 돌일한데 왜 HashTable을 사용하나요?
배열은 미리 공간은 할당해둬야하는 공간적 손해가 생길 수 있지만, 해시 테이블은 그렇지 않아 공간적 측면에서 더 실용적입니다.
Hash Collision을 예방하기 위한 방법
분리 연결법(Separate Chaining)이 있습니다. 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용해 다음 데이터 주소를 저장하는 방법입니다. 테이블의 확장이 필요없고, 삭제와 구현이 간단하다는 장점이 있습니다. 단, 데이터의 수가 많아지면 동일한 버킷에 연결된 데이터가 많아지며 캐시의 효율성이 감소합니다.
개방 주소법(Open Addressing)이 있습니다. 해시 함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용하는 취지입니다. 개방 주소법은 삭제시 더미를 넣어줘야하는데 이유는 다른 주소에 값을 넣어 줬기 때문에, 삭제가 되면 바로 종료가 됩니다.
Tree(트리)란?
트리는 하나의 루트 노드를 갖고 있고, 루트노드는 0개 이상의 자식을 갖고 있는 비선형 계층적 구조의 자료구조입니다.
Tree의 특징
계층적 자료구조 이며, 사이클이 존재하지 않습니다. 하나의 루트 노드를 갖고 있으며, 루트 노드는 0개 이상의 자식 노드를 갖고 자식노드 또한 0개 이상의 자식 노드를 갖습니다.
이진 탐색 트리(Binary Search Tree)
이진 탐색 트리는 정렬된 이진 트리입니다. 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가 있는 노드만 포함되며 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가 있는 노드만 포함됩니다. 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리여야 하며, 중복된 키를 허용하지 않습니다. Inorder Traversal을 수행해 모든 키를 정렬된 순서로 가져올 수 있습니다.
검색할때, BST의 검색에 대한 시간 복잡도는 균형 상태이면 O(logN)의 시간이 걸리고, 불균형 상태라면 최대 O(n)의 시간이 걸립니다. 검색과정은 루트에서 시작해 검색 값을 루트와 비교합니다. 루트보다 작으면 왼쪽에 대해 재귀, 크다면 오른쪽에 재귀합니다. 일치하는 값을 찾을 때까지 반복합니다.
삽입(입력)할때, 중복을 허용하진 않습니다. 새 키는 항상 리프노드에 삽입 됩니다. 루트에서 시작되어 삽입 값을 루트와 비교합니다. 루트보다 작으면 왼쪽으로 재귀, 크다면 오른쪽으로 재귀합니다. 리프 노드에 도달한 후 노드보다 크다면 오른쪽에 작다면 왼쪽에 삽입합니다.
삭제할때, 리프노드인 경우에는 노드를 삭제하기만 하면 됩니다. 노드에 자식이 하나만 있을 경우 삭제된 노드의 부모 노드에 직접 연결합니다. 노드가 두개일 경우, 오른쪽 subtree에 최소값을 올려줍니다.