오래 못 할 짓 하지 않기

해밀턴 경로 (Path) = 그래프에서 모든 정점을 한 번만 지나는 경로 해밀턴 순환 (Circuit) = 시작과 끝점이 같은 해밀턴 경로 = 모든 vertex를 한 번만 지나서 순회가 가능한 경 아래 3개가 해밀턴 경로인지 봐라 - G1 = ㅇㅇ 해밀턴 Circuit - G2 = a가 막다른 길이라 Circuit은 안 됨. 대신 막다른 길에서 끝내서 Path로 만드는 건 가능. ( * 막다른 길이면 순회가 안 됨 b에서 a갔다가 순회하려면 다시 b를 밟아야 한다 ) - G3 = Circuit / Path 둘 다 안 됨 예제2) Shortest Path Problems 이해해야 하는 거 : Dijkstra Algorithm 시작점에서부터 이어져 있는 가장 짧은 다리들로 이동하면 최단 경로가 된다. 모든 ..

Path Path ( 경로 ) : 인접한 vertex간 연결되어있는 길 * n개의 vertex로 연결된 path는 n-1개의 edge가 있다. = 경로의 길 1) a - d - c - f - e 각 vertex 순서대로 이동하는 경로가 있고, vertex는 5개, 그 경로의 길이는 4 2) 이건 e > c edge가 없음 3) 이거도 1)이랑 같게 생각하면 됨 4) 길이는 5가 맞는데 한 번 갔던 edge 또 밟으면 simple path가 아니다. Connectedness : 특정 vertex 두 개를 기준으로 Path가 존재할 때 connected라고 한다. connected component 이지, connected graph가 아님 ● Cut Vertices : 1개의 vertex를 없앴을 때 di..

Adjacency List Adjacency(인접) : 해당 vertex와 Edge하나로 이어져있는 관계를 뜻한다. ● Simple graph : [ Vertex - Adjacent vertices ] 관계로 이루어져있다. ● Directed graph : [ Initial vertex - Terminal vertices ] 관계로 이루어져있다. 행렬을 통한 그래프 표현 • Adjacency matrix : 행과 열이 Vertex로 이루어져있다 + 두 vertex가 인접하면 1, 아니면 0 1) n*n matrix이다. 아래 그래프가 어떤 성향을 띄고있는지 분석해보자 0,1이 아닌, edge의 개수로 나타내는 matrix도 가능하다 *참고 ● Directed 는 ( a, b )= 순서 중요 ● Undir..

그래프 : 인접 Adjacent G = ( V , E ) 에서 꼭짓점 u,v를 연결한 모서리 e가 있을 때 u와 v는 서로 인접하다고 말한다. Multi 그래프 : 두 vertex ( node) 사이에 두 개 이상의 Edge가 있는 그래프 참고 : pseudograph = Multi 그래프 + loop Direct 그래프 화살표로 모서리를 표현 , Vertex간의 순서나 관계를 알 수 있다. Direct Multi 그래프 Direct에다가 Multi. 즉 화살표로 표시된 edge가 두 vertex 사이에 두 개 이상 있는 것. 그래프들의 특징 분석 1) 두 개의 vertex가 edge하나로 연결되어 있을 때, 두 vertex는 'adjacent' or 'neighbors'라고 한다. 2) Vertex v..

Equivalence Relations : 집합 A가 [ Reflexive + Symmetric + Transitive ] 하다면, Equivalence하다 고 한다. 출처 ) https://www.youtube.com/watch?v=pR89T9SPFX4&t=938s 예제 1) (a,b) | a ≡ b( mod M) , 즉 [ a를 m으로 나누었을 때 나머지= b를 m으로 나누었을 때 나머지 ] 이다. * a-b 를 m으로 나누었을 때 0이면 됨 ● Reflexive : a ≡ a (mod m) a - a = 0 은 m으로 나눴을 때 0이므로 ㅇㅋ ● Symmetry : a - b 가 m으로 나누어질 때, a-b = km으로 표시할 수 있다. b- a = (-k)m으로 될 것. ● Transitive :..

