분할수 – 오일러프로젝트 078

동전 100개를 나누는 방법 이 문제는 오일러 프로젝트 76번 문제와 같은 문제로 볼 수 있는데…. 처음 작성한 시점부터 너무 오래된 글이라, 진도를 기다리지 못하고 미리 발행한다. 5개의 동전이 있다.  이 동전들을 나누는 방법을 생각해 보자. 동전 5개는 아래와 같이 총 7가지 방법으로 나눌 수 있다. ooooo # 5개짜리 그룹 1개 oooo o # 4개 + 1개 ooo oo # 3개 + 2개 ooo o o # 3개 + 1개 + 1개 oo oo o # 2개 + 2개 + 1개

Fast Fibonacci Transform

빠른 피보나치 항 구하기 피보나치 수열은 0, 1, 1, 2, 3, 5, 8,… 과 같이 앞의 두 항의 합이 그 앞의 항이 되는 수열이다. 피보나츼 수열의 n 항을 구하는 함수는 보통 이렇게 많이 작성한다. def fib(n): if n < 3: return (0, 1)[n] return fib(n-1) + fib(n-2) 하지만 이 함수는 지극히 비효율적이라 %time fib(35) Wall time: 7.05 s Out[7]: 9227465 이런 처참한 성능이 나온다. 이는 한 번 계산했던 값을 계속 재계산하기 때문인데, 이런 문제를 피하기위해서는 메모이제인션이라는 캐싱 기법을 쓴다. #

체를 사용하여 소수 집합 구하기

가장 빠른 알고리듬 현재까지 순수 파이썬으로 작성된 알고리듬 중 가장 빠른 것으로 알려진 것은 @Robert William Hanks가 개발한 아래 알고리듬이다. def primes(n): “””Return a list of primes under n””” sieve = [True] * (n/2) for i in xrange(3, int(n**0.5)+1, 2): if sieve[i/2]: sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) return [2] + [2*i+1 for i in xrange(1, n/2) if sieve[i]]