책 이야기

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

13195의 소인수는 5, 7, 13, 29이다.

600851475143의 가장 큰 소인수는 무엇인가?

--------------------------------------------------------------------------

이렇게 큰 수가 나오기 때문에 프로그램을 작성하지 않으면 답을 구하기가 어려운 것이 프로젝트 오일러의 문제이다. 일단 소인수는 소수이면서 인수인 숫자이다. 12를 예로 들면 12를 나눌 수 있는 1, 2, 3, 4, 6, 12가 인수가 되며, 이 중 소수인 2, 3이 소인수가 된다.

간단히 생각해 보면 2가지 접근이 가능하다. 2부터 1씩 키워가면서 나눠지는 숫자(나머지가 0)이면서 소수인 숫자 중 가장 큰 수를 찾는 방법이 있고, 소수를 구해놓고 600851475143을 나눌 수 있는 가장 큰 숫자를 구하는 방법도 있다.

인수를 구하고 소수인지 판별하는 전자의 방법으로 해결했으며, 함수를 이용하여 소수 여부를 확인하였다.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

피보나치 순열에서 새 항은 이전 두 항을 합해서 구해진다. 1과 2로 시작하면 첫 10개 항은 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...가 된다.

피보나치 순열에서 4백만이 넘지 않는 항 중 짝수인 항의 합계를 구하시오.

--------------------------------------------------------------------------

피보나치 순열 새 항의 값이 4백만 이하인 동안, 짝수인 항을 더해서 답을 구하면 된다. 변수 4개로 답을 구하는 것이 더 간단하지만, 리스트를 활용해서 답을 구했다.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

10 이하의 자연수 중 3과 5의 배수인 수는 3, 5, 6, 9이며, 이들의 합은 23이다.

1000 이하의 자연수 중 3과 5의 배수의 합계를 구하시오.

--------------------------------------------------------------------------

접근 방법에 따라 다양한 해결방법이 있을 문제인다, 가장 중요한 것은 공배수를 처리해줘야 한다는 것이다.

1,000 이하의 3의 배수, 5의 배수 합계에 15의 배수를 빼는 형태로 구할 수 있지만, 3 또는 5의 배수의 합계를 구하는 형태로 해결하였다.

최근에 파이썬에 대한 관심이 생겨 문법을 공부하기 시작했는데, 책과 인터넷으로 문법을 읽기만 하는 것 보다는 프로그램을 실제로 작성해 볼 필요를 느끼게 되었다.

큰 규모 프로그램을 작성하기에는 아직 기초 문법만 공부하고 있는 상황이어서, 좀 간단하면서도 문법을 다양한 형태로 응용할 방법을 고민하던 중 찾게 된 것이 프로젝트 오일러이다.

프로젝트 오일러는 문제가 나와 있고 이를 프로그램으로 해결하여 답안을 제출하면 정답이 맞는지 확인하는 방식으로 되어 있는데, 정답만을 확인하기 때문에 허술해 보이지만 수학문제 정답으로 꼽히는 -1, 0, 1이 답안이 아니라 많은 반복을 통해 구할 수 있는 큰 숫자가 답안이기 때문에 문제를 알고리즘으로 바꿔 정확한 프로그램을 작성하고 실행해야 답안을 얻을 수 있다.

파이썬 문법 공부보다는 알고리즘, 논리, 수학에 대해 다시 생각해 보는 일이 더 많기도 했지만, 숫자, 문자열, 리스트, 딕셔너리 등 파이썬에서 제공하는 자료형, 파일 입출력, 함수 등 파이썬 문법을 다양한 방식으로 활용해보고 이해할 수 있게 하는 기회가 되고 있다.

문제를 해결하고 나면 다른 사람의 해결방안을 확인해 보기도 하는데, 답안을 구하기 위한 로직 중심으로 프로그램을 작성하기 때문에 훨씬 많은 시간이 걸려 답을 구하는 것을 보면서 많이 놀라고 있다. 그리고, 예전 언어에 비해 파이썬이 얼마나 작성하기 편한지도 느끼고 있고.

뒤로 갈수록 난이도는 높아지고 파이썬 보다는 수학 지식이 더 필요한 경우가 많아지게 되고 있기 때문에 현재 기준 840개 문제를 모두 풀지는 않을 것 같지만, 파이썬을 편하게 활용할 수 있을 때까지는 풀고 있을 것 같다.(지금으로 봐서는 100번 전후가 될 것 같다)