본문 바로가기

# Foundation/기초수학

 (8)
# Foundation/기초수학 급수 알고리즘 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 급수(Series)의 정의수열 An이 주어졌을 때, 수열(Sequence)에 속해있는 모든 원소의 합. 끝이 존재하는 수열의 급수를 유한급수라고 하며,끝이 존재하지 않는 수열의 급수를 무한급수라고 한다. 급수 알고리즘 개요 사실 알고리즘도 아니다.급수 공식을 활용하면 대부분 상수 시간내에 수열의 합을 계산할 수 있다. Function Information series_arth(a0, d, n) 순회를 이용하여 산술급수를 구한다. series_arth_formla(a0, d, n) 급수공식을 이용하여 산술급수를 구한다. series_geo(a0, r, n) 순회를 이용하여 기하급수를 구한다. s..

2018. 11. 5. 16:11
# Foundation/기초수학 파도반 수열 알고리즘 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 파도반 수열(Padovan Sequence)의 정의현재항의 값이 2, 3번째 이전의 항의 합으로 계산되는 수열.여기서는 인덱스가 0이고 초기값인 {1, 1, 1}인 수열을 사용한다.아래는 인덱스가 0이고 초기값이 {1, 0, 0}인 파도반 수열의 리스트이다.{1, 1, 1} 으로 시작하는 부분부터 위 그림의 점화식을 따른다. 출처 : OEIS_A000931 파도반 수열 알고리즘 개요파도반 수열과 피보나치 수열의 점화식은 매우 유사하다.따라서 파도반 수열을 구하는 알고리즘도 피보나치와 고만고만하다. Function Information pado_recursion(n) 재귀를 이용하여 n번째 피보..

2018. 11. 4. 18:53
# Foundation/기초수학 피보나치 수열 알고리즘 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 피보나치 수열(Fibonacci Sequence)의 정의현재항의 값이 이전 2개 항의 합으로 계산되는 수열. 컴퓨터 과학에서는 주로 0번째 항이 0인 피보나치 수열을 사용한다. ( 0, 1, 1, 2, ... )아래는 200번째 인덱스까지의 피보나치 수열 테이블이다. 출처 : OEIS_A000045 피보나치 수열 알고리즘 개요N번째 피보나치수를 알고 싶다면, 정의에 따라 N-1, N-2번째 피보나치 수를 알고 있어야 한다.정리하자면, 얼마나 효율적으로 N-1, N-2를 가져오느냐가 전체 성능을 좌우한다. 아래는 피보나치 수열을 만들때 사용하는 방법들이다. Function Information ..

2018. 11. 3. 17:02
# Foundation/기초수학 소수 알고리즘 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 소수(Prime-Number)의 정의 1과 자기 자신만을 약수로 갖는 수. 소수가 아닌 수를 합성수(composite)라고 한다.그림에서 보듯이 소수는 1과 자신을 제외한 m x n 형태로 표현할 수 없다. 아래는 인덱스가 1,000,000 이하의 소수 테이블이다. 출처 : OEIS_A000040 소수 판별 알고리즘 개요정확히는 소수 판별(Prime Testing)이 아닌 소수 생성(Prime Generation)알고리즘이다. N이 소수인지 알고 싶다면 N까지 소수 테이블을 만들고나서 확인해야 한다.수학적 의미의 판별(Testing)은 완벽한 결과를 보장할 수 없거나 확률론을 기반으로 하기 때..

2018. 10. 26. 23:11
# Foundation/기초수학 최대 공약수와 최소 공배수의 관계 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 두 정수의 최대공약수와 최소공배수의 관계두 정수 a, b에 대하여, 이것의 최대공약수와 최소공배수를 각각 hcf, lcm이라 하면 아래와 같은 등식이 성립된다. HCF (Highest Common Factor) : 최대 공약수 GCD (Greatest Common Divisor) : 최대 공약수 LCM (Lowest Common Multiple) : 최소 공배수 증명은 다음과 같다. 숫자가 여러개일 때, 최대공약수와 최소공배수의 관계 숫자가 3개 또는 4개 이상일 때도 비슷하게 흘러간다.

2018. 10. 24. 01:04
# Foundation/기초수학 최소 공배수 알고리즘 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 두 수의 최소 공배수 구하기두 수의 최소 공배수를 구하는 방법을 알아보자.배수를 구하는 방법은.. 다들 알 것이라 굳게 믿는다. 자, 처음에 소개할 방법은 가장 기초적이고 직관적이다!이중 반복문을 순회하면서 a * i == b * j 를 만족할 때 값을 반환한다. 최악의 경우는 두 수가 서로소인 경우이고, 이 때의 최소 공배수는a * b이다.따라서 각각의 반복문의 범위는 b, a 까지로 한정된다. 물론 간단한 만큼 성능은 떨어진다. 최악의 경우에서의 시간 복잡도는 O( a*b )이므로 O( n^2 )에 근사하다고 볼 수 있고,입력값이 각각 46341, 46340 인 경우에서 평균 소요시간은 4..

2018. 10. 23. 03:10
# Foundation/기초수학 최대 공약수 알고리즘 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 두 수의 최대 공약수 구하기이번에는 두 숫자의 최대 공약수를 구하는 방법에 대해서 알아보자. 약수를 빠르게 찾는 방법은 이전 게시글을 참고하도록 하자. 먼저 쉽게 가보자. 지금보다 큰 공약수가 나올때마다 갱신하면 된다. 물론 성능은 보장할 수 없다. a = 1,000,000,000 이고 b = 876,543,210 일 때, 평균 2711 ms가 걸렸다. 반복문이 min(a, b)번 만큼 순회하므로, 시간 복잡도는 O( min(a, b) ) 이고, 큰 입력값이나 횟수나 들어온다면 더더욱 성능을 보장할 수 없다. 여기서 잔머리를 한번 굴려보자, 뒤에서 첫 공약수가 최대 공약수임을 눈치챘다면 공약수..

2018. 10. 22. 14:01
# Foundation/기초수학 약수 알고리즘 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 성능은 중요해아무런 고려없이 약수 알고리즘을 만든다면 아래와 같지 않을까. 아무리 심플한게 좋다지만, 이건 좀 과한 듯 싶다. 이 심플한 알고리즘은 v = 1,000,000,000 기준으로 평균 4208 ms가 걸렸으며, 전체 연산량이 입력값에 대해 선형으로 증가하므로, 시간복잡도는 O(n)이다. 입력값이 작은 상황에서는 괜찮겠지만, 입력값이 크거나 타임 크리티컬한 상황에서는 절대 사용하면 안된다. 상당한 개선이 필요해보인다. 음.. 전체 연산량을 줄일 수 있는 방법은 없을까? 있다. 약수의 정의를 생각하면 좀 더 빠르게 동작하는 약수 알고리즘을 구현할 수 있다. 정수 V, A, B에 대하여 ..

2018. 10. 21. 21:59

티스토리툴바