반응형

알고리즘 4

에라토스테네스의 체 이해하기

그리스 수학자 에라토스네테스가 고안해 낸 소수를 찾는 알고리즘입니다. 다른 알고리즘에 비해서 논리가 상당이 심플하기 때문에 어렵지 않게 접근할 수 있습니다. 우선 소수의 정의는 1과 자기 자신 외에 약수를 가지지 않는 수 입니다. 따라서 1이 아닌 어떤 수를 n(n > 1)배 했을 때 소수가 나올 수는 없습니다. 이것이 이 알고리즘의 핵심입니다. 소수가 아닌 수는 합성수입니다. 1과 자기 자신 이외에 약수를 가지는 수가 합성수죠. 알고리즘을 간단히 설명하겠습니다. 예를들어 2부터 100까지의 수 중에서 소수를 구한다고 해봅시다. 앞서 예기한 것처럼 1이 아닌 어떤 수(여기서는 2부터 100까지의 수를 차례대로)를 2배, 3배, ... 해서 100을 넘기기 전까지의 배수를 구합니다. (아래 그림) 위 그림..

C언어 에라스토테네스의 체 알고리즘

그리스의 수학자.천문학자.지리학자. 소수를 발견하는 방법으로서 에라스토테네스의 체(코스키콘)를 고안하고, 해시계로 지구 둘레의 길이를 처음으로 계산한사람. 지리상의 위치를 위도. 경도로 표시한 것은 그가 처음인것으로 알려져있다. -두산백과- 알로리즘을 짜다보면 소수, 약수,최대공약수 등등 익숙하지만 난감한 문제에 봉착할때가 많다. 수학파트에서 살펴본 공약수의판별을 위해 유클리드의 호제법을 알아야하는 것 처럼 말이다. 에라스토테네스의 체는 말그대로 체(고운가루는 통과 시킨다) 고운가루는 소수가아닌수이다. 알고리즘으로 살펴보자. 입력을 받은 수까지의 소수를 출력시켜준다. 배열을 생성하여 첨자찾으려는 수로 인식하고 배열의 값은 1로 초기화한다. 그리고 2의 배수부터 4,6,8,10.... 3의배수 6,9,12..

C언어 [Factorial]팩토리얼 알고리즘

팩토리얼을 C언어로 표현해보자. 0!=1이다. 이문제는 수학적 정의이다. 우리가 어떤수의 0제곱수는 1이라고 정의하는 것과 동일한 이치이다. 여기선 자세히 설명하지 않겠다. 우리가 지금 중요하게 다루는건수학적 정의보다는 어떤 식을 프로그램상으로 표현하는 방법에 대해서 공부하는 것이다. 힌트를 보려면 아래를 펼치면 된다. 먼저 원칙을 정하자 1.포맷을 맞추자 어떤 식을 표현하기위해선 여러변수들의 복합적인 작용이 있기때문에 틀을 정하지않고 생각하려면 한계에 다다른다. 그러므로 위 실행결과를 보고 그에 맞는 포맷(큰 틀)을 만들자 #include int main(void) { printf("%d! = %d", n, 결과); } 2. 위 실행결과에 맞는 틀을 갖춰졌다. 이젠 하나식 분석해보자. - 먼저 결과값을..

C언어 nCr 조합 알고리즘

위공식은 조합의 일반식을 점화식으로 나타낸 공식이다. 이 공식을 점화식으로 바꾼 것 뿐이다. 점화식이나 조합에대해서 잘 모른다면 그냥 맨처음 공식을 알고리즘으로 표현 하길 바란다. 우리는 간단히 조합을 나열하는 알고리즘을 만들 것이다. 결과 간단한 듯 보이지만, 몇가지 생각해볼 부분이있다. 우리는 그런 부분에 초점을 마추며 실력을 쌓아가자. 관련글 2012/12/06 - [프로그래밍/알고리즘] - C언어 알고리즘[Factorial]팩토리얼

반응형