cyphen156

소수(Prime Number)를 찾는 방법은 단순하지만 시간이 오래걸린다. 우선 소수란 1을 제외한 어떤 양의 정수가 약수를 1과 자기 자신만을 갖는 수를 말한다. 2, 3, 5, 7, 11, 13 ... 등이 소수다. 보통 제곱근 판정법이나 가장 효율적이라고 알려진 에라토스테네스의 체를 알고리즘으로사용한다. 본 글에서는 아래로 갈수록 효율적인 방법들을 소개한다. 결정론적 방법 확실하게 소수인지 아닌지를 판단하는 방법 결과가 명확하지만 연산 시간이 길어진다. 일반적인 소수판정법 가장 통상적인 방법은 2부터 시작해서 입력값의 전 까지 모두 나눠보고, 나머지가 존재하는지를 확인하는 방법이다. 이것은 이전글에서 소개한 방법과 동일하게 절반까지만 확인하는 방법 또한 존재한다. 소수판정법_native.C // 일..

이번에 배울 내용은 유클리드 알고리듬과 유사한 스테인의 알고리듬이다. 전에 컴퓨터의 연산은 뺄셈이던지 곱셈이던지 혹은 나눗셈이던지 항상 이진 덧셈으로 이루어진다고 했다. 그런데 곱셈 연산과 나눗셈 연산의 경우 덧셈이 아닌 방식으로 동작시키는 것이 가능하다. 바로 비트시프트를 이용하는 것이다. 여기 1byte크기의 메모리에 데이터가 저장되어있다고 하자. 이 정수의 4배를 구하려면 같은 수를 덧셈 연산을 4번 해야 한다. 반면 비트시프트 연산의 경우 단순히 저장된 데이터중 일부 비트정보를 뒤집으면 되기에 이론적으로 횟수로는 2번의 횟수가 되어 덧셈 연산보다 더욱 빠를 수 있다. 나눗셈의 경우도 곱셈과 연산 방향만 바뀔 뿐 연산 수행 횟수는 동일하다. 이러한 비트시프트라는 것과 짝수에 반드시 2라는 약수가 있..

흔히 유클리드 호제법(Euclidean algorithm)으로 알려진 두 양의 정수의 최대공약수와 최소공배수를 빠르게 찾아내는 문제해결방법이다. 수식이 조금 난잡해서 보기 불편한데 함수 수식으로 변환하면 f(x) = ax + b가 성립한다면 gcd(a, b) = gcd(r, b)이다 GDC(greatest common divisor/최대공약수) 최대공약수를 구하는 일반적인 방법은 다음과 같다. 두 수를 소인수 분해하여 서로 공통되는 약수들을 찾아 모두 곱한다. A = 100, B = 12일 때 두 수의 약수들은 각각 (1, 2, 4, 5, 10, 20, 25, 50, 100), (1, 2, 3, 4, 6, 12)로 1 * 2 * 4 = 8이다. 코드로 약수를 찾아가는 과정은 다음과 같다 아래의 코드는 한..

알고리즘 문제의 해답을 구하기 위한 절차를 순서대로 명확하게 나타낸 것, 주어진 문제 해결을 위한 단계적인 절차 9세기경 페르시아의 수학자 알-콰리즈미(Al-Khwarizmi)의 이름에서 유래되었다. 컴퓨터를 통한 문제의 해결은 한가지 방법만 있는것이 아니라 서로 다른 여러가지의 방법들이 존재한다. → 방법들 사이의 효율성 차이가 매우 크다. ⇒ 가장 최적화된 효율적인 방법론을 찾는것이 중요!! 알고리즘의 조건 컴퓨터를 통한 문제 해결은 절차를 표현하기 위해 명령어들을 사용한다. 하지만 모든 명령어의 집합이 알고리즘이 되는것은 아니다. → 알고리즘이라는 명령어가 되기 위해서는 조건이 필요하다. 입력 : 0개 이상의 입력을 갖는다. 출력 : 반드시 1개 이상의 출력을 갖는다. 명확성 : 각 명령어의 의미는..