캐시 (2) 썸네일형 리스트형 [EP 023] 두 과잉수의 합으로 나타낼 수 없는 모든 수의 합 완전수는 자신보다 작은 약수의 합이 자신과 같은 수이다. 예로는 6, 28 등이 있다. 과잉수는 이 합이 자신보다 큰 것을 말한다. 두 과잉수의 합으로 나타낼 수 없는 모든 양의 정수의 합은? 자신을 포함하는 모든 약수의 합, 즉 약수함수가 곱셈적이라는 성질 때문에 재귀함수를 만들거나 캐시리스트를 만드는 방식으로 "쪼개서" 문제를 해결하는 전략을 쓸 수 있다. 아래코드는 s 라는 리스트에 약수함수값을 저장하여 n의 약수함수값을 s[n] 으로 가져올 수 있고, n = p q 일 때에, 가장 작은 소수인수를 만나면, s(n) = s[p] s[q] 라는 성질을 이용하여, 차례대로 s 리스트를 채우는 방식으로 문제를 풀어본 것이다. # PROJECT EULER # PROBLEM 23 def s_f(n): """.. [Euler Project 114] 몇 칸짜리 격자를 빨간색이나 검은 색으로 채운다. 이 조건만 있으면 단순히 2의 n승으로 답이 끝난다. 조건은 빨간색은 최소한 연속 3칸 이상 이어져 있어야 한다는 조건이 추가되어 문제가 복잡해진다. 제일 처음 칸 부터 한칸씩 빨간색을 칠할 지, 검은 색을 칠할지를 결정하는 함수를 구성했고, 이 함수를 재귀적으로 불렀다. 어차피 한 칸을 채운 다음에는 남은 몇 칸에 대해 고민하는 것은 똑같으니까. 이전에 빨간색이 아니었다면, 빨간색이 오면 3칸이 무조건 칠해진다. 경우의 수가 줄어든다. 그리고 마지막에 3칸 미만이 남아 있으면 무조건 검정색이 들어갈 수밖에 없다. 뭐 이런 조건들을 함수에서 분기해야 했다. 처음에는 완성된 격자를 다 프린트하는 함수를 만들어서 예시로 주어진 7칸 짜리를 해 봤고, 50을 .. 이전 1 다음
