Array vs Linked List
Array
가장 기본적인 자료구조인 Array 자료구조는, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스(index)로 해당 원소(element)에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 BIG-O(1)에 해당 원소로 접근할 수 있다.
하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤 (O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생기는 것이다.
따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift 해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)가 된다. 그렇게 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity의 worst case는 O(n)의 시간을 요구하게 된다.
Linked List
이 부분에 대한 문제점을 해결하기 위한 자료구조가 linked list이다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 따라서 이부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1) 만에 해결할 수 있는 것이다.
하지만 Linked List 역시 한 가지 문제가 있다. 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search 과정에 있어서 첫번재 원소부터 다 확인해봐야 한다는 것이다.
결국 linked list 자료구조는 search 에도 O(n)의 time complexity 를 갖고 , 삽입 , 삭제에 대해서도 O(n)의 time complexity 를 갖는다.
이 Linked List는 Tree 구조의 근간이 되는 자료구조 이다.
Stack
나중에 들어간 원소가 먼저 나온다
Queue
먼저 들어간 놈이 먼저 나온다.
Tree는 스택이나 큐 같은 선형 구조가 아닌 비선형 자료구조이다.
트리를 구성하고 있는 구성요소들
Node: 트리를 구성하고 있는 각각의 요소를 의미함
Edge: 트리를 구성하기 위해 노드와 노드를 연결하는 선
Root Node: 트리 구조에서 최상위에 있는 노드를 의미
Terminal Node: 하위에 다른 노드가 연결되어 있지 않은 노드를 의미
Internal Node: 단말 노드를 제외한 모든 노드로 루트노드를 포함한다.
Binary Tree (이진트리)
루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.
BST (Binary Search Tree)
효율적인 탐색을 위한 저장방법
이진 탐색 트리에는 데이터를 저장하는 규칙이 있다.
1. 이진 탐색 트리의 노드에 저장된 키는 유일하다
2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
3. 부모의 키가 오른쪽 자식 노드의 키보다 작다
4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
이진 탐색 트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖는다
Hash Table
hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다
특정한 값을 Search 하는데 데이터 고유의 인덱스로 접근하게 되므로 average case에 대하여 Time Complexity가 O(1)이 되는 것
Graph
정점과 간선의 집합 , Graph
트리 또한 그래프이며, 그 중 사이클이 허영되지 않는 그래프를 말한다.
그래프를 구현하는 두 방법
인접 행렬
인적 리스트
깊이 우선 탐색 (Depth First Search: DFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다라는 방법을 우선으로 탐색한다. 일단 연결된 정점으로 탐색하는 것이다. 연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더이상 연결되지 않은 정점이 없으면 바로 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 살펴봐야 할 것이다. 갔던 길을 되돌아 오는 상황이 존재하는 미로찾기처럼 구성하면 되는 것이다. 어떤 자료구조를 사용해야할까? 바로 Stack 이다. Time Complexity : O(V+E) … vertex 개수 + edge 개수
너비 우선 탐색 (Breadth First Search: BFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. Tree 에서의 Level Order Traversal 형식으로 진행되는 것이다. BFS 에서는 자료구조로 Queue 를 사용한다. 연락을 취할 정점의 순서를 기록하기 위한 것이다. 우선, 탐색을 시작하는 정점을 Queue 에 넣는다.(enqueue) 그리고 dequeue 를 하면서 dequeue 하는 정점과 간선으로 연결되어 있는 정점들을 enqueue 한다. 즉 vertex 들을 방문한 순서대로 queue 에 저장하는 방법을 사용하는 것이다.
Time Complexity : O(V+E) … vertex 개수 + edge 개수
! 모든 간선에 가중치가 존재하지않거나 모든 간선의 가중치가 같은 경우, BFS 로 구한 경로는 최단 경로이다.
