본문 바로가기
반응형

Programming/Project Euler89

16. 프로젝트 오일러 #16 : 2의 1000승의 모든 자릿수 합 구하기. 사실 이번 프로그램은 Big integer를 사용할 줄 아느냐 아니냐에 따라서 달라진다고 봅니다. 많은 언어가 기본으로 Big Integer를 지원하기 때문에, 언어에 따라서 구현 난이도도 차이가 많을겁니다. 예를 들어서 python을 이용하면, 가볍게 이 문제를 해결할 수 있습니다. >>> 2**1000 10715086071862673209484250490600018105614048117055336074437503883703510 51124936122493198378815695858127594672917553146825187145285692314043598 45775746985748039345677748242309854210746050623711418779541821530464749 8358194126.. 2015. 1. 13.
프로젝트 오일러 #15 격자 경로의 수 구하기 사실 이번 문제는 상당히 쉬운 편이라서 그다지 설명이 필요할 것도 없을 듯 합니다. 다른 프로그래머도 저랑 비슷한 접근을 했고요. 2014년 년 마지막 날을 이렇게 보내네요. 예를 들면 2x2 격자에서 오른쪽과 아래로만 갈 수 있는 경로의 수는, 오른쪽 이동을 R, 아래 이동을 D라 표현하면 다음과 같습니다. RRDD RDRD RDDR DRRD DRDR DDRR 위와 같이 총 6가지의 경우가 나옵니다. 이 중에 R만을 가지고 따진다면, 4개의 칸 중에 2개의 R을 배치하는 방법의 수입니다. 프로젝트 오일러의 문제 링크입니다. https://projecteuler.net/problem=15 Problem 15 - Project Euler Starting in the top left corner of a 2.. 2014. 12. 31.
14. 프로젝트 오일러 #14 : 최대 체인을 가지는 우박수 구하기 이번 문제는 동적 프로그래밍을 이용해서 작성을 하는 것이 가장 좋을 듯 합니다. 우박수를 구하다보면, 이미 전에 계산했던 우박수 체인수가 있을 수 있습니다. 그렇게 하지 않으면, 체인수가 100여개 있는데, 1,000,000까지 구한다면, 1억번정도 평균적으로 계산해야 합니다. 동적 프로그래밍을 이용하면, 이 수를 줄일 수 있습니다. 물론 수가 1이 된다는 가정하에서 이야기지만, 현재까지 예외는 없으니까요. 사실 수학적으로 1,000,000까지 우박수가 된다는 것을 확인하면, n/2로 건너뛰기를 하기 때문에 반드시 우박수가 될 수밖에 없습니다. 순수한 수학적인 증명만으로는 할 수 없지만요. 물론, 자꾸 홀수에 걸쳐서 숫자가 비대해질 수는 있습니다만, 3n+1 은 반드시 짝수가 되기 때문에 홀수가 연달아 .. 2014. 12. 30.
13. 프로젝트 오일러 #13 : BigInt 수의 합 구하기 사실 이번 문제는 꼼수로 푸는 것이 맞을 듯 합니다. BigInt 라이브러리를 이용해서 풀어도 되겠지만, 그렇게 하면 시간이 많이 걸리죠. 앞자리부터 10자리 숫자만 구하면 되는 것이니까요. 그렇게 하면 int형으로는 위험할지 몰라도 int64형으로는 충분한 자릿수가 됩니다. 32비트 자료형은 10의 9승정도를 표현할 수 있으니까요. 64비트는 10의 19승까지 표현할 수 있죠. 여기에 소스만 올리도록 할께요. 특별하게 설명할 일은 없는 듯 합니다. #include int main() { char *s = "37107287533902102798797998220837590246510135740250" "46376937677490009712648124896970078050417018260538" // 데이터.. 2014. 12. 30.
12. 프로젝트 오일러 #12 : 500개 초과 삼각수 구하기 이번 문제는 삼각수에 대한 것입니다. 간단한 중학수학 수준만 알고 있다면, 이 문제를 좀 빠르게 풀 수 있을 것이라 생각합니다. 1~n 까지의 합은 다음과 같은 식으로 구할 수 있습니다. 그 다음은 약수들의 갯수를 구하는 방법입니다. 예를 들어서 12의 약수의 갯수는 다음과 같이 계산할 수 있습니다. 이것만 알아도, 보다 쉽게 약수의 갯수를 구할 수 있습니다. 조금 더 나아간다면, n과 n+1은 서로소관계이므로, 을 적용할 수 있습니다. 그래서 n이 짝수인 경우와 홀수인 경우로 나누고, 동적 프로그래밍을 이용하면, 빠르게 원하는 답을 얻을 수 있습니다. 프로젝트 오일러 사이트에 가보면, 어떤분은 수십초가 걸렸다고 하는데요. 제 경우에는 노트북에 가상머신을 잡고 리눅스를 돌렸는데, time으로 실행시간을 .. 2014. 12. 29.
#11 : 그리드에서 가장 큰 곱수 구하기(Brute Force) 이번 문제는 사실 효율적인 알고리즘을 찾기가 어렵네요. 난이도 5%로 아주 쉬운 문제로 평가되어 있는 문제입니다. 탐욕 알고리즘을 이용해서 풀어볼려고 시도를 했는데, 탐욕 알고리즘이 늘 최선의 결과를 내는 것이 아니고, 오히려 정렬하는 시간 때문에 속도 향상을 기대하기 힘드네요. 400개의 데이터를 정렬하는 것 자체가, 순차적으로 모든 곱을 계산하는 것보다 기본적으로 점근적 접근상 더 큰 값을 가지니까요. 효율로 따져서 득 될 것이 없다고 생각했습니다. 제가 처음에 생각했던 탐욕 알고리즘은, 가장 큰 수부터 차례대로 근처에 있는 곱을 계산하고, 현재의 최대값이 다음 가장 큰수의 네제곱수보다 크다면, 거기서 종료하는 방법이었습니다. 이 알고리즘으로 한다면, 제일 큰 곱수를 구할 수 있습니다만, 과연 이게 .. 2014. 12. 28.
728x90

티스토리툴바