기술 블로그

두 개의 정점이 두어졌을 때 v = (p1, p2, p3) 를 가지고 있고 w = (q1, q2, q3)를 가지고 있을 때 v정점과 w정점의 특성이 있을 때 차별성 함수는 다음과 같이 계산을 할 수 있습니다.  차별성 함수 값은 v와 w 간의 차이를 나타내는 척도가 됩니다.  N이라는 값을 하나 고정을 시키는데 이 값을 고정시키고 나면 간선을 표기할 때 s(v,w)  두 정점 v와 w 사이의 간선이 있다라는 것은 같은 클래스에 속한다는 것입니다. 이는 두 프로그램은 같은 클래스로 정의될 수 있다는 것입니다.  완전그래프완전그래프 Kn은 n개의 정점을 가진 심플 그래프라고 볼 수 있습니다. 한가지 특징은 하나의 간선으로 모든 정점이 결합되는 것을 완전그래프라고 합니다. 즉 모든 정점이 하나의 간선으로 연결..

스패닝트리그래프 G가 주어졌을 때 트리 T는 그래프 G는 신장 트리입니다.T가 그래프 G의 서브그래프이고T가 G의 모든 정점을 포함할 때이런 경우 스패닝 트리라고 합니다. 그래프의 모든 정점을 포함하는 트리라고 보면 됩니다.  최소스패닝트리가중치 그래프 G가 주어졌을 때 제일 첫 번째 단계에서는 시작 정점을 하나 선택을 합니다. 우리가 찾으려고 하는 스패닝트리에 이 시작 정점이 추가됩니다. Kruskal's algorithm이 간선이 1의 가중치를 가지기 때문에 선택이 됩니다. 나머지 간선들 중에 역시 가장 작은 간선이 계속적으로 선택이 되고 싸이클을 생성하지 않는 간선을 계속적으로 선택해나가면 됩니다.  Binary trees이진트리이진트리는 각각의 정점이 0개 또는 1개 또는 2개의 자식을 가지는 루..

그래프란?실생활에서 서로 관련되는 두 가지 또는 그 이상의 양의 관계를 정점과 간선을 이용하여 그림으로 나타낸 것입니다. 그래프는 자료 요소들의 관계가 비선형 구조로 나타날 때 사용되는 자료구조입니다.   각각의 간선 e가 존재하면 e = (v,w) 혹은 e=(w,v)라고 나타냅니다. 여기서 (v,w)는 무방향 그래프에서 정점 v와 w간의 간선을 나타내며 방향이 있는 쌍이 아닙니다.  그래프의 설명그래프 g는 정점의 집합 v와 간선의 집합 E로 구성되어 있고, 각각의 간선 E는 순서가 없는 정점의 쌍으로 나타냅니다.  만약 정점 v와 w를 연결하는 유일한 간선 e가 존재하면 e = (v,w) 또는 e= (w,v)라고 나타냅니다. 여기서 (v,w)는 무방향 그래프에서 정점 v와 w간의 간선을 나타내며 방향..

이진 탐색 알고리즘 13개의 원소를 가진 수열에서 찾고자 하는 값이 35가 있는지를 찾아야 합니다.  해당 위치 index를 반환하고 없으면 0을 반환하면 됩니다. binary_Search 검색 방법을 보면 제일 처음에 중간 index를 계산을 합니다. 시작 index가 1이고 마지막 index가 13이고 이에서 2를 나누면 가운데 값을 찾게 됩니다.  찾고자 하는 값은 key값으로 35입니다. 이 35라는 값이 왼쪽에는 없기 때문에 제외를 하고 오른쪽 부분에서 이진 탐색 부분을 재귀적으로 호출해서 찾으면 됩니다.  이진탐색 알고리즘은 다음과 같습니다.이진탐색의 시간복잡도는 앞에 살펴 본 마스터 정리로 볼 수 있습니다.  합병 정렬의 복잡도

베이즈 정리 다음과 같은 질문 대답-특정 질병을 가진 사람에 대해 양성으로 반응한 사람이 실제로 그 질병에 걸렸을 확률은?-질병에 관해 음성 판정을 받았다면 실제로 그 질병에 걸렸을 확률은? 의학, 법, 인공지능, 공학 등 다양한 분야에 기초적 확률을 기반으로 합니다.  패턴인식이란?항목이 가지는 것에 대해 클래스로 구분을 하는 것입니다. 조건 확률로 계산을 하는 것인데요. 어떤 특성 집합이 구해졌을 때 조건부확률로 구할 수 있는데요. 이와같은 패턴인식에서 사용하는 것이 베이즈 정리입니다. E와 F가 표본공간 S에서의 사건으로 P(E) != 0이고 P(F) != 0이라고 할 때 다음과 같이 성립합니다.  베이즈 정리의 유도는 해당 방식으로 됩니다.  이것은 조건부확률의 정의입니다.  이 조건부확률의 정의..

