본문 바로가기

recursion

 (7)
[EP 092] T(n) = n의 각 자리수의 제곱의 합. T(T(T(..(n)...))) = n 이 되는 n은 1과 89 # http://projecteuler.net # Problem 92 # 2 2 2 2 2 # 89 -> 8 + 9 = 145 -> 1 + 4 + 5 = 42 -> 20 -> 16 -> 37 -> 58 -> 89 -> ... -> 89 # 1 -> 1 -> 1 from functools import lru_cache import time from tqdm import tqdm BIGN = 10 ** 7 sol_dict = dict() sol_dict[0] = 0 sol_dict[1] = 1 sol_dict[89] = 89 digit_sq = [i * i for i in range(10)] @lru_cache def arrives_at_89_recur(n: int): if n == 0 or n == 1 o..
재귀 시험지 분배 비유 재귀에 대한 비유가 생각나서 써 봄. 학교 다녀 본 사람은 시험시간에 시험지를 나누는 두가지 방법이 있는 것을 안다.1. 선생님이 돌아다니면서, 모든 사람에게 하나씩 시험지를 나누어 준다.2. 매 줄마다 학생수만큼 시험지를 맨 앞사람에게만 주고, 시험지 더미을 받은 사람은 자신이 하나를 갖고, 시험지 더미를 뒷사람에게 준다. 즉, 대략 def 시험지나눠주기(시험지더미, 학생들):# 학생들 = [ 학생1, 학생2, 학생3, ..., 학생n ]for 학생 in 학생들:시험지하나주기(학생)시험지더미-=1 def 시험지나눠주기뒤로넘기기(시험지더미, 학생들):# 학생들 = [ 학생1, 학생2, 학생3, ... 학생n ]학생들[0].시험지하나갖기() # 학생들[0] 은 시험지를 받은 학생들 리스트의 첫번째 학생시험..
nCr 캐시된 재귀함수로 구하기 Python 3.4.4 (v3.4.4:737efcadf5a6, Dec 20 2015, 20:20:57) [MSC v.1600 64 bit (AMD64)] on win32Type "copyright", "credits" or "license()" for more information.>>> def nCr(n, r):if r in (n, 0);SyntaxError: invalid syntax>>> @functools.lur_cache(maxsize=200, typed=False)def nCr(n, r):if r in (n, 0):return 1return nCr(n-1, r-1) + nCr(n-1, r) Traceback (most recent call last): File "", line 1, in @fu..
stack overflow 메모리 탐구. stack overflow 가 날 때 실제 메모리 주소를 찍어 보고, 그 값을 vmmap 툴과 비교해 봤다. 재귀함수(recursive fuction)를 배울 때 가장 많이 듣는 유의점이, 재귀함수는 stack overflow 를 유발할 수 있기 때문에 주의하라라는 말이다. 재귀함수를 이용하여 문제를 발생시켰다.재귀함수 내부에 지역변수를 하나 생성하였고, 그 지역변수의 주소를 찍었다. sysinternals 의 vmmap 툴은 프로세스를 선택하면 해당 프로세스의 메모리 공간의 각 부분이 어떤 영역으로 잡히는 지를 보여준다. 우리의 관심사는 stack 이고, stack은 0x00030000 ~ 0x00130000 영역에 잡혀있다. 첫번째 그림에서 찍힌 첫번째 r의 주소는 0x12ff48 스택 중에서도 윗부..
[Euler Project 114] 몇 칸짜리 격자를 빨간색이나 검은 색으로 채운다. 이 조건만 있으면 단순히 2의 n승으로 답이 끝난다. 조건은 빨간색은 최소한 연속 3칸 이상 이어져 있어야 한다는 조건이 추가되어 문제가 복잡해진다. 제일 처음 칸 부터 한칸씩 빨간색을 칠할 지, 검은 색을 칠할지를 결정하는 함수를 구성했고, 이 함수를 재귀적으로 불렀다. 어차피 한 칸을 채운 다음에는 남은 몇 칸에 대해 고민하는 것은 똑같으니까. 이전에 빨간색이 아니었다면, 빨간색이 오면 3칸이 무조건 칠해진다. 경우의 수가 줄어든다. 그리고 마지막에 3칸 미만이 남아 있으면 무조건 검정색이 들어갈 수밖에 없다. 뭐 이런 조건들을 함수에서 분기해야 했다. 처음에는 완성된 격자를 다 프린트하는 함수를 만들어서 예시로 주어진 7칸 짜리를 해 봤고, 50을 ..
[Euler Project 164] 연속된 세 개의 자리수의 합이 9를 넘지 않는 20자리수 연속된 세 개의 자리수의 합이 9를 넘지 않는 20자리수의 갯수를 구하라. ( http://projecteuler.net/index.php?section=problems&id=164 ) def get_count(n1, n2, remain): #print " "*(20 - remain), n1, n2, remain if cache.has_key((n1, n2, remain)): return cache[(n1, n2, remain)] count = 0 sum = n1 + n2 if remain == 1: cache[(n1, n2, remain)] = 10 - sum return 10 - sum for n3 in range(10 - sum): count += get_count(n2, n3, remain - 1..
[Py] 숫자 리스트와 합이 주어졌을 때, 리스트의 합이 주어진 합인 부분 리스트 찾기 #----------------------------------------------------- def is_in_list(lst, lstlst): lst.sort() bRet = False for e in lstlst: e.sort() if len(e) == len(lst): bRet = True for i in range(len(e)): if e[i] != lst[i]: bRet = False break return bRet #----------------------------------------------------- def find_combination(sum, list): # print "---------" # print "-----------", sum, list, "------------..

티스토리툴바