CS

1. 그래프의 개념 그래프 G는 두 개의 집합 V와 E로 구성 V : node 혹은 vertex E : node 쌍을 연결하는 edge -> V(G)와 E(G)는 그래프 G의 정점들의 집합과 간선들의 집합을 나타냄. -> 개체들 간의 이진관계 표현 V = {1,2,3,4,5,6,7,8} E = {(1,2), (1,3), (2,3), .. , (7,8)} n = |V| = 8 m = |E| = 11 그래프의 종류에는 2가지가 있다. 방향그래프(Directed Graph) G = (V,E) : edge (u,v)는 u->v 가중치 그래프(Weighted Graph) : edge 마다 가중치 지정 2. 그래프의 표현 * 무방향 그래프 1) 인접행렬 (adjacency matrix) : n x n 행렬 A = ..

1. 해쉬테이블- dynamic set을 구현하는 효과적 방법 중 하나- 평균 탐색, 삽입, 삭제 시간은 O(1)- 최악의 경우 Θ(n)- 해쉬함수 h를 이용해 키 k를 T[h(k)]에 저장- h : U -> {0, 1, ..., m-1} (m : 테이블 크기, U : 모든 가능한 키들의 집합)- 하나의 slot 혹은 bucket으로 사상됨- 즉, 각 키는 0 ~ m-1의 정수로 mapping  2. 해쉬 함수의 예- 모든 키를 자연수로 가정예1) 문자열ASCII 코드 : C = 67, L = 76, R = 82, S = 83CLRS = (67 * 128^3) + (76 * 128^2) + (82 * 128^1) + 83 * (128^0) 예2) h(k) = k % m : key를 m으로 나눈 나머지  ..