11강 재귀호출 sum(Python Algorithm 11 Recursive call sum)

11강 재귀호출 sum(Python Algorithm 11 Recursive call sum)

 

부제 : 알고리즘을 배우면서 파이썬 기초부터 RPG까지 정복

내용 : 초중고 또는 코딩 기초 입문자를 위한 누구나 따라 배울 수 있는 Python Algorithm 프로그램 기초 강의

 

1. 파이썬 기초 입문자

2. 알고리즘 기초에서 수학 기초

3. 기초 코딩

4. Text RPG Project

 

[동영상강의]

https://youtu.be/dc0fJlpPpjU

 

Python-Algorithm-11-재귀호출-sum.pdf

0.33MB

 

 

11. 재귀호출-합(sum)

알고리즘 첫 강의 때 배운 sum.py 를 재귀호출로 구현을 해 봅시다.

 

sum.py

# 1부터 n까지 연속한 숫자의 합을 구하는 알고리즘 
# 입력 : n
# 출력 : 1부터 n까지의 숫자를 더한 값

def sum_n(n): # 함수명에는 마지막에 반드시 콜론(:) 를 붙여야 함
    s = 0  # 합을 계산할 변수
    for i in range(1, n+1) : # 1부터 n까지 반복 (n+1)은 제외
        # s = s + i
        s += i
    return s

print(sum_n(10))
print(sum_n(100))

 

지금 다시 보니까 굉장히 눈에 익죠?

조금씩 배워 나가는 것이 나중에 큰 힘이 되어 돌아오는 것입니다.

1부터 n까지의 합을 고등학교때 배우는데 이것을 수식으로 나타내보면 다음과 같습니다.

 

$$
1 + 2 + 3 + \cdots + (n-1) + n = { {n(n+1) } \over 2}
$$


내친김에 고등학교 때 배우는 제곱의 합을 한번 구현해 볼까요?

$$
1^2 + 2^2 + 3^2 + \cdots + (n-1)^2  + n^2 = {{ n(n+1)(2n+1)} \over 6}
$$


예를 들어 1부터 3까지의 제곱의 합을 구하기 위해 n 에 3을 대입해 봅시다. 


$$
{{3 \times (3+1) \times (2 \times 3 + 1) } \over { 6}} ={ { 3 \times 4 \times 7} \over 6}=14
$$


$1^2 = 1$

$2^2 = 4$

$3^2 = 9$

$ 1 + 4 + 9 = 14 $

 

 

그리고 세제곱의 합도 배웁니다. 

 

 

$$
1^3 + 2^3 + 3^3 + \cdots + (n-1)^3 + n^3 = \left \{ { {n(n+1)} \over {2}  } \right \} ^2
$$

 

제곱은 영어로 square 이므로 함수명을 sum_sq 로 했습니다. 


다시 제곱의 합으로 돌아와서 머릿속에서 생각을 해 봅시다. 

- 처음에 0을 둡니다. 
- 제일 먼저 1의 제곱을 구해야 하니 1을 두번 곱합니다. 
- 그 나온 값에 2를 두번 곱해서 더합니다. 
- 그 다음 3을 두번 곱해서 더합니다.
- 그럼 제곱의 합을 구하는 것이 됩니다. 

 

 

프로그래밍을 해 봅시다. 

 

# 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 알고리즘 
# 입력 : n
# 출력 : 1부터 n까지의 숫자를 제곱해서 더한 값

def sum_sq(n):
  sum = 0
  for i in range(1, n+1):
    sum = sum + i * i
  return sum 

print(sum_sq(10))
print(sum_sq(100))

 

385
338350

 

이것을 수학 공식으로 다시 코딩을 해 봅시다

 

 

sum_sq2.py

# 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 알고리즘 
# 입력 : n
# 출력 : 1부터 n까지의 숫자를 제곱해서 더한 값

def sum_sq(n):
    return n * (n+1) * (2*n+1) // 6 # 연산자 // : 몫연산자(floor division)
                                    # 몫을 구하는 연산자입니다. 

print(sum_sq(10)) # 385
print(sum_sq(100)) # 338350

 

연산자(operator) 를 한개 배우고 갑시다.

나눗셈을 하면 몫과 나머지가 나오죠.

 

