일단... "Project Euler @kr" 88번까지 완료! ^^
우와~~~ ^^ "Project Euler @kr" 웹 사이트에서 오늘 날짜 기준으로 출제된 문제까지 모두 풀었습니다.
인증샷~~~ 나갑니다. ^^ 오~~~ 멋지죠? ^^
오일러 수학자의 명성과 함께 사이트 소개 자체가 "수학적인 문제"들이라고 해서 긴장했는데, 일단은 65번 정도까지는 별다르게 수학적인 재능이 없어도 "프로그램빨(!)"로 풀 수 있으니... '수학'이란 단어에 걸려 주춤하고 계신 분이 있다면 부담 없이 도전해 보시라고 말씀드리고 싶습니다. ^^
아래는, 프로그래머 입장에서 수학적인 지식이 요구되는 문제들만을 설명해 보았습니다.
66번 - 펠 방정식
66번에서 처음으로 수학적인 지식을 요구하는데요. '디오판토스 방정식' 문제인데 Brute-force 방식으로 했다가는 한 세월 갑니다. 가령 3번째로 큰 x 값이 "3879474045914926879468217167061449"으로 어마어마하기 때문에 이건 아무것도 안하고 for 문만 돌려도 계산이 언제 끝날지 모릅니다. 어쩔 수 없이 '펠의 방정식'에 대해서 공부해야 하는데요. ^^ 다음의 글을 읽어보시면 어떻게 풀어야 할지 해법이 나옵니다.
펠 방정식(Pell's equation)
; http://pythagoras0.springnote.com/pages/4439359
결국, sqrt 값을 알기 위하여 펠 방정식이 근사값을 구하는데 씌여질 수 있고, 그 방정식에 해를 구하기 위해 연분수를 사용할 수 있다는 것이지만... 제 지식으로는 어떻게 '펠 방정식'의 해가 '연분수'와 연관지어지는가에 대해서는 이해가 안되는군요. ^^; 위의 웹 사이트 제목이 '수학이 알고 싶은 중고대딩을 위한 수학 노트'인데... Orz... 왜 난 이해가 안 된단 말인가???
69번, 70번, 72번 - 오일러의 φ(Phi)함수
이 방법이 아닌, 단순하게 공약수 찾는 방법을 사용했다가는 한 세월입니다. (참고로, 오일러 프로젝트의 모든 문제는 1분 안에 답이 나오도록 되어 있다고 합니다.) 오일러의 φ(Phi) 함수에 대해서는 다음의 글을 읽어보시면 도움이 되실 것입니다.
Euler's totient function
; http://en.wikipedia.org/wiki/Totient#Euler.27s_product_formula
혹시나, 여러분들 중에서 70번을 풀었는데 "9708131"이라는 오답이 나왔다면, 아래의 글을 보시면 어디가 잘못 되었는지 힌트를 얻으실 수 있습니다.
Euler's totient function - C#
; https://www.sysnet.pe.kr/2/0/1256
75번 - 피타고라스 수
피타고라스 방정식과 관련해서 9번과 39번 문제가 있었지만, 이번에는 정확하게 피타고라스 수를 생성해내는 방정식을 모르면 (적정한) 시간 내에 문제를 풀 수 없습니다. 이를 위해서는 다음의 글을 공부하시면 됩니다. ^^
피타고라스 수
; http://en.wikipedia.org/wiki/Pythagorean_triple
76번, 78번 - 점화식
76번도 수학적 지식이 요구되지만, 프로그램 실력으로 풀면 다음과 같이 풀립니다.
동전을 여러 더미로 나누는 경우의 수 세기
; https://www.sysnet.pe.kr/2/0/1271
76번과 78번을 풀 수 있으면 77번과 88번도 자연스럽게 해결됩니다.
기타, 제 경우 68번과 79번은 손으로 풀었고, 84번의 경우에는 Simulator로 풀어보라는 회사 동료의 요청에 따라 ^^ 실제로 그것을 만들어서 나온 결과로 답을 냈습니다. (Simulator가 어쨌든 확률적이라 그런지, 첫 번째에 정확하게 답이 나오지는 않았습니다. ^^)
마지막으로 아래는 제가 마인드 맵으로 그려본 80번까지의 문제들간의 관계를 나타낸 것입니다.
참고로, "
Project Euler 영문 사이트"는 371번까지 문제가 있던데... 그건 질려서 못하겠고, 우선 한국 사이트라도 충실히 따라가 봐야겠습니다. (그나저나... 초보적인 수학지식으로 몇 번까지 버틸 수 있을지는 모르겠군요. ^^)
암튼, 영문 "프로젝트 오일러"의 한글화 작업을 해 주고 있는 사이냅소프트(
http://www.synap.co.kr/)에 박수를 보냅니다. ^^
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]