자료구조 with 윤성우
-
Chap 11. 그래프자료구조 with 윤성우 2021. 1. 30. 03:29
정점 : 연결의 대상이 되는 개체 또는 위치 간선 : 정점 사이의 연결 - 무방향 그래프 연결 관계에 있어서 방향성이 없는 그래프 - 방향 그래프 간선에 방향정보가 포함된 그래프 - 완전 그래프 각각의 정점에서 다른 모든 정점을 연결한 그래프 - 가중치 그래프 간선에 가중치 정보를 두어서 그래프를 구성 ex) 두 정점 사이의 거리 - 부분 그래프 그래프의 일부 정점 및 일부 간선으로 이루어진 그래프 - 무 방향 그래프 정방 행렬 - 방향 그래프 정방 행렬 - 무방향 그래프 연결리스트 - 방향 그래프 연결리스트 ex) 비상 연락망 - 한 사람에게만 연락한다. - 연락할 사람이 없으면, 자신에게 연락한 사람에게 알린다. - 처음 연락을 시작한 사람의 위치에서 연락은 끝이 난다. - 보낼 수 있는 사람 모두에..
-
Chap 10. 테이블과 해쉬자료구조 with 윤성우 2021. 1. 30. 03:08
해쉬 테이블은 빠른 탐색을 한다. 하지만, 트리의 언급은 없다. 테이블의 탐색 시간 복잡도는 O(1)을 나타낸다. 저장하는 데이터에 대하여 키와 값으로 하나의 쌍을 이룰 경우에 테이블이라 칭한다. 키는 유일해야한다. 키가 존재하지 않는 값은 존재할 수 없다. 테이블의 문제점 - key의 범위가 배열의 인덱스 값으로 사용하기에 적당하지 않을 수 있다. - key의 범위를 수용할 수 있는 매우 큰 배열이 필요하다. 위 두가지 문제를 해결해주는 '해쉬 함수'가 존재한다. '해쉬 함수'는 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 한다. '충돌' 이란 해쉬 함수를 통과하였는데, 키의 값이 동일한 경우를 나타낸다. '충돌'은 피하는게 아니라, 해결을 해야한다. 좋은 해쉬 함수 - '충돌'이 발생활 확률이..
-
Chap 09. AVL(균형 잡힌 이진 트리)자료구조 with 윤성우 2021. 1. 30. 02:51
이진 탐색 트리의 시간 복잡도는 O(log2N)이다. 하지만 균형이 맞지 않다면 O(N)에 가까워진다. ==>> 높이가 중요함. 시간 복잡도는 애초에 높이에 의해 결정되었기 때문이다. 따라서, '균형 잡힌 이진 트리'를 AVL이라고 한다. * 노드가 추가될 때, 노드가 삭제될 때 스스로 그 구조를 변경하여 균형을 잡는다. 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 '균형 인수'의 절댓값이 2 이상 ==>> 균형이 무너졌다. '균형 인수'가 무너진 경우 LL상태 자식 노드 두 개가 왼쪽으로 연이어 연결되어 '균형 인수'가 2이상이다. RR상태 자식 노드 두 개가 오른쪽으로 연이어 연결되어 '균형 인수'의 절댓값이 2 이상이다. LR상태 자식노드가 왼쪽으로 하나, 그 자식 노드의 오른..
-
Chap 08. 탐색자료구조 with 윤성우 2021. 1. 30. 02:41
탐색 : 데이터를 찾는 방법 탐색이 효율적이기 위해서는 효율적인 '저장방법'을 고려해야한다. 대표적으로 '이진 트리'가 효율적이다. 이진 탐색 - 탐색 대상을 반으로 줄여나가면서 탐색 - '찾는 대상의 위치에 따라 탐색의 효율에 차이가 발생'한다. 이진 탐색의 단점을 보완한 탐색이 보간탐색. 보간 탐색 - 대상에 비례하여 탐색의 위치를 결정 '이진 탐색'보다 '보간 탐색'이 더 효율적이다. 내가 찾고자 하는 데이터의 값에따라 탐색위치를 정해준다. low : 배열의 시작 인덱스 high : 배열의 마지막 인덱스 s : 찾고자하는 값의 배열 인덱스 배열의 값들이 정렬되어 있다면, 이진 트리에 저장된 데이터의 수가 10억개라면, 거치는 노드의 수는 30을 넘지 않는다. 이진 탐색 트리 = 이진 트리 + 데이터..
-
Chap 06. 우선순위 큐자료구조 with 윤성우 2021. 1. 29. 17:00
배열의 단점 - 데이터를 '삽입' 및 '삭제'하는 과정에서 데이터를 한 칸씩 이동하는 연산이 필요하다. - '삽입의 위치'를 찾기 위해 모든 데이터와 비교하여야한다. 연결리스트의 단점 - '삽입의 위치'를 찾기 위해 모든 데이터와 비교하여야한다. 위의 단점들을 보완하기 위해 우리는 '완전 이진 트리'인 힙을 사용하여야한다. ● 배열과 연결리스트의 단점이 '힙'에는 존재하지 않는다. ● 완전 이진 트리 (차곡 차곡 데이터를 쌓는 트리) ● 모든 노드에 저장된 값의 우선 순위는 자식 노드에 저장된 값의 우선순위보다 크거나 같아야한다. = 루트 노드가 우선순위가 높아야 한다. 배열과 연결리스트에서는 삽입을 하기 위해서는 삽입하는 데이터와 저장되어있는 데이터와 모두 비교를 해야한다. 하지만 은 1. ..
-
Chap 05. 트리자료구조 with 윤성우 2021. 1. 29. 16:21
트리는 '계층적 관계'를 표현하는 자료구조이다. 트리는 '비선형' 자료구조이다. ● 노드 : 트리의 구성 요소에 해당하는 요소 ● 간선 : 노드와 노드를 연결하는 선 ● 루트 노드 : 트리에서 최상위에 존재하는 노드 ● 단말 노드 : 아래로 다른 노드가 연결되어 있지 않는 노드 ● 부모 노드 : 연결된 노드 중 상위에 있는 노드 ● 자식 노드 : 연결된 노드 중 하위에 있는 노드 ● 형제 노드 : 부모 노드가 같은 노드 서브 트리 : 하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리 서브 트리또한 서브트리로 이루어져 있다.(재귀적인 관계) 이진 트리의 조건 ● 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 진다. ● 나뉘어진 두 서브 트리 모두 이진 트리어야한다. (재귀적) 트리는 루트노드부터 lev..
-
Chap 04.큐(Queue)자료구조 with 윤성우 2021. 1. 26. 13:06
먼저 들어간 것이 먼저 나오는 First In First Out = FIFO ex) 줄서기 typedef struct_lQueue { Node* front; Node* rear; }LQueue;//연결리스트 typedef struct _cQueue { int front; int rear; Data queArr[QUE_LEN]; }CQueue;//배열 rear - 입구를 나타내는 인덱스/노드 front - 출구를 나타내는 인덱스/노드 데이터 저장(enqueue) 하면 rear 이 이동 데이터 삭제(dequeue) 하면 front 가 이동 ● 큐(배열)의 문제점 비어있는 배열이 있지만, R이 오른쪽으로 이동할 수가 없다. 따라서, 이런 단점을 보완하기 위해 '원형 큐'가 도입되었다. ● 원형 큐의 문제점 R..