자료 구조
자료구조 & 알고리즘
자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조이고, 알고리즘이란 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임입니다.
Array
Array 자료구조는, 논리적 저장 순서와 물리적 저장 순서가 일치하는 자료구조입니다.
따라서 O(1)만에 조회를 할 수 있습니다. 즉 random access 가 가능하다는 장점이 있는 것 입니다. 하지만 삽입 혹은 삭제의 경우 배열의 연속적인 특징이 깨지게 되므로 삽입, 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)이 됩니다.
키워드: 저장 순서, 연속적인 특징, shift 비용
Linked List
Array의 문제점을 해결하기 위한 자료구조가 linked list 입니다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지 기억하고 있기에 이 부분만 다른 값으로 바꿔주면 삽입과 삭제를 O(1) 만에 해결할 수 있습니다.
하지만 원하는 위치에 삽입을 하고자 하면 원하는 위치를 찾는 과정에 있어서 O(n)의 시간이 추가적으로 발생합니다. 결국 Linked list 자료구조는 삽입, 삭제, 조회에 모두 O(n)의 시간 복잡도를 갖습니다. 이 Linked List 는 Tree 구조의 근간이 되는 자료구조이기에 Tree 에서 사용되었을 때 그 유용성이 드러납니다.
키워드: Array의 문제점 해결, 다음 원소 기억, 삽입/삭제 O(1), 조회 O(N), 트리
Stack
선형 자료구조의 일종으로 후입선출(FILO)방식 즉, 나중에 들어간 원소가 먼저 나오는 구조입니다.
Array와 Linked List로 구현할 수 있습니다.
Queue
선형 자료구조의 일종으로 선입선출(FIFO)방식 즉, 먼저 들어간 원소가 먼저 나오는 구조입니다. 참고로 Java Collection 에서 Queue 는 인터페이스이고 이를 구현하고 있는 Priority queue등을 사용할 수 있습니다.
Array와 Linked List로 구현할 수 있습니다.
키워드: FIFO, 인터페이스, 배열/Linked List로 구현
Priority Queue (우선순위 큐)
우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다.
우선순위 큐 구현 방식에는 배열, 연결 리스트, 힙이 있고, 그중 힙 방식이 worst case라도 시간 복잡도 O(logN)을 보장하기 때문에 일반적으로 완전 이진트리 형태의 힙을 이용해 구현합니다.
키워드: 순서 상관X
Tree
트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이고 계층적 관계(Hierarchical Relationship)를 표현하기에 적합합니다.
트리에서는 각 층별로 숫자를 매겨서 이를 트리의 Level(레벨)이라고 한다.
레벨의 값은 0 부터 시작하고 따라서 루트 노드의 레벨은 0 이다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 한다.
모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리라고 한다.
위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 한다.
모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리를 가리켜 정 이진 트리라고 한다.
키워드: 비선형 자료구조
Heap
Heap은 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로,
각 노드의 키값이 자식의 키값보다 작지 않거나(최대힙) 그 자식의 키값보다 크지 않은(최소힙) 완전이진트리 입니다.
Binary Tree
이진 트리 혹은 binary tree 는 하나의 노드가 최대 2개의 자식을 가지는 트리 자료구조를 의미합니다.
키워드: 최대 자식 2개
BST (Binary Search Tree)
왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 이진트리가 이진 탐색 트리입니다.
이진 탐색 트리는 삽입, 검색, 삭제가 모두 트리의 높이인 logN에서 N만큼의 시간 복잡도를 갖습니다. 그래서 트리가 편향되지 않기위해
자가 균형 트리를 사용합니다.
자가 균형 트리
이진 탐색 트리는 시간 복잡도가 트리의 높이에 따라 결정되므로 편향될 경우 효율이 떨어집니다. 그래서 편향되지 않게 삽입과 삭제를 개선한 이진 탐색 트리를 자가 균형 트리라고 합니다. 자가 균형 트리로는 AVL 트리와 Red-Black 트리가 있습니다.
Red-Black 트리
Red-Black Tree는 이진 탐색 트리를 기반으로하는 트리 형식의 자료구조입니다. Red-Black Tree 에 데이터를 저장하게되면 탐색, 삽입, 삭제에 O(logN)의 시간 복잡도가 소요됩니다.
Hash
해시는 해시에 매핑하여 데이터를 저장하는 자료구조입니다. Key는 Hash Function을 통해서 해시로 변경된 다음에 Value와 매핑되어서 Bucket에 저장됩니다. 시간복잡도는 삽입, 삭제, 조회가 모두 O(1)의 시간 복잡도를 갖습니다.
좋은 Hash Function(해시 함수)
일반적으로 좋은 해시 함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고 키 전체를 참조하여 해쉬 값을 만들어 냅니다.
해시 함수를 무조건 1:1 로 만드는 것보다 충돌을 최소화하는 방향으로 설계하고 발생하는 충돌에 대비해 어떻게 대응할 것인가가 더 중요합니다. 충돌이 많아질 수록 탐색에 필요한 시간 복잡도가 O(1)에서 O(n)에 가까워지기 떄문입니다. 고로 좋은 해시 함수를 선택하는 것은 해시 테이블의 성능 향상에 필수적입니다.
Open Address 방식 (개방 주소법)
개방 주소법은 해시 충돌이 발생하면, 다른 버킷에 해당 원소를 삽입하는 방식입니다.
방법: 순차 탐색, 2차 함수, 2차 해시 함수
Separate Chaining (분리 연결법)
분리 연결법은 버킷에 원소 하나를 담는 것이 아니라 Linked List 혹은 Tree를 담는 방식입니다.
Tree는 기본적으로 메모리 사용량이 많기에 데이터가 적을때는 Linked List를 많을때는 Tree를 사용합니다.
데이터가 많고 적음의 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수입니다. 이 키-값 쌍의 개수 6개, 8개를 기준으로 결정합니다. 7이 없는 이유는 변경하는데 소요되는 비용을 줄이기 위함입니다.
B-Tree
B-Tree는 이진 트리와는 다르게 하나의 노드에 많은 정보를 가지거나, 두 개 이상의 자식을 가질 수도 있습니다.
데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조 입니다.
Graph
그래프(Graph)는 연결되어있는 원소간의 관계를 표현한 자료구조입니다. 정점(Vertex)과 정점을 연결하는 간선(Edge)의 집합으로 구성됩니다. 인접 행렬 혹은 인접 리스트를 사용하여 그래프를 구현할 수 있습니다.
Minimum Spanning Tree (최소 신장 트리)
최소 신장 트리는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리입니다.
Array와 ArrayList의 차이점
Array는 크기가 고정적이고, ArrayList는 크기가 가변적입니다.
Array는 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르고,
ArrayList는 데이터 추가 및 삭제 시 메모리를 재할당하기 때문에 속도가 Array보다 느립니다.
Hash Map과 Hash Table의 차이점
Hash Table은 Thread-safe하고 Key값에 Null 값을 허용하지 않습니다.
Hash Map은 Thread-safe하지 않고 Key값에 Null 값을 허용합니다.