반복이 허용될 때 n 개 원소를 가진 집합에서 r개를 뽑을 때는 n^r 이 나옵니다. 반복에 의한 조합3개의 책이 있다고 가정해봅시다. (computer science book, physics book, history book) 최소한 6개의 카피본을 선택해야 한다고 가정할 때 얼마나 많은 중복을 가진 것에서 선택을 할 수 있을까요? 이런식으로 book-end 를 사용해서 책을 나눠주면 됩니다.  전체 자리는 8자리로 합니다. 그 다음 8자리에서 해야하는 것은 book-end 위치만 정의를 해주시면 됩니다. book end 위치를 정한다고 생각하면 C(8, 2)로 해주시면 됩니다.  예를 통해서 중복이 허용하는 경우를 생각해보겠습니다.  빨강, 파랑, 녹색 공들이 있을 때 각각의 더미는 8개의 공을 가지..

P(n,r) = n(n-1)(n-2)...(n-r+1) r 예시 100명이 참여한 경품에서 1등, 2등, 3등을 한 명씩 선발하는 방법은 모두 몇 가지 인가?P(100,3) = 970,200 가지입니다.  P(10, 4) = 10 * 9 * 8 * 7 = 5040 조합 (Combinations)n개의 다른 원소로 구성된 집합이 있습니다. r-조합은 r개 원소에 대한 unordered selection입니다. r  r 조합의 개수는 다음과 같이 표기할 수 있습니다 .C(n,r) 대각선을 그었을 때 대각선 위로 이동하지 않는 개수는 어떻게 될까요? - Gn + Bn = C(2n, n)좋은 경로의 개수는 나쁜 경로를 빼주면 되는데요. Bad route의 개수는 (n+1) * (n-1) grid가 되는데요.이는..

곱셉의 법칙이와 같은 메뉴를 보고 각각 하나를 주문하고 싶다고 생각을 해봅시다. 이 경우에 3 * 3 * 4 = 24개가 될 것입니다.  원소가 m개의 집합에서 원소가 n개인 집합으로의 1대1 함수m > n : 1 대 1 함수가 존재할 수 없습니다.m 결국 가능한 모든 가지 수는 n(n-1)(n-2) ... (n-m+1) 입니다.  비둘기집 원리4개의 공간에 6개의 공을 넣어야 한다면 우리는 필연적으로 2개 이상의 공이 들어가는 1개 이상의 공간이 있다는 것을 알 수 있습니다.  이것이 처음의 비둘기집의 원리입니다.  n개의 공이 k개의 장소에 들어가야 할 때 k

재귀적이란?어떤 알고리즘이 문제를 보다 작은 입력을 갖는 동일한 문제로 단순화시켜 해결하는 것 분할정복분해된 각각의 하위 문제는 간단한 방법으로 풀릴 수 있는 문제가 될 때까지 계속해서 분해, 마지막으로 분해된 하위 문제들의 해답들은 원래 문제의 해답을 얻기 위해 결합 n! 는 1에서 n까지의 곱으로 정의를 하는 것입니다.  팩토리얼의 알고리즘factorial (n) { if(n == 0) return 1 return n*} n!이 나오는 것을 본다면  1. 기본단계n이 0일 때 0! (=1)을 반환합니다. 2. 귀납단계(n-1)! 일 때 성립한다고 가정 n>0n에 대해서 성립하는지 가정n이 아니면 n * (n-1)! 시행(n-1)! * n = n! n일때 정확하게 n 성립최종적으로 알고리즘..

함수의 증가 함수 f(x)가 g(x)보다 더 빠르게 증가한다면, f(x)는 충분히 큰 x에 대해 항상 g(x)보다 커집니다. 사용자 데이터를 처리하는 웹 사이트를 설계한다고 가정해봅시다. 데이터 베이스 처리를 위해서 프로그램 A는 n개 레코드를 처리하기 위해 fa(n) = 30n+8 microseconds가 걸립니다. 프로그램 B는 n개 레코드를 처리하기 위해 fa(n) = n^2+1 microseconds가 걸립니다. Big - o notation 함수의 order에 대한 big o notation에 대해서 설명하겠습니다. f와 g를 정수의 집합 또는 실수의 집합에서 실수의 집합으로의 함수라고 하자. 만약 x > k 일 때, 다음을 만족하는 상수 c와 k가 존재한다면 f(x)는 o(g(X)) 라고 한다..