본문 바로가기

project euler

오일러 프로젝트 16 (Julia) 2의 1000제곱의 각 자리 수를 더한 값을 구하는 문제이다. 파이프 연산을 사용해서 각 함수에 순서대로 전달하면 되는 정직한 문제. @time big(2)^1000 |> digits |> sum |> println 더보기
오일러 프로젝트 8번 (Julia) 문제 다음은 연속된 1000자리 숫자입니다. (읽기좋게 50자리씩 잘라놓음)73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866.. 더보기
오일러 프로젝트 7번 문제 소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다. 이 때, 10,001 번째의 소수를 구하세요. 풀이 드디어 소수 판별 함수가 등장할 차례이다. 소수의 목록을 구하는 방법에는 크게 두 가지 가 있는데, 하나는 소수판별함수를 작성하여 루프를 돌거나 리스트를 필터링하는 것이고 다른 하나는 에라토스테네스의 체를 이용하는 것이다. 에라토스테네스의 체는 매우 빠르게 동작할 수는 있지만 범위를 알고 있는 경우에 유용할 수 있다. 소수의 분포에는 현재까지는 알려진 규칙이 없으므로 10,001 번째 소수가 어디쯤에 위치할지를 가늠할 수 없다. 따라서 소수 판별 함수를 통해서 2에서부터 소수를 하나씩 세어보는 수 밖에 없을 것 같다. 관건은 얼마나 빠른 소수 판별 함수를 작성.. 더보기
오일러 프로젝트 6번 문제 1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합). 1^2 + 2^2 + ... + 10^2 = 385 1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱). (1 + 2 + ... + 10)^2 = 55^2 = 3025 따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다.그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까? 풀이 문제의 그대를 간단히 계산하면 된다. '차이'를 구하는 것은 큰 값에서 작은 값을 빼면 되는 것인데, 간단히 한쪽에서 다른 한쪽을 뺀 다음 그 절대값을 구하는 것과 같다. 절대값을 구하는 함수는 abs() 이다. .. 더보기
오일러 프로젝트 5번 (Julia) 문제 1~10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다. 그러면 1~20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까? 풀이 어떤 수 A를 B로 나누었을 때 나머지가 0이라면 (즉, 나누어 떨어진다면) A는 B의 배수이다. 문제에서 예를 든 2520은 1의 배수이면서 2의 배수이자 동시에 3, 4, 5, ... , 10의 배수로 1과 10 사이의 모든 자연수의 공배수이다. 물론 이러한 공배수는 무한히 많지만 그 중에서 가장 작은 값이라 하였으니 최소공배수이다. 따라서 문제는 1~20의 모든 자연수의 최소 공배수를 구하는 문제라 할 수 있다. 셋 이상의 수의 최소 공배수를 구하려면 먼저 두 개의 자연수의 최소 공배수를 구하고, 다시 그 값과 나머지 하나의 수의 최.. 더보기
오일러 프로젝트 4번(Julia) 문제 앞에서부터 읽을 때나 뒤에서 부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다. 두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009(= 91 x 99) 입니다. 세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까? 풀이 세 자리수 (100 ~ 999) 중에서 두 개를 골라 곱해서 대칭수가 되는지 판별하고, 그렇게 필터링된 결과 중에서 최대값을 고르면 된다. 대칭수를 판별하기에 가장 간편한 방법은 문자열로 변환하여 reverse() 함수를 통해서 뒤집은 결과와 원래 문자열이 같은지를 보면 된다. ispal(n) = let s = "$n"; s == reverse(s); end 전체 풀이는 다음과 같다. ispal() 함수 사용하여 대칭수를 판별할 수.. 더보기
프로젝트 오일러 3번 풀이 (Julia) 프로젝트 오일러 3번 어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다. 예를 들면 13195의 소인수는 5, 7, 13, 29입니다. 600851475143의 소인수 중에서 가장 큰 수를 구하세요. 어떤 자연수 N이 다른 자연수 a 로 나누어 떨어진다고 하자. 이 관계를 수식으로 쓰면 $$N = a \times b$$ 이 되는데 이 때, a는 N의 인수가 된다. 그리고 이 때 a가 소수라면 a는 N의 소인수가 된다. 그런데 이 식에서 주목할 점은 b 역시 N을 나눌 수 있는 인수라는 점이다. 다시 자연수 N을 그 소인수들의 곱으로 표현했을 때 \(a \times a \times b \times c\)가 되고 이 때 a < b < c 라면 c가 가장 큰 .. 더보기
프로젝트 오일러 2번 (Julia) 프로젝트 오일러 2번 풀이 피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까? 피보나치 수열을 구현하기 위한 방법은 많이 있다. 흔히 재귀적으로 특정항을 구하는 방법이 있지만, 이는 지수적인 시간복잡도를 갖기 때문에 이 문제에는 적용할 수 없다. 다행히 '바로 앞 항 두개를 더한다'는 계산으로 피보나치 수열을 앞에서부터 계산하는 것은 간단하다. A, A+1 항의 값을 가지고 있을 때, A+1, A+2 항의 값을 계산하는 것은 (A+1항, A항 + A+1항)으로 계산되기 때문에 단순한 반복문으로 계산할 수 있다. 참고로 계산된 항이 짝수인 경우, if 문을 사용해서.. 더보기

티스토리툴바