전체 글140 최대 공약수, 최소 공배수 최대 공약수(GCD : Greatest Common Divisor) 두 수의 공약수중 가장 큰 수 첫번째 방법. 2부터 둘 중 작은 수까지 계속 나눠 보는 방법 두번째 방법. 유클리드 호제법 : gcd(a,b) = gcd(b, a%b) 임을 이용. 최소 공배수(LCM : Least Common Multiple) 두수의 공배수중 제일 작은 수 최대 공약수를 이용해 구하는 방법. lcm(a,b) = ab/g ( g = gcm(a,b) ) 오버플로우를 조심. a/g * b/g *g 같은 방식으로 구하면 조금 덜 수 있다. 2020. 3. 10. 소수 판별 소수(Prime Number) : 1과 자기 자신으로만 나누어 떨어지는 수. 암호 분야에서 기술적으로 이용하고 있는 중요한 수. 임의의 수 N의 소수 구하기. 첫번째 방법 2~N-1까지 모든 수로 나누어 보면서 나머지가 0인 경우가 있는지 판단하는 방법. 0인 경우가 한번이라도 있으면 소수가 아님. 두번째 방법. 2~ N의 제곱근 까지 모든 수로 나누어보고 나머지가 0인 경우가 없으면 그보다 큰 수는 당연히 없다. 하지만 컴퓨터 입장에서는 제곱근 연산이 부담되므로 첫번째 방법이 나음. 세번째 방법. 에라토스테네스의 체 : 여러개의 수에 대해 소수 판별을 해야할 때 사용할 수 있다. 1. 1을 제외한 모든 수를 표에 적는다. 2. 현재 수가 지워져 있다면 다음 수로 이동. 3. 현재 수가 지워져 있지 않다.. 2020. 3. 10. 카테고리 정의 이 카테고리는 프로그래밍에 유용하거나 자주사용되는 수학적 내용들을 코드와 함께 정리하는 카테고리 2020. 3. 10. 알고리즘 - 기하 알고리즘 CCW(Counter Clockwise) 세 점이 어떤 위치 관계로 놓여있는가를 판단하기 위한 알고리즘. 기하 알고리즘의 기본. 세 점이 일직선, 가운데점을 기준으로 반시계, 시계 방향으로 놓여있는 경우를 판단하는 알고리즘. 각 점 사이의 벡터(A,B 와 B,C) 에 대해 외적을 계산하여 0이 나오면 평행으로 일직선, 양수라면 반시계, 음수라면 시계방향으로 나타난다고 본다. 컨백스 헐(Convex Hull) 2차원 평면상의 여러 점중에 다른 모든 점을 포함할수 있는 볼록 다각형을 찾는 알고리즘. 만약 10개의 점이 존재하면 점 10개를 모두 포함하는 면적을 가진 볼록 다각형을 찾는것. 1. 기준점을 잡는다. 보통 기준점은 최하단 좌측에 위치한 점을 잡음. 2. 기준점의 반시계방향으로 다른 점들을 각도순으.. 2020. 3. 10. 이전 1 ··· 13 14 15 16 17 18 19 ··· 35 다음