Relations with Matrix Matrix로 R을 나타내려면, Zero-one matrix로 한다. 해당 원소가 존재하면 1, 그렇지 않으면 0으로. A = {1,2,3} and B = {1,2} 가 있고, R은 A → B이다. R = (a,b)형태이고 a ∈ A, b ∈ B이다. R의 조건은 a>b이다. 그런 경우 R의 원소는 {(2,1), (3,1),(3,2)} 이다. 예제) 이거 보고 몇 번째 원소들이 있는지도 파악 가능해야함 종류별 R의 Matrix 모양 Reflexive : 그냥 대각선으로 1 쭈루루룩 Symmetric : (a,b)가 있으면 (b,a)도 있어야 함 반대로 (a,b)가 없으면 (b,a)도 없어야함 위와 같은 형태 Antisymmetric : (a,a)빼고는 대칭인 거 있..

Binary Relations : 집합 A와 B를 가지고 만들 수 있는 관계들을 모은 것 = R Binary 라는 뜻은 A와 B 안에 있는 원소가 있을 수도, 없을 수도 있다는 의미로 해석하면 된다. A = {0,1,2} B = {a,b} 일 때, A*B = {(0, a), (0, b), (1, a), (1, b) (2,a) , (2, b)}이지만 R은 모두 다 가지고 있을 필요가 없다. R= {(0, a), (0, b), (1,a) , (2, b)} 이런 식이다. 따라서 해당 관계는 아래와 같이 표현할 수 있다. 아마 R의 최대값(?)은 A*B와 같을 때 일 것이다. 아래 원소를 가질 수 있는 R은? 이런 것도 풀 수 있어야 한다. n개의 원소가 있는 set A에서 나올 수 있는 R의 개수는? =>1)..

기댓값 확률변수 X가 취하는 값 x1, x2, ... , xn에 대한 확률분포가 p1, p2, ... , pn일 때, 평균을 구하면 E(X) = x1p1 + x2p2 + ... + xn*pn X를 주사위를 던졌을 때 나오는 숫자라고 해보자 X의 기댓값은? [1부터 6까지 ] → (n) * ( n이 나올 확률 ) 동전을 3번 튕겼을 때 나올 수 있는 경우에서, 확률변수 X를 Head 면이 나온 횟수라고 하자. X의 기댓값은? 가능한 경우의 수 3개: HHH 2개 : HHT,HTH, THH 1개 : HTT,THT,TTH 0개 : TTT 이렇게 되어 있을 때, 3개일 때는 하나의 경우만 나오므로 1/8 1, 2개일 때는 3개의 경우이므로 3/8 0개일 때는 하나의 경우이므로 1/8 => ( 3 * 1/8 ) ..

Bayes’ Theorem p(E) ≠ 0 and p(F) ≠ 0 일때, 위 식이 성립한다. 이 식은 사실 = p( E and F ) / p( E and F ) + p( E and ~F ) // p( E and F ) + p( E and ~F ) = p( E ) 이와 같다. 예제 ) 박스 A = 초록공 2개 + 빨간공 7개 박스 B = 초록공 4개 + 빨간공 3개 이 때 하나를 뽑아서 빨간공이 나올 확률을 구하는 것이다. E = 빨간공 선택 F = A박스 선택 우리는 p( F | E ) 를 구할 것이다. 우선 빨간공이 나오는 경우의 수는 1) 박스 A → 빨간공 (7/9) 2) 박스 B → 빨간공 (3/7) 이 있다. 따라서 p( 빨간 공인데 | 첫 번째 박스를 골랐을 때 ) = p( 박스 A 빨간공 )..

확률은 주로 - A가 일어날 확률 = [ A가 일어날 경우의 수 / 전체 경우의 수 ] 이런 형태이다. 경우의 수에 선택지가 2개 외에는 없을 때 E' = 1 - E 이렇게 해석된다. (아래 예시에서 S는 전체 경우의 수) 예제1) 10비트 칸이 있을 때, 적어도 하나는 0일 확률은? 풀이) 더보기 E = 적어도 하나는 0인 경우 ~E = 모두 1인 경우 따라서 " 1 - 모두 1일 확률 = 적어도 하나는 0인 경우 " --> 모두 1일 확률 = 모두 1인 경우의 수 / 전체 경우의 수 경우의 수에 선택지가 2개보다 많을 때 그냥 집합의 덧셈과 같다. 각 확률에서 더하다 보니 중복해서 들어가는 부분이 있기 때문에 그 값을 한 번은 빼준다. 예제) 100 이하의 랜덤 숫자로 뽑았을 때 2나 5로 나눠지는 ..