4알고리즘 분석

 

알고리즘은 문제를 푸는 절차나 방법입니다. 그런데 어떤 문제를 푸는 방법이 한 가지만 있을까요? 보통은 그렇지 않습니다. 1부터 100까지의 합을 구하는 문제만 해도 최소 두 가지 방법이 있습니다.

하나는 앞에서 만든 프로그램처럼 1부터 100까지의 숫자를 차례로 더하는 방법이고, 다른 하나는 수학 천재 가우스가 어렸을 적 주변을 놀라게 했다는 방법입니다(가우스보다 훨씬 더 오래 전인 피타고라스 시절부터 알려진 방법이라는 설도 있습니다).

다른 친구들이 숫자를 하나씩 더하느라 고생할 때 가우스는 그림 1-3과 같은 원리를 이용해 순식간에 답을 구했다고 합니다.

 

그림 1-3 가우스의 방법

 

이러한 발견을 일반화해서 만든 1부터 n까지의 합 공식은 다음과 같습니다.

 

 

이 공식을 이용해 ‘1부터 n까지 연속한 숫자의 합 구하기’ 문제를 푸는 파이썬 프로그램을 만들면 다음과 같습니다.