개발아 담하자

유전 알고리즘은 자연 세계의 진화 과정에 기초한 계산 모델로서 존 홀랜드에 의해서 개발된 전역 최적화 기법 으로, 최적화 문제를 해결하는 기법의 하나이다. 생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화 과정에서 많은 부분을 차용하였으며 변이, 교배 연산 등이 존재한다. 유전 알고리즘의 동작의 단계는 아래와 같다. 1. 초기 염색체의 집합 생성 초기 염색체 생성 연산에 의해 생성된 염색체들은 위 과 같다. 2. 초기 염색체들에 대한 적합도 계산 의 염색체들에 대한 적합도를 계산하면 위 와 같다. 3. 현재 염색체들로부터 자손들 생성 룰렛 휠 선택 방법을 통해 염색체 [B C E D] 가 선택되었다고 가정하면, crossover 연산을 통해 과 같은 자손이 생성된다. Crossover 연산..

Greedy Algorithm 이란? 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 탐욕 알고리즘, 욕심쟁이 알고리즘 으로도 불린다. 매 순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하 최종적인 최적해에 도달하는 기법이다. 활동 선택 문제 (Activity Selection Problem) 한 강의실에서 여러 개의 수업을 하려고 할 때 한 번에 가장 많은 수업을 할 수 있는 경우를 고르는 것이다. Si는 시작시간, Fi는 종료시간이다. (서로 수업 시간이 겹치면 안 된다.) 직관적으로 생각하면, 최적의 해를 구하기 위해서는 첫 번째 활동이 최대한 일찍 끝나면 된다. 그래야 다른 활동을 더 많이 선택할 수 있기 때문이다. 위의 경우 첫 선택으로 가장 ..

2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 예시 1071과 1029의 최대 공약수를 구하면, 1071은 1029로 나누어떨어지지 않기 때문에 1071을 1029로 나눈 나머지를 구한다 >> 42 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나..

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체 '라고 부른다. 구현 과정 120까지의 모든 소수를 구한다고 해 보자. 에리스토테네스의 체는 2부터 120까지의 수를 배열에 모두 넣은 후 소수가 아닌 것들으 모두 체크해버리는 것이다. 즉, 체크가 안 된 수들이 소수 이다. 2. 2를 제외한 2의 배수 지우기 2. 3을 제외한 3의 배수 지우기 3. 4의 배수는 지울 필요 없다 (2의 배수에서 이미 지워짐) 2,3 다음으로 남아있는 가장 작은 수인 5를 제외한 5의 배수를 지운다. 이런 식으로 남은 것들의 2배수, 3배수, ... n배수를 지우다 보면 소수만 남는다. 이미 정해진 소수의 배수인 것들은 지워서 소수를 ..