알고리즘/알고리즘 도감 (44) 썸네일형 리스트형 하노이의 탑 지난 글 : [알고리즘/알고리즘 도감] - 페이지랭크 하노이의 탑은 원반을 이동해 탑을 쌓는 게임이다. 재귀적인 알고리즘을 쉽게 이해할 수 있는 예로 대표적이다. 참고 : [알고리즘/Do it 알고리즘] - 하노이의 탑 1 1 | | 2 | | 3 | | ===== ===== ===== A B C 위 그림에는 A, B, C 세 개의 기둥이 있으며, A 기둥에 3개의 원반이 꽂혀 있다. 이것이 초기 상태다. 3개의 원반을 순서를 유지한 채 C 기둥으로 이동하는 것이 게임의 목적이다. 원반의 이동에는 아래 두 가지 조건이 있다. 1. 한 번에 한개의 원반만 이동할 수 있다. 2. 작은 원반 위에 그것보다 큰 원반을 둘 수 없다. 위 조건 하에 모든 원반을 마지막 기둥으로 이동하는 것이 게임의 목표이며 이 과.. 페이지랭크 지난 글 : [알고리즘/알고리즘 도감] - 소수 판별법 페이지랭크(PageRank)는 검색 사이트에서 검색 결과의 순위를 결정하기 위해 사용되는 알고리즘이다. 1 페이지랭크는 페이지 간의 링크 구조로부터 페이지의 가치를 산출하는 알고리즘이다. 산출까지의 구체적인 과정을 보자. 페이지 / | \ 페이지 페이지 페이지 위 그림에서 세 개의 페이지가 하나의 페이지를 링크하고 있다. 페이지랭크에서는 링크된 수가 많을 수록 중요한 페이지라고 판단한다. 위 표에서는 상위에 있는 페이지가 가장 중요한 페이지라 판단한다. 실제로는 각 페이지의 중요도가 계산에 의해 수치화된다. 기본적인 계산 방법을 보자. 2 페이지 / | \ 1 1 1 링크되지 않은 페이지의 점수를 1이라 하자. 3 / | \ 1 1 1 링크돼 있는 .. 소수 판별법 지난 글 : [알고리즘/알고리즘 도감] - 유클리드 소수 판별법은 특정 자연수가 소수인지 판단하는 방법이다. 소수(prime number)는 1과 자신 이외는 약수로 갖지 않는 1보다 큰 자연수다. 현대 암호 기술에서 자주 사용된다는 'RSA 암호'에서 매우 큰 소수를 다루므로 '소수 판별법'이 중요한 역할을 한다고 한다. 1 113이라는 수가 소수인지를 판별해보자. 단순히 113을 2보다 큰 수로 차례대로 사용하며 나누어지는지 확인하는 방법이 있다. '완전히 나누어진다'는 mod 연산의 결과가 0인 것을 의미한다. 2 하지만 위 방법은 판별할 수가 클수록 많은 시간이 걸린다. 이 문제를 해결하는 방법으로 '페르마 테스트(Fermat test)'가 있다. 3 페르마 테스트는 확률적 소수 판별법이라고 불리.. 유클리드 지난 글 : [알고리즘/알고리즘 도감] - k-means 알고리즘 유클리드(Euclidean) 알고리즘은 두 수의 최대공약수를 구하는 알고리즘으로서 세계에서 가장 오래된 알고리즘으로 유명하다. 언제 발견됐는지는 알 수 없지만, 가장 오래된 기록이 기원전 300년에 작성된 유클리드 필서라는 것에서 유클리드라는 명칭이 붙여졌다. 1 유클리드 알고리즘으로 1112와 695의 최대공약수를 계산하기에 앞서 수기로 계산해보자. 1. 일반적인 방법으로 두 개의 수를 소인수분해해 공통되는 소수를 최대공약수로 구한다. 1112 = 139 X 2 X 2 X 2 695 = 139 X 5 139 = 최대공약수 2. 하지만 이 방법에서는 두 수가 커질수록 소인수분해가 어려워진다. 유클리드 알고리즘에서는 더 효율적으로 최대공약수.. k-means 알고리즘 지난 글 : [알고리즘/알고리즘 도감] - 클러스터링 k-means 알고리즘은 클러스터링 알고리즘의 하나로, k-means 알고리즘에서는 클러스터의 수를 미리 지정해 그 수에 맞춰 그룹을 나눈다. 1 아래에서 데이터는 '점'으로 표현한다. 1. 먼저, 클러스터링을 하고픈 데이터를 준비하고 클러스터 수를 정한다(여기서는 3). 2. 클러스터의 중심점이 될 세 점을 임의의 위치에 설치한다. 3. 각 데이터는 세 개의 중심점 중 자신으로부터 가장 가까운 곳에 있는 것을 찾는다. 4. 각 데이터가 속하는 중심점의 색으로 데이터를 분류하고, 이 것으로 세 개의 클러스터가 만들어진다. 5. 각 클러스터의 중심을 재계산해 해당 위치로 클러스터의 중심점을 이동시킨다. 6. 가장 가까운 클러스터의 중심점을 재계산하고 각.. 클러스터링 지난 글 : [알고리즘/알고리즘 도감] - 전자 인증서 비슷한 것끼리 묶는다 클러스터링(clustering)은 다수의 데이터가 주어졌을 때 '비슷한 것'들을 묶어 그룹으로 분류하는 작업을 뜻한다. 개별 그룹을 '클러스터(cluster)'라 한다. '비슷한 것'은 어떻게 정하나 데이터 간의 거리로 정하기 어떤 기준으로 '비슷한 것'을 정하는지는 데이터에 따라 다르다. 구체적으로는 두 개의 데이터 간 거리를 정의해야 한다. 예를 보자. 고등학교 모의고사에서 1학년 400명의 국어, 수학, 영어 점수를 데이터화한 후, 학생들을 '특기 과목과 비특기 과목의 유사 정도'로 클러스터링 하는 경우에 , 각 학생을 (국어 점수, 수학 점수, 영어 점수)형식으로 데이터화하고, 두 개의 데이터(k1, m1, e1)과 (k.. 전자 인증서 지난 글 : [알고리즘/알고리즘 도감] - 전자 서명 공개키 암호 방식이나 전자 서명에서는 공개키가 정말 통신하고자 하는 상대인지 보장되지 않는다는 문제가 있었다. 따라서 악의를 지닌 제삼자가 공개키를 바꿔 전달해도 받는 측에서는 눈치채지 못할 수 있다. 오늘 배울 전자 인증서를 이용하면 공개키의 정장성을 보장할 수 있게 된다고 한다. 1 1. A는 공개키 Pa와 비밀키 Sa 쌍을 갖고 있으며, 공개키 Pa를 B에게 전달하려 한다. 2. 먼저 A는 인증 기관(CA : Certification Authority)에 Pa가 자신의 것임을 나타내는 인증서 발행을 의뢰한다. 3. 인증 기관은 자신이 준비한 공개키 Pc와 비밀키 Sc를 소유하고 있다. 4. A는 공개키 Pa와 메일 주소를 포함한 개인 정보를 인증.. 전자 서명 지난 글 : [알고리즘/알고리즘 도감] - 메시지 인증 코드 전자 서명은 메시지 인증 코드가 가지는 '인증'과 '변조 검출' 두 가지 기능에 '부인 방지'를 추가한 것이다. 메시지 인증 코드는 공통키를 사용하는 구조이므로 키를 가진 수신자도 메시지 전송자일 가능성이 있어 '부인'이라는 문제가 발생할 수 있다. 하지만 전자 서명에서는 전송자만 작성할 수 있는 '전자 서명'이라는 데이터를 이용해 메시지 작성자가 누구인지 식별할 수 있다. 1 전자 서명의 특징을 알아보자. 1. A가 B에게 메시지를 보내려 한다. 2. 이때 전자 서명을 첨부한다. 전자 서명은 A만 작성할 수 있다. 3. A의 전자 서명이 첨부된 메시지가 전송된 경우, 전송자가 A인 것이 보장된다. 4. B는 전자 서명의 정당성을 검증할 수 있.. 이전 1 2 3 4 ··· 6 다음
