본문 바로가기

알고리즘

 (105)
단순 선택 정렬 지난 글 : [알고리즘/Do it 알고리즘] - 버블 정렬 단순 선택 정렬 알아보기 단순 선택 정렬은 가장 작은 요소를 맨 앞으로, 두 번째로 작은 요소를 맨 앞에서 두 번째로 이동하는 등의 작업을 반복하는 알고리즘이다. 참고 : [알고리즘/알고리즘 도감] - 선택 정렬 단순 선택 정렬의 교환 과정은 아래와 같다. 1. 아직 정렬하지 않은 부분에서 가장 작은 키값(a[min])을 선택한다. 2. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다. 아래는 단순 선택 정렬을 수행하는 메서드다. static void selectionSort(int[] a, int n) { for(int i = 0; i < n - 1; i++) { int min = i; for(int j = i + 1; j <..
유클리드 지난 글 : [알고리즘/알고리즘 도감] - k-means 알고리즘 유클리드(Euclidean) 알고리즘은 두 수의 최대공약수를 구하는 알고리즘으로서 세계에서 가장 오래된 알고리즘으로 유명하다. 언제 발견됐는지는 알 수 없지만, 가장 오래된 기록이 기원전 300년에 작성된 유클리드 필서라는 것에서 유클리드라는 명칭이 붙여졌다. 1 유클리드 알고리즘으로 1112와 695의 최대공약수를 계산하기에 앞서 수기로 계산해보자. 1. 일반적인 방법으로 두 개의 수를 소인수분해해 공통되는 소수를 최대공약수로 구한다. 1112 = 139 X 2 X 2 X 2 695 = 139 X 5 139 = 최대공약수 2. 하지만 이 방법에서는 두 수가 커질수록 소인수분해가 어려워진다. 유클리드 알고리즘에서는 더 효율적으로 최대공약수..
버블 정렬 지난 글 : [알고리즘/Do it 알고리즘] - 정렬 알고리즘 버블 정렬 알아보기 참고 : [알고리즘/알고리즘 도감] - 버블 정렬 버블 정렬 프로그램 만들기 버블 정렬 알고리즘을 프로그램으로 구현해보자. 변수 i값을 0부터 n - 2까지 1씩 증가시키며 패스를 n - 1번 수행하는 프로그램이다. 알고리즘 개선하기 1 만약 임의로 저장된 요소가 정렬하려는(여기서는 오름차순) 방식과 유사하게 정렬되어 있다면 패스(요소값을 비교하고 위치를 변경하는 작업)를 많이 진행할 필요가 없다. 어떤 패스에서 요소의 교환 횟수가 0번이면 더 이상 정렬할 요소가 없다는 뜻이기에 정렬 작업을 멈춘다. 이런 멈춤 방식을 도입하면 정렬을 마친 배열이나 정렬이 거의 다 된 상태의 배열에 대한 비교 연산이 많이 생략되어 짧은 시간..
k-means 알고리즘 지난 글 : [알고리즘/알고리즘 도감] - 클러스터링 k-means 알고리즘은 클러스터링 알고리즘의 하나로, k-means 알고리즘에서는 클러스터의 수를 미리 지정해 그 수에 맞춰 그룹을 나눈다. 1 아래에서 데이터는 '점'으로 표현한다. 1. 먼저, 클러스터링을 하고픈 데이터를 준비하고 클러스터 수를 정한다(여기서는 3). 2. 클러스터의 중심점이 될 세 점을 임의의 위치에 설치한다. 3. 각 데이터는 세 개의 중심점 중 자신으로부터 가장 가까운 곳에 있는 것을 찾는다. 4. 각 데이터가 속하는 중심점의 색으로 데이터를 분류하고, 이 것으로 세 개의 클러스터가 만들어진다. 5. 각 클러스터의 중심을 재계산해 해당 위치로 클러스터의 중심점을 이동시킨다. 6. 가장 가까운 클러스터의 중심점을 재계산하고 각..
정렬 알고리즘 지난 글 : [알고리즘/Do it 알고리즘] - 8퀸 문제 정렬 정렬(sorting)은 이름, 학번, 키 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업이다. 이 알고리즘을 이용해 데이터를 정렬하면 검색을 더 쉽게 할 수 있다. 값이 작은 데이터를 앞쪽에 놓으면 오름차순(ascending order) 정렬, 값이 큰 데이터를 앞쪽에 놓으면 내림차순(descending order) 정렬이라 한다. 정렬 알고리즘의 안정성 앞으로 정렬 알고리즘 중 대표적인 8개의 알고리즘을 배울 것이다. 이때 정렬 알고리즘은 안정된(stable) 알고리즘과 그렇지 않은 알고리즘으로 나뉜다고 한다. 안정된 정렬이란 키값이 같은 요소의 순서가 정렬 전후에도 유지되는 것을 말한다. 안정되지 않..
클러스터링 지난 글 : [알고리즘/알고리즘 도감] - 전자 인증서 비슷한 것끼리 묶는다 클러스터링(clustering)은 다수의 데이터가 주어졌을 때 '비슷한 것'들을 묶어 그룹으로 분류하는 작업을 뜻한다. 개별 그룹을 '클러스터(cluster)'라 한다. '비슷한 것'은 어떻게 정하나 데이터 간의 거리로 정하기 어떤 기준으로 '비슷한 것'을 정하는지는 데이터에 따라 다르다. 구체적으로는 두 개의 데이터 간 거리를 정의해야 한다. 예를 보자. 고등학교 모의고사에서 1학년 400명의 국어, 수학, 영어 점수를 데이터화한 후, 학생들을 '특기 과목과 비특기 과목의 유사 정도'로 클러스터링 하는 경우에 , 각 학생을 (국어 점수, 수학 점수, 영어 점수)형식으로 데이터화하고, 두 개의 데이터(k1, m1, e1)과 (k..
8퀸 문제 지난 글 : [알고리즘/Do it 알고리즘] - 하노이의 탑 8퀸 문제 알아보기 8퀸 문제(8-Queen problem)는 재귀 알고리즘을 깊이 있게 이해하기 위한 예제로 자주 등장하며 19세기 유명 수학자 카를 프리드리히 가우스(C. F. Gaus)가 잘못된 해답을 내놓은 것으로도 알려져있는 문제라 한다. 문제는 아래와 같다. 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 X 8 체스판에 놓이시오. 이 문제의 답이 되는 조합은 무려 92가지라 한다. 체스판의 가로줄을 행, 세로줄을 열이라 하고 배열 인덱스에 맞추어 행과 열에 0~7의 번호를 부여한다. 그리고 퀸을 아래와 같이 배치한다. 0행 0열 4행 1열 7행 2열 5행 3열 2행 4열 6행 5열 1행 6열 3행 7열 퀸 배치하기 8개의 퀸을 배치하..
전자 인증서 지난 글 : [알고리즘/알고리즘 도감] - 전자 서명 공개키 암호 방식이나 전자 서명에서는 공개키가 정말 통신하고자 하는 상대인지 보장되지 않는다는 문제가 있었다. 따라서 악의를 지닌 제삼자가 공개키를 바꿔 전달해도 받는 측에서는 눈치채지 못할 수 있다. 오늘 배울 전자 인증서를 이용하면 공개키의 정장성을 보장할 수 있게 된다고 한다. 1 1. A는 공개키 Pa와 비밀키 Sa 쌍을 갖고 있으며, 공개키 Pa를 B에게 전달하려 한다. 2. 먼저 A는 인증 기관(CA : Certification Authority)에 Pa가 자신의 것임을 나타내는 인증서 발행을 의뢰한다. 3. 인증 기관은 자신이 준비한 공개키 Pc와 비밀키 Sc를 소유하고 있다. 4. A는 공개키 Pa와 메일 주소를 포함한 개인 정보를 인증..

티스토리툴바