728x90 공부164 크루스칼 알고리즘(Kruskal algorithm) 크루스칼 알고리즘에 대해 배워보겠습니다. 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 그니깐 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이죠. 실제로 여러 개의 도시 연결을 위해 도로 건설 최소 비용을 위해 적용되는 알고리즘 입니다. 그래프 용어를 정리해 보겠습니다. 노드 = 정점 = node = 도시 : 그래프에서 동그라미 간선 = 거리 = edge = 비용 : 그래프에서 선 이 그림의 노드 개수는 7개이고 간선의 개수는 11개입니다. 즉 7개의 도시, 11개의 도로인거죠. 크루스칼 알고리즘의 핵심은 다음과 같습니다. 정렬 후 비용이 작은 ( 거리가 짧은) 순서대로 그래프에 포함시키자. 모든 노드를 최소 비용 연결시키는 게 목적이니 모든 노드를 오.. 2020. 6. 4. Union-Find(합집합찾기) Union-Find는 대표적인 그래프 알고리즘 입니다. 바로 '합집합 찾기'라는 이름의 알고리즘인데요. 서로소 집합(Disjoint-Set) 알고리즘이라고도 불리기도 합니다. 여러 개의 노드가 존재할때 두 노드가 같은 집합 안에 속했는지, 즉 연결이 되어있는지를 판별하는 알고리즘 입니다. 다음과 같은 노드셋이 있습니다. 모든 노드가 연결되어 있지 않고 자기 자신만을 집합의 원소로 가지고 있는 때입니다. 모든 값이 자기 자신을 가리키도록 만드는 겁니다. 아래 표에선 첫번째 행은 '노드 번호'를 의미하고 두번째는 '부모 노드 번호'를 의미합니다. 즉, 자기 자신이 어떤 부모에게 포함되어 있는지를 의미합니다. 어차피 한 노드에만 연결되어 있으면 다른 노드에도 연결되어져 있게 되는거니깐요. 여기서 부모노드는 값.. 2020. 6. 4. RSA 안녕하세요. 옆집 컴공생입니다. 정말 유명한 RSA에 대해 이야기 해봅시다. RSA는 1978년, MIT의 Rivest, Shamir, Adleman 세명의 연구로 발명되었습니다. 공개키 암호시스템의 하나로 암호화뿐만 아니라 전자서명이 가능한 최초의 알고리즘입니다. 공개키 스키마로 가장 유명한데요. 보통 1024비트 이상의 큰 정수를 사용합니다. 바로 어떻게 작동하는지 확인해보겠습니다. 그렇게 엄청 어려워보이진 않습니다! (희망적) 물론 이걸 이해하기 위해 앞에서 많은 시간들 할애해 다양한 것들을 배워야합니다. 갈로아필드라든지 페르마 정리 라든지 등등. 평문은 집어넣는거 부터 생각을 해보겠습니다. 평문 P가 C로 암호화가 됩니다. 이때 수신자의 공개키와 n을 이용해 암호화를 합니다. 암호문 Cipher .. 2020. 6. 3. Ch9:Public-key crptography and RSA 오늘은 공개키 암호 중에서도 가장 유명한 RSA에 대해 자세히 알아봅시다. Private-key 전통적인 암호학은 single key를 사용합니다. 암호화,복호화에 모두 하나의 키를 사용하는 겁니다. 만약 이 키가 공개될 경우 비밀성이 깨지게 됩니다. Key distribution problem A B C 와 통신을 위해서는 (A,B) 둘만의 비밀키가 존재해야하고 (B,C),(A,C) 각각 둘만의 비밀키가 존재해야합니다. 그니깐 키를 완전히 분배해야합니다. 제 3자의 둘만이 아는 키를 어떻게 분배할지가 문제점이 됩니다. Public-key 두개의 키가 사용됩니다. 하나는 공개키고 하나는 비밀키입니다. asymmetric(비대칭)인데 이는 암호화할때와 복호화할때 쓰는 키가 다르다는 말입니다. 특징 - 계산.. 2020. 6. 3. 이전 1 ··· 32 33 34 35 36 37 38 ··· 41 다음 728x90
