본문 바로가기

Math with Code

공분산(Covariance) 계산하기. 공분산은 두 가지 사전의 확률변수의 분포를 이용해서 두 사건이 어느 정도의 상관관계를 가지고 있는지를 표현하는 한가지 수단이다. 공분산에 대한 자세한 설명은 다른 블로그나 웹을 찾아보도록 하고, 두 개 확률 변수 리스트가 있을 때, 이로부터 공분산을 구하는 코드를 설명해보겠다. 공분산은 두 확률 변수의 집합에서 각각의 편차의 곱을 다시 평균한 것이다. 따라서 다음과 같이 간단한 함수를 만들어서 계산할 수 있다. ### 공분산 계산함수 def covariance(X, Y): ## 먼저 평균을 구하는 함수가 필요하다. avg = lambda ns: sum(ns) / len(ns) ax, ay = avg(X), avg(Y) return sum((ax-x)*(ay-y) for x, y in zip(X, Y)) .. 더보기
0부터 9까지의 수를 사용해 규칙에 맞는 수를 만들기 0부터 9까지 10개의 숫자를 모두 사용해서 규칙에 맞는 수를 만드는 문제이다. 규칙은 단순하다. 원문: http://blog.naver.com/PostView.nhn?blogId=kyaryunha&logNo=220923287298 첫번째 숫자까지 1로 나눠진다. 두번째 숫자까지 2로 나눠진다. ... n번째 숫자까지 n으로 나눠진다. 그리고 이 숫자는 0-9 팬디지털 숫자이므로 같은 숫자를 두 번 쓸 일은 없다. 원문에서는 C로 코드를 작성한 거 같던데 5분 내외에 답을 구하고 있다. 여기서는 파이썬으로 풀이해본다. 팬디지털 숫자이므로 1,023,456,789~9,876,543,210까지의 범위를 루프로 돌기보다는 각자리에 사용될 숫자를 추출해서 돌아본다. 여기서 사용된 숫자를 피해서 추출하는 로직을 .. 더보기
소인수분해하기 소인수분해와 약수의 개수 어떤 자연수 n을 소인수 분해하였을 때 나오는 소인수의 모든 지수에 1을 더하고, 그 값들을 모두 곱하면 n의 약수의 개수가 된다. 이는 n의 모든 약수는 각각의 소수인 인수 a, b, c.... 들을 0번에서 각 지수번까지 사용한 조합을 만드는 것과 동일하기 때문이다. 따라서 어떤 자연수 n을 소인수 분해 할 수 있다면 그 약수의 개수를 빠르게 계산할 수 있을 것이다. 문제 오일러 프로젝트 12번 문제는 약수의 개수를 빠르게 구하는 것에 중점을 두는 문제이다. 1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라 합니다. 예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 입니다. 이런 식으로 삼각수를 구해 나가면 다음과 같습니다. 1, 3.. 더보기
(파이썬) 소수 판별하기 소수판별하기 소수(Prime number)는 1과 자기자신만을 약수로 가지는 양의 정수를 말한다. 2, 3, 5, 7, 11, 13... 등의 수이다. 어떤 수가 소수인지 판단하는 방법에 대해 알아보자. 가장 간단하게 소수의 정의로부터, 어떤 자연수 N이 소수인지를 살펴보려면 N 이 1 이면 소수가 아니다. 2 부터 N-1 까지의 자연수들로 순서대로 N을 나눠서 나누어 떨어지는 수가 하나도 없으면 N은 소수이다. 라는 간단한 검사 규칙을 얻을 수 있다. 기본적으로 이 규칙을 그대로 적용하여 코드로 옮겨보면 생각보다 매우 간단한 함수가 만들어진다. def is_prime_bad(n: int) -> bool: if n < 2: return False for i in range(2, n): if n % i i.. 더보기
완전수와 초과수 (약수의 합 구하기) 완전수와 초과수 어떤 자연수 N의 자기 자신보다 작은 양의 약수들의 합이 자기 자신과 같다면 그 수를 완전수라하고, 만약 약수의 합이 N보다 크다면 초과수라고 한다. 6은 가장 작은 완전수로, 6의 약수는 1, 2, 3, 6이며, 이중 6 자신을 제외한 세 수의 합은 6으로 원래의 값과 일치한다. 12의 약수는 1, 2, 3, 4, 6, 12이고, 12를 제외한 약수의 합은 16으로 12는 초과수이다. 약수의 합을 구하는 방법은 크게 두 가지가 있다. 무식하게 1부터 N까지의 수로 N을 나눠서, 나눠지는 수가 약수이므로 이들을 모두 합산한다. N을 소인수분해하여, 각 인수의 누적 거듭제곱의 합들을 구하고, 다시 이들의 누적 곱을 구한다. (수학 시간에 약수의 합을 구하는 공식이라고 배웠다.) 컴퓨터를 이.. 더보기
최대공약수와 최소공배수 최대 공약수와 최소 공배수최대 공약수와 최소 공배수를 계산하는 방법에 대해서 알아보자. 최대 공약수와 최소 공배수가 나오는 제법 유명한 문제로는 프로젝트 오일러의 5번 문제는 다음과 같다. 1~10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다. 그러면 1~20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까? 이 문제는 결국 20이하의 자연수 전체의 최소 공배수가 얼마인지를 묻는다. 참고로 이 문제의 답은 매우 큰 수이기 때문에 C와 같이 큰 수를 기본적으로 지원하지 않는 언어에서는 큰 수의 곱셈을 계산하는 별도의 자료 구조와 알고리듬이 필요할 것이다. 이 글은 당연희 파이썬으로 푸는 방법을 소개한다.두 A, B 의 최소 공배수를 구하는 방법은 다음과 같다. 두 수 A.. 더보기
피보나치 수열 피보나치 수열 피보나치 수열은 1, 1, 2, 3, 5, 8... 과 같이 전개되는 수열로 처음 두 항이 모두 1이고 세번째 항 부터는 앞의 두 항의 합으로 이루어지는 수열이다. 중학교 과정에서 수열을 배울 때 잠깐 언급이 되는데, 프로그래밍을 공부하다보면 재귀와 관련하여 꼭 다시 만나게 되는 수열이다. 피보나치 수열의 수학적 정의는 다음과 같다. $$ F*{1}= 1, F*{2} = 1\\ F*{n} = F*{n-1} + F_{n-2} $$ 이 식을 바탕으로 피보나치 수열의 일반항을 구하는 코드를 파이썬으로 작성해보면 다음과 같은 함수를 작성할 수 있다. def fibonacci(n): if n < 3: return 1 return fibonacci(n-1) + fibonacci(n-2) 원래 점화식으.. 더보기

티스토리툴바