20을 7로 나누면 몫이 2가 나오고 나머지가 4가 나옵니다.

 

 

$$
20 = 7 \times 2 + 6
$$

 

 

 

몫에 해당하는 2가 우리가 일반적으로 사용하는 자연수인데 음수까지 다루게 되면 정수가 됩니다 .

참고로 숫자의 나눗셈에서 나머지는 0, 1, 2, 3 처럼 0 또는 자연수가 나오는 것을 알 수 있습니다.

수학적으로 나타내어 보면

$$
A = B \times Q + R
$$

 

 

A : 나누어 지는 수

B : 나누는 수

Q : 몫

R : 나머지 (0, 1, 2, 3, 4, $ \cdots $)

 

 

연산자 // 은 몫을 구하는 것입니다. 
연산결과가 정수가 나옵니다. 

 

 

제곱의 합을 구할 때 정수가 나오므로 몫연산자(floor division : // ) 를 사용한 것입니다.

floor division 을 연습해 봅시다.

참고로 / 는 나누기 입니다. 자세한 것은 후에 연산자 강의에서 하기로 하고 오늘은 그냥 나누기는 알 수 있으니 테스트만 해봅니다.

 

 

>>> 10 // 3
3   
>>> 8 // 7
1   
>>> 10 / 3
3.3333333333333335
>>>

 

1부터 n 까지의 합도 floor division 을 이용해 구현해 봅시다. 

 

 

sum.py

# 1부터 n까지 연속한 숫자의 합을 구하는 알고리즘 
# 입력 : n
# 출력 : 1부터 n까지의 숫자를 더한 값

def sum_sq(n):
    return n * (n+1) // 2  

print(sum_sq(10)) # 55
print(sum_sq(100)) # 5050

 

 

세제곱의 합도 구해 봅시다. 

세제곱은 cubic 이므로 sum_cu 로 했습니다. 

 

sum_cu.py

 

# 1부터 n까지 연속한 숫자의 세제곱의 합을 구하는 알고리즘 
# 입력 : n
# 출력 : 1부터 n까지의 숫자를 세제곱해서 더한 값

def sum_cu(n):
  sum = 0
  for i in range(1, n+1):
    sum = sum + i * i * i
    # s += i * i * i
  return sum 

print(sum_cu(10))  # 3025
print(sum_cu(100)) # 25502500

 

3025
25502500

 

sum_cu2.py

# 1부터 n까지 연속한 숫자의 세제곱의 합을 구하는 알고리즘 
# 입력 : n
# 출력 : 1부터 n까지의 숫자를 세제곱해서 더한 값

def sum_cu(n):
    return n * (n+1) // 2 * n * (n+1) // 2  

print(sum_cu(10))  # 3025
print(sum_cu(100)) # 25502500

 

 

이제 재귀호출로 n 까지의 합을 구현해 봅시다. 

 

 

sum_recur.py

# 1부터 n까지 연속한 숫자의 합을 구하는 알고리즘 
# 입력 : n
# 출력 : 1부터 n까지의 숫자를 더한 값

def sum_recur(n):
    if n == 0:   # 종료조건
                 # == : 같음을 확인하는 비교연산자
      return 0

    return sum_recur(n-1) + n 

print(sum_recur(10)) 
print(sum_recur(100)) 

 

sum_recur2.py

 

# 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 알고리즘 
# 입력 : n
# 출력 : 1부터 n까지의 숫자를 제곱해서 더한 값

def sum_recur(n):
    if n == 0:   # 종료조건
      return 0

    return sum_recur(n-1) + n*n
    # return sum_recur(n-1) + n*n*n

print(sum_recur(10))  # 3025
print(sum_recur(100)) # 25502500

 

합에 대해서 여러가지 구현도 해보고 재귀호출로도 구현을 해 보았습니다. 

그럼 이만 강의를 마치고 아마 다음 강의는 최댓값 찾기가 될 듯 싶습니다.

코딩 소프트웨어 교육에 도움이 되었다면 구독 좋아요 해 주세요.

큰 힘이 됩니다.  참,,,, 아두이노 강의를 오랫동안 못했는데 이번 주 내로 한 강의를 올리도록 하겠습니다. 파이썬 기초와 알고리즘이 아무래도 더 중요해서 여기에 신경을 많이 쓰고 있습니다.