재귀설계 중요코드모음 & 전수조사 재귀설계 연습의 중요 4가지 문제 비교

중요:무엇보다 재귀설계를 할때가 가장 곤혹이다. 많이 연습해 보는 방법밖에 없고 비슷한 유형의 문제를 두고 머릿속으로 그림을 그려가며 그 그림과 해당 코드의 내용을 비교하면서 그리고 문제간의 코드차이도 비교해 보면서 익숙히 하는게 장땡이다. 아래가 그 공부방법의 정확한 예시다.

피보나치와 막대기자르기의 Top-down방식 해결책에서 살펴본 코드로 바로 보이는 큰그림과 숨겨진 작은그림

def fiboTD(m,n):
    if(m[n]>0):
        return m[n]
    if(n<=2):
        return 1
    result=fiboTD(m, n-1)+fiboTD(m, n-2)#큰 그림에서 트리의 자식노드 2개의 합은 윗레벨의 부모레벨이고
    #이것은 코드에서 보는 바와같이 직관적으로 보인다. 하지만 세세한 그림은 보이지 않는 작은그림이다.
    m[n]=result
    return result

fiboTD(m, 8)
print(m)


def cuttingStickTd(p,n,m):
    if(m[n]>=0):
        return m[n]
    if(n==0):
        q=0
    else:
        q=-1                 
        for i in range(1, n+1):
            q=max(q, p[i]+cuttingStickTd(p, n-i, m))#자식노드들 여럿을 비교하여 그 중가장큰것이 
            #부모노드의 값이 된다. 이것은 코드에서 보는 바와같이 직관적으로 보인다. 핮만 세세한그린인
            #(내려갔다 올라오면서 그 각각의 자식들의 값을 구하는 그림은 보이지 않는 작은그림이다.
    m[n]=q
    return q

 

재귀함수 안의 각 코드의 중요 위상!(아래 코드로 부터 핵심을 간출임)

 

def bestSum(arr, target):

     min=None#재귀함수에서 함수초입부분에 이렇게 변수를 설정하면 그 변수는 그 단계의 그 지점에서 그 변수는 그 값을 같는 것이다. 즉, 각각의 수많은 실(방)이 있고 min은 그 구성원이다. 처음 내려갈때의 모든 실의 그 변수값은 그 초기값을 가진다. 이것은 재귀함수가 반복문 안에 있고 그 반복문안에서 이 변수를 변경하면 오직 그 실안에서의 이 변수에 영향을 미치게 되고 이 변수를 반환하게되면 그 윗레벨의 실에서 그값을 반환받아 연산에 연계시킨다. 그리고 그 값은 물론 그 레벨에서의 그 변수에 영향을 미치게될수 있는 것이다.

         #재귀함수전의 내용은 내려가면서의 상황이다
         answer=howSum(arr, target-arr[i])#재귀함수와 같은 라인의 내용은 올라가면서의 상황이다(반환받은것이므로)
         if(answer!=None):
             answer.append(arr[i])
             return answer
             #재귀함수뒤의 내용은 올라가면서의 상황이다

if(canSum(arr, target-arr[i])):#답 자체가 True인지 False인지를 요구하는 것이기
             #때문에 canSum의 결과를 다른 변수에 담을 필요없이 조건문안에 담아 코드를 더 간결하고
             #효율적으로 구성하였다. 

 def canSum(arr, target):
     if(target<0):
         return False
     if(target==0):
         return True
     for i in range(len(arr)):
         if(canSum(arr, target-arr[i])):#답 자체가 True인지 False인지를 요구하는 것이기
             #때문에 canSum의 결과를 다른 변수에 담을 필요없이 조건문안에 담아 코드를 더 간결하고
             #효율적으로 구성하였다. 
             return True
 #canSum문제 역시 howSum문제와 마찬가지로 target이 0이되는 경우 하나만 찾으면 되므로
 #찾는즉시 바로바로 return하며 올라간다
 def countSum(arr, target):
     count=0
     if(target==0):
         return 1
     if(target<0):
         return 0
     for i in range(len(arr)):
         count+=countSum(arr, target-arr[i])
     return count


 def howSum(arr, target):
     answer=list()
     if(target<0):
         return None
     if(target==0):
         return list()
     for i in range(len(arr)):
         #재귀함수전의 내용은 내려가면서의 상황이다
         answer=howSum(arr, target-arr[i])#재귀함수와 같은 라인의 내용은 올라가면서의 상황이다
         if(answer!=None):
             answer.append(arr[i])
             return answer
             #재귀함수뒤의 내용은 올라가면서의 상황이다
             #answer이 None이 아니면 다른거 볼것도 없이 그냥 그 대로 다른 거 볼것 없이 
             # 쭈욱 올라가면되므로 해당레벨의 arr[i]를 append만 해주고 바로바로 return
             # 해주고있다. 따라서 올라갈때의 코드가 위처럼 매우 간단하다


 def bestSum(arr, target):
     min=None
     if(target<0):
         return None
     if(target==0):
         return list()
     for i in range(len(arr)):
         cur=bestSum(arr, target-arr[i])
        if(cur!=None):
             if(min==None or len(min)>len(cur)):
                 cur.append(arr[i])
                 min=cur
     return min
         #bestSum의 경우 재귀호출다음라인부터인 올라가면서 그려지는 그림이 다른 3가지
         #문제보다 매우첨예하다. 우선 target이 0으로 한번도 만들어진 적이 없는 경우에서는
         # min이 None이다. 
         # 처음으로 target이 0인 상황발생-> 반환되어 한단계 위로 올라감. 거기서의 arr[i]은 어떤값
         #cur은 target이 0인 상황에서 반환된 list()을 가짐(cur=list()) -> min=None 따라서 cur.append(arr[i])
         #에 의해서 min또한 arr[i]을 가진 리스트가 되고 그 min이 한 반환되어 한단계 위로 올라감
       
         #또 한가지 더 구체화시켜서 기억해 놓아야 하는것은 target=0인 경우가 발생해 어떤 줄기를 타고 올라가
         #는 과정에서 다시 내려가는 상황이다. 이때의 min은 none이 아니다. 내려가면서 target=0인 상황이
         #발생할 것이다. 이때 cur은 다시 빈 리스트를 갖는 상황이 온다. 재밌는 건 이때 부터인데, 이렇게
         #빈 리스트를 반환하면 반환받은 한단계윗레벨에서는 min의 크기는 이전상황때문에 그안에 어떠한 하나의
         #데이터를 가지고 있다(물론 가지가 전혀 다른 쪽이라면 이때의 min역시 None일수 있음).
         #  따라서 조건문의 min==None에 걸리지 않고 무조건 len(min)>len(cur)인 상황에 걸리게 된다. 왜? 현재 
         #cur은 빈리스트이기 때문에. 조건문에 진입하면 그때서야 cur.append(arr[i])가 이루어지고 
         #min=cur에 의해 새롭게 갱신가 min이 반환된다. 즉,같은 크기의 리스트라도 더 나중에 탐색이 이루어지는
         #쪽으로 min이 수시로 갱신되는 것이다.