두 노드 사이의 관계가 있는 경우 에지로 연결하여 표현하는 추상적이고 일반적인 자료구조 단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다. Ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목 등 그래프는 여러 개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수 있다. 기본 구성 노드(node), 정점(vertex): 그림에서 노란 동그라미 에지(edge), 링크(link): 그림에서 갈색 선 그래프의 종류 무방향 그래프 그림에서 왼쪽 그래프 방향이 없다 방향 그래프 그림에서 오른쪽 그래프 방향이 있다 그래프의 표..

B-Tree 하나의 노드에 여러 자료(데이터)가 배치되는 트리 구조 스스로 균형을 맞추는 트리 --> 최악의 경우에도 O(logN)의 검색 성능을 보인다. 한 개의 노드에 M개의 자료가 배치되면 M차 B 트리라 한다 규칙 - 노드의 자료수가 n이라면, 자식 수는 n+1 - 각 노드의 자료는 정렬된 상태 - root노드는 적어도 2개 이상의 자식을 가짐 - root노드 제외 모든 노드는 적어도 M/2개의 자료를 가짐 B+ Tree 색인 구조에서 순차 접근에 대한 문제의 해결책으로 제시 key값이 leaf node와 leaf의 부모 노드에 공존 B-Tree의 변형 구조로 index부분과 leaf노드로 구성된 순차 data부분으로 이루어짐 index 부분의 key값은 leaf에 있는 key값을 직접 찾아, 모..

red-black 트리는 binary 트리의 일종, 균형 잡힌 tree, 가장 유명하다. Red - Black Tree의 조건 모든 노드는 red 혹은 black의 색깔을 가지고 있다. root 노드는 무조건 black이다. leaf(None) 노드는 black이다. red 노드의 child는 모두 black이다. black노드의 자식 색깔은 상관이 없다. 각 노드에서 leaf node 까지 갈 때의 black 노드 수가 항상 같아야 한다. Red - Black Tree의 사실 및 증명 h(v) = v의 높이(height) bh(v) = v에서 leaf node까지 v를 제외한 black노드의 개수 사실 1. v의 서브 트리의 내부 노드 수 >= 2^bh(v) - 1 사실 2. h = O(logn) re..

해시 테이블 Hash Table: Key와 Value를 1:1로 매핑시켜, Key를 통해 Value값을 도출한다. Hash Table은 매우 빠른 평균, 삽입, 삭제, 탐색 연산을 제공한다. 해시 함수 key ---f(key)---> index: f(x)는 해시함수이다. 해시함수의 역할: key값을 작은 범위의 값인hash로 변경한다. hash는 저장소에 value와 매핑되어 저장된다. 해시함수의 종류와 특징 충돌(collision): 서로 다른 여러 key값이 동일한 hash값으로 결과가 되는 경우 - 충돌을 막기 (최소화 하기) 위한 hash function이 필요하다. open addressing - 추가 메모리 공간의 사용 없이, 기존 메모리 공간을 이용한다. - 충돌이 발생했을 때, 빈 공간에 ..

1. 배열과 리스트 배열과 리스트는 가장 기본적인 순차적(sequential) 자료구조 [매우 기본, 중요] 2, C언어 int A [4] = {2, 4, 0, 5}; 2 4 0 5 ex) A[2]의 주소 : RAM --> 주소 찾아갈 수 있다 A[0]의 주소 +2 * 4 bytes 3, Python : list - 객체는 따로 메모리 주소를 가리킨다. 객체가 새로 생겨서 그 주소를 가리킨다. - index로 임의의 원소를 접근 - 연산자 []: A[2]:-1 - 삽입: append , insert --> O(1) - 삭제: pop--> O(1), remove --> O(n) 4, 리스트 용량 자동 조절(Dynamic Array) C 에서 int A[4] = {2, 4, 0, 5} A 2 4 0 5 A[..

1. 힙: 힙 성질(heap property)을 만족하는 이진 트리 - 힙은 자식이 꽉꽉 채워져 있어야 한다. 그렇다면 힙성질이란? - 힙 성질: 모든 부모 노드의 key값은 자식 n노드의 key값 보다 작지 않다. 즉 부모님이 자식보다 더 크다! 그렇다면 root노드의 값이 가장 크다! 2. 트리를 표현하는 방법 중 리스트를 이용하여, 모든 노드를 빈 곳도 다 작성하는 방법 사용시 - 단점: 메모리 낭비가 심하다.(비어있는 곳도 None으로 저장) - 장점: 자식 노드와 부모 노드의 위치를 알 수 있다. ex) H = [a, b, c, None, d, e, f] 일때, H[k]의 왼쪽 자식 노드 : H[k*2+1] H[k]의 오른쪽 자식 노드 : H[k*2+2] H[k]의 부모 노드 : H[(k-1)/..