파이썬 a부터 b까지 더하기 - paisseon abuteo bkkaji deohagi

이 문제를 풀기 위한 중요 포인트는 두 가지이다. 한 가지는 1000 미만의 자연수를 구하는 방법이고 또 다른 한 가지는 3과 5의 배수를 구하는 것이다. 이 두 가지만 해결되면 문제는 쉽게 해결될 것으로 보인다.

1. 먼저 1000 미만의 자연수는 어떻게 구할 수 있을지 생각해 보자. 여러 가지 방법이 떠오를 것이다. 다음과 같이 변수에 초깃값 1을 준 후 루프를 돌리며 1씩 증가시켜서 999까지 진행하는 방법이 가장 일반적인 방법일 것이다.

n = 1
while n < 1000:
    print(n)
    n += 1

또는 다음과 같이 좀 더 파이썬다운 range 함수를 사용할 수도 있다.

for n in range(1, 1000):
    print(n)

두 가지 예 모두 실행하면 1부터 999까지 출력하는 것을 확인할 수 있다.

2. 1000까지의 자연수를 차례로 구하는 방법을 알았으니 3과 5의 배수를 구하는 방법을 알아보자. 1000 미만의 자연수 중 3의 배수는 다음과 같이 증가할 것이다.

3, 6, 9, 12, 15, 18, …, 999

그렇다면 1부터 1000까지 수가 진행되는 동안 그 수가 3의 배수인지는 어떻게 알 수 있을까? 1부터 1000까지의 수 중 3으로 나누었을 때 나누어떨어지는 경우, 즉 3으로 나누었을 때 나머지가 0인 경우가 바로 3의 배수이다. 따라서 다음과 같이 % 연산자를 사용하면 3의 배수를 쉽게 찾을 수 있다.

for n in range(1, 1000):
    if n % 3 == 0:
        print(n)

그렇다면 5의 배수는 n % 5가 0이 되는 수로 구할 수 있을 것이다.

3. 이러한 내용을 바탕으로 만든 최종 풀이는 다음과 같다.

result = 0
for n in range(1, 1000):
    if n % 3 == 0 or n % 5 == 0: 
        result += n
print(result)

3과 5의 배수에 해당하는 수를 result 변수에 계속해서 더해 주었다.

이 문제에는 한 가지 함정이 있는데 3으로도 5로도 나누어지는 15와 같은 수를 이중으로 더해서는 안 된다는 점이다. 따라서 15와 같이 3의 배수도 되고 5의 배수도 되는 값이 이중으로 더해지지 않기 위해 or 연산자를 사용하였다.

다음 예는 15와 같은 수를 이중으로 더하여 잘못된 결과를 출력하는 잘못된 풀이이다.

[잘못된 풀이]

result = 0
for n in range(1, 1000):
    if n % 3 == 0:
        result += n
    if n % 5 == 0:
        result += n
print(result)

이 문제는 코딩 연습을 할 수 있는 "프로젝트 오일러"라는 사이트의 첫 번째 문제이다. 이 사이트는 첫 번째 문제부터 차례대로 풀 수 있으며 본인이 작성한 답이 맞는지 즉시 확인할 수도 있다.

2. 1부터 n까지의 합을 구하는 알고리즘

1. 반복문 사용

2. 재귀 함수 사용

3. 가우스 등차수열의 합 공식 사용

2.1. 반복문 사용

>>> def sum_iter(n):
	total = 0
	for i in range(1, n+1):
		total += i
	return total

>>> sum_iter(100)
5050

반복문을 사용한 1부터 n까지의 합을 구하는 방법은 매우 간단하게 for문 반복문을 이용해서 1부터 n까지의 값을 range() 함수로 반복시켜 그 값을 total값에 더해 쉽게 구할 수 있다.

2.2. 재귀 함수 사용

>>> def sum_rec(n):
	if(n < 2): return 1
	else: return n + sum_rec(n-1)

	
>>> sum_rec(100)
5050

재귀 함수는 함수를 선언하고 해당 함수에서 자기 자신을 재귀 호출(Recursive Call)하는 함수를 말한다. 1부터 n까지의 합을 구하는 알고리즘에서 굳이 사용할 필요는 없겠지만 기본적인 재귀 함수의 개념을 이해하기엔 좋은 예제이다.

재귀 함수를 처음 보는 경우 이게 어떻게 작용하는지 이해하지 못하는 경우가 많은데 그런 분들을 위해 코드를 살짝 변형해서 재귀 호출이 어떻게 이루어지는지 확인해보겠다.

>>> def sum_rec_chk(n):
	if n < 2: return 1
	else:
		print(f'n + sum_rec_chk({n}-1): {n} + {n-1}')
		return n + sum_rec_chk(n-1)

	
>>> sum_rec_chk(10)
n + sum_rec_chk(10-1): 10 + 9
n + sum_rec_chk(9-1): 9 + 8
n + sum_rec_chk(8-1): 8 + 7
n + sum_rec_chk(7-1): 7 + 6
n + sum_rec_chk(6-1): 6 + 5
n + sum_rec_chk(5-1): 5 + 4
n + sum_rec_chk(4-1): 4 + 3
n + sum_rec_chk(3-1): 3 + 2
n + sum_rec_chk(2-1): 2 + 1
55

코드 실행 결과만 보고는 아직까지 이해하기 어려울 수 있어 설명을 덧붙이자면 sum_rec_chk(10)을 최초 호출했을 때 조건문에 의해 print() 함수로 문자열을 출력하고 n + sum_rec_chk(n-1)을 반환하는 것을 볼 수 있다. 여기서 중요한 점은 return문에서 n + sum_rec_chk(n-1)를 반환하기 위해 sum_rec_chk(n-1)을 다시 호출한다.

표로 작성해보면 이런 식으로 재귀 호출이 이루어져 10 + 9 + 8 + ... + 2 + 1 = 55가 결국 return문에서 반환되게 된다. 재귀 함수를 처음 배울 때 이해가 바로 된다면 좋겠지만 그렇지 못한 경우 위 표처럼 각각 값의 진행에 따른 테스트를 직접 해보면 이해하기보다 수월할 것이다.

2.3. 가우스 등차수열의 합 공식 사용

>>> def sum_gauss(n):
	return int(n*(n+1)/2)

>>> sum_gauss(100)
5050

등차수열의 합 공식을 사용하면 반복문을 사용하지 않고 빠르게 1부터 n까지의 합을 구할 수 있다. 그러나 반복이나 재귀를 사용하지 않기 때문에 각 숫자에 대한 조건을 부가할 수 없어 추가적인 요구사항이 있을 경우 적용하지 못한다는 단점이 있다.