Array
논리적 순서, 물리적 순서 동일 index로 접근가능, index를 알면 O(1) 랜덤 엑세스 가능
삽입 삭제 후 옮겨주는 과정으로 O(n)
Linked List
자신 다음이 누군지만 알고 있다
삽입 삭제 O(1), 특정 원소 찾기에 O(n)
하지만 트리의 근간이 된다!
Stack
LIFO 나중에 들어온 원소 먼저 나감
Queue
FIFO 먼저 들어온 원소 먼저 나감
Tree
비선형구조 노드, 간선, 루트노드, 단말노드, 비단말노드로 구성
이진트리
트리 중에서도 자식이 최대 2명가능한 트리
레벨의 모든 노드가 있다면 포화 이진트리
위에서 아래 왼쪽에서 오른쪽으로 채워지면 완전 이진트리
모든 노드의 자식이 0아니면2라면 정 이진트리
배열로 만든다면 root=1, i기준 (i/2 : 부모), (왼쪽자식 : 2i), (오른쪽자식 : 2i+1)
BST
특정 데이터 위치를 찾는데 효율적인 방법
규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
규칙 2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
규칙 3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
규칙 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
탐색 연산 시 O(log n) 정확히는 O(h)
하지만 저장 순서를 맞추다보면 한쪽에만 쏠리는 편향트리가 될 수 있다. 그러면 메모리와 시간복잡도에서 결국 손해를 본다. 이것을 해결하기위해 다시 트리를 조정하는 Rebalancing 필요
Binary Heap
배열+완전이진트리 최대힙 최소힙존재 최대힙은 루트가 제일 큰 수 최소힙은 반대
RBT
- 각 노드는 Red or Black이라는 색깔을 갖는다.
- Root node 의 색깔은 Black이다.
- 각 leaf node 는 black이다.
- 어떤 노드의 색깔이 red라면 두 개의 children 의 색깔은 모두 black 이다.
- 각 노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 모두 같은 수의 black nodes 들을 포함하고 있다. 이를 해당 노드의 Black-Height라고 한다.
특징 :
1. BST특징을 가진다
2. Root node 부터 leaf node 까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2 보다 크지 않다. 이러한 상태를 balanced 상태라고 한다.
3. 노드의 child 가 없을 경우 child 를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL 들을 leaf node 로 간주한다.
Hash Table
내부적으로 배열사용 index접근을 통해 복잡도 O(1) 하지만 저장되는 key가 불규칙하다.
그래서 불규칙을 탈피하고자 특별한 알고리즘(해시 함수)을 이용해 인덱스로 사용한다.
해쉬함수 역할을 불규칙한 key를 특정 작은 범위의 값들로 바꾼다는 것이다.
하지만 완벽한 해쉬 함수는 없는 법 동일 key에 여러값이 들어가버리는 Collision이 일어난다.
좋은 해쉬함수는 Collision이 없는것이 아니라 Collision최소화 하는것이다.
1대1로 대응되는 key는 사실상array와 다를것이 없기 때문이고 메모리도 많이 차지한다.
Collision 해결법
1. 개방주소법
만약 Collision 발생하면 다른 버킷에 해당 데이터 저장
- 분리 연결법
만약 Collision 발생하면 해당 버킷에 리스트에 추가하는 방식으로 링크드 리스트, Tree로 구현할 수 있다.
그래프
정점과 간선의 집합 방향성에 따라 나뉜다. 각 간선에 연결된 간선 개수는 디그리이다.
표현법은 인접행렬과 인접리스트이다.
탐색법
1. 깊이 우선 탐색 : 한정점으로만 이동 Stack사용
2. 너비 우선 탐색 : 한정점에서 모든 정점으로 이동 Queue사용
미로찾기
가중치가 가장 작은 사이클 없는 형태 찾기
1. Kruskal Algorithm : 간선을 정렬하고 작은거 부터 순서대로 채운다. 단 사이클 생기지 않도록
사이클 판단은 연결할 때마다 set-id를 하나로 통일시키는데, 값이 동일한 set-id 개수가 많은 set-id 값으로 통일시킨다.
- Prim Algorithm : 한 개의 vertex 로 이루어진 초기 그래프 A 를 구성한다. 그리고나서 그래프 A 내부에 있는 vertex 로부터 외부에 있는 vertex 사이의 edge 를 연결하는데 그 중 가장 작은 weight 의 edge 를 통해 연결되는 vertex 를 추가한다.
