반응형 Euler Project2 8. 프로젝트 오일러 #8 : 가장 큰 곱하기 수 구하기. 이 문제는 문서에서 단어찾기에도 이용할 수 있는 문제입니다. 단어찾기의 경우에는 보통 더하기 해시를 이용하든지 하겠지만, 여기서는 곱하기이기 때문에 일단 숫자 범위가 넘어가는지 생각해보는 것도 필요합니다. 그리고 0이란 숫자가 있기 때문에 좀 골치 아픕니다. 13개의 단자리 곱셈이기 때문에 최대 숫자는 9의 13제곱인 2,541,865,828,329이 됩니다. 약 20억정도의 숫자를 표시하는 int 형으로는 오버플로우가 발생할 수 있습니다. 그래서 int64 자료형을 이용해서 프로그램을 작성해야 합니다. 4개의 숫자를 가지고 한다고 하면, 7316717653 의 숫자의 경우, 7x3x1x6 3x1x6x7 1x6x7x1 ... 과 같이 하나씩 이동하면서 4개씩 곱해주어도 됩니다. 그렇지만, 7 3 1 6 .. 2014. 12. 23. 프로젝트 오일러 #1 3 또는 5의 배수의 합 대학 과제에서 보면, 1부터 100까지 다 더하는 프로그램을 만드세요라는 문제가 많이 나옵니다. 대부분 결과는 for 루프를 이용해서 답을 구하고 있습니다. (물론 문제 출제 의도는 for 루프를 잘 쓸 수 있는지를 보는 것이니 당연하다고 할 수도 있겠죠.) 그렇다고 해서, 1부터 n까지 합을 구하는 가장 기본적인 공식을 알고 있다면, 굳이 for 루프를 돌리지 않아도, 계산을 할 수 있습니다. for 루프를 돌린다면, \(O(n)\)만큼의 시간이 기본적으로 듭니다. 그렇지만, 등차수열의 합 공식을 이용하면, 상수 시간으로 계산을 할 수 있습니다. 사실 더해야 하는 범위가 오일러 프로젝트의 문제처럼 1,000정도라면, 프로그램 실행시간은 사람이 눈치챌 수 없을 정도입니다. 해당 숫자 범위 안에서 m배수만.. 2014. 12. 18. 이전 1 다음 728x90