모두의 알고리즘 문제 04. 팩토리얼 구하기 연습문제

# 연습문제 4-1. 1부터 n까지의 합 구하기를 재귀호출로 만들기.
def re_sum_n (n):
    if n <= 1:
        return 1
    return n+re_sum_n(n-1)

print(re_sum_n(10)) # 결과: 55
print(re_sum_n(100)) # 결과: 5050



# 연습문제 4-2, 숫자 n개 중에서 최댓값 찾기를 재귀 호출로 만들어 보세요.
l=[23,34,22,42,12,52,38,52,24,41]

def re_find_max (l, n):  # l은 리스트, n은 리스트의 전체 자료 개수

    if n==1:  #자료 개수가 1개면 그대로 반환
        print("n = ", n, "max_n =", l[0])
        return l[0]

    max_n = re_find_max(l, n-1) # 전체 자료 개수 하나 줄여서 재귀호출. n=2이면 맨 처음값 반환받고 그걸 최대값으로.

    if max_n > l[n-1]: # n=2일때 맨 처음값을 최댓값으로 두고 맨 끝값을 차례대로 비교.
        print("n = ", n, "max_n = ", max_n, "max_n이 다음위치의 원소보다 값이 더 커서 max_n은 그대로 유지")
        return max_n

    else:
        print("n = ", n, "max_n = ", max_n, "max_n의 다음자리가 값이 더 커서 다음자리 값을 반환")
        return l[n-1]

#맨 처음값을 최댓값으로 가정하고 다음값과 비교한 후, 리스트의 길이를 1씩 늘임과 동시에 비교할 리스트 끝자리의 원소도 한자리씩 넘어가며 최댓값과 차례대로 비교.

#최댓값, 비교하는 수: 맨 첫번째 자리의 값, 첫번째 자리보다 높은 각 단계의 비교대상.

# 비교 대상: 리스트가 늘어날때마다 갱신되는 리스트 맨 끝자리의 원소. n=5일때는 l[4](l[n-1])자리의 값과 최댓값을 비교한다.

print(re_find_max(l, len(l)))

연습문제 2의 출력은 다음과 같다.

 

n =  1 max_n = 23
n =  2 max_n =  23 max_n의 다음자리가 값이 더 커서 다음자리 값을 반환
n =  3 max_n =  34 max_n이 다음위치의 원소보다 값이 더 커서 max_n은 그대로 유지
n =  4 max_n =  34 max_n의 다음자리가 값이 더 커서 다음자리 값을 반환
n =  5 max_n =  42 max_n이 다음위치의 원소보다 값이 더 커서 max_n은 그대로 유지
n =  6 max_n =  42 max_n의 다음자리가 값이 더 커서 다음자리 값을 반환
n =  7 max_n =  52 max_n이 다음위치의 원소보다 값이 더 커서 max_n은 그대로 유지
n =  8 max_n =  52 max_n의 다음자리가 값이 더 커서 다음자리 값을 반환
n =  9 max_n =  52 max_n이 다음위치의 원소보다 값이 더 커서 max_n은 그대로 유지
n =  10 max_n =  52 max_n이 다음위치의 원소보다 값이 더 커서 max_n은 그대로 유지
52

 

 

연습문제 1은 이론공부하며 배운 코드를 응용하면 됐는데 2는 달라서 결국 답지를 봤다. 리스트 외에 리스트의 길이도 매개변수로 줘야하는 지는 몰랐다.

 

연습문제 2는 코드를 반복해서 보고, 각 과정마다 상황을 출력하고, 직접 구조도를 써보니까 대강 이해가 가긴 하는데 내가 닥친 상황에서 응용하진 못할 거 같다. 바로 떠올리기엔 내 이해력이 낮다.

 

일단 글로 정리하며 생각을 정리하도록 해야겠다.

 

 

리스트a의 길이가 5일 때. 즉 원소가 5개 들어있을 때.

 

findMax(a, n). a는 리스트 이름, n은 리스트 길이.

 

1. findMax(a, 5) -> findMax(a, 4) -> findMax(a, 3) -> findMax(a, 2) -> findMax(a, 1) 순으로 함수가 호출된다.

 

2. findMax(a, 1)은 리스트의 1번째 값인 a[n-1] 즉 a[0]을 findMax(a, 2)에 반환한다.

 

3. findMax(a, 2)는 반환받은 a[0]과 리스트의 마지막 값인 a[n-1] 즉 a[1]을 비교한 후 더 큰 값을 findMax(a, 3)에 반환한다.

 

4. findMax(a, 3)은 findMax(a, 2)에서 반환받은 최대값과 findMax(a, 3)일 때 리스트의 마지막 값인 a[2]의 값을 비교한 후 더 큰 값을 findMax(a, 4)에 반환한다.

 

5. findMax(a, 4)는 반환받은 최대값과 리스트의 마지막 값인 a[3] 즉 a[n-1]값을 비교한 후 더 큰 값을 findMax(a, 5)에 반환한다.

 

6. findMax(a, 5)는 반환받은 a[0]부터 a[3]을 비교한 후 나온 최대값과 a[4]를 비교한 후 더 큰 값을 반환한다.

 

 

리스트 길이를 하나씩 줄이고 원소가 하나만 남았을 때 첫 번째 값을 일단 반환받으며 최대값으로 잡고, 리스트 길이를 첫번째 값과 그 다음값만 있게끔 즉 길이를 2로 만든 후 이 둘을 비교한다.

그 후 리스트 길이를 하나씩 늘리며 비교할 수를 하나씩 넘어가게 하고 하나씩 넘어오는 수와 기존의 최대값이 서로 비교한다. 비교하고, 리스트 늘어나고, 덩달아 생긴 새로운 끝자리 원소와 기존 최대값이 비교된다.

 

너무 어렵다. 물론 이해는 되는데 이걸 나중에 내가 필요로할 때 생각해낼 수 있을지 의문이다.

 

 

 

일단 공부나 하자. 하면 어떻게든 되겠지.