[Algorithm] 파이썬으로 1부터 n까지의 합 구하기

안녕하세요~! 저번 포스팅에서 파이썬과 파이참을 설치하는 방법에 대해 알아보았는데요,

 

설치한 파이썬으로 오늘부터 알고리즘 공부를 차차 해보겠습니다.

 

알고리즘은 간단히 설명하면 '어떤 문제를 풀기 위한 절차나 방법'을 말합니다.

 

주어진 '입력'을 '출력'으로 만드는 과정이며, 알고리즘의 각 단계는 구체적이고 명료해야 합니다.

 

하지만 어떤 문제를 푸는 과정은 꼭 한가지로 한정되는 것은 아닙니다. 

 

프로그래밍적인 측면에서 바라보면, 어떤 문제를 풀기 위해서는 여러가지 방법(알고리즘)을 사용할 수 있지만,

 

가장 최적의 속도를 이끌어 내기 위해서 어떤 알고리즘이 어떤 특징을 지니고 있는지 알아야 합니다.

 

이처럼 알고리즘의 성능이나 특징을 분석하기 위해서는 어려운 수학적 지식이 많이 필요하지만,

 

앞으로 포스팅에서 복잡한 수학적 증명 없이 직접 문제를 다뤄 보면서 알고리즘을 분석하는 감을 기르도록 하겠습니다.

 

그렇다면 오늘의 문제를 알아보겠습니다.

 

문제. 1부터 n까지의 합을 구하는 알고리즘을 만들어 봅시다.

 

학창시절에 꽤 많이 접해봤을법한 문제입니다. 

 

이 문제를 다르게 말하면 n을 입력하면 결과값을 출력해주는 프로그램을 만들어라. 정도로 해석할 수 있습니다.

 

그렇다면 다음으로는 문제를 풀기 위한 알고리즘을 최대한 구체적으로 적어보겠습니다.

 

1. 합을 기록할 변수 sum을 0으로 선언해 준다.

 

2. 변수 i를 만들어 1부터 n까지의 숫자를 1씩 증가시키며 반복한다.

 

3. 기존의 sum에 i를 더해주고 그 값을 다시 sum에 저장한다.(반복)

 

4. 반복이 끝나면 sum값을 출력해 준다.

 

이제 이 과정을 파이썬 코드로 작성을 해 보겠습니다.

 

def algorithm_sum(n):
    sum = 0  				#합을 담아줄 변수 sum을 선언
    for i in range(1, n+1): #함수를 매개변수로 받은 n만큼 반복
        sum = sum + i		#sum에 i를 반복해서 더해줌
    return sum				#sum을 리턴


print(algorithm_sum(100))	#100을 매개변수로 넘겨받는 algorithm_sum 함수의 리턴값을 출력

아주 간단한 식이 완성되었습니다.

하지만 알고리즘을 푸는 방법에는 여러가지가 있다고 말씀을 드렸었죠?

 

어렸을 적 1부터 100까지의 합을 구할 때 (1+100)*50을 해서 아주 쉽게 답을 구할 수 있다는 걸 다들 알고 계실 겁니다.

이 공식을 이용해서 코드를 짜 보겠습니다.

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


print(algorithm_sum(1000))

식이 더 짧아졌습니다. 이렇듯 똑같은 문제도 여러가지 시야에서 접근할 수 있고,

 

그 중에서 더 효율적인 방법을 찾아가는 것이 알고리즘 분석입니다.

 

알고리즘을 계산할 때 계산이 얼마나 복잡한지 나타낸 정도를 '계산 복잡도(complexity)'라고 합니다.

 

계산 복잡도를 표현하는 방법은 여러가지가 있지만 그 중 대문자 O 표기법(빅 오 표기법)을 많이 사용합니다.

 

앞에서 살펴본 예제를 예로 설명해드리면, 첫번째 식은 입력 숫자 n에 대해 사칙 연산을 n번 해야합니다.

 

이 때 이 알고리즘의 복잡도를 O(n)이라고 표현합니다. 필요한 계산 횟수가 입력 크기에 정비례하기 때문입니다.

 

두 번째 식은 입력 숫자 n과 무관하게 사칙연산을 세 번 해야합니다.

 

입력 숫자 n과 필요한 계산의 횟수가 무관하다면 계산 복잡도는 O(1)로 표기합니다.

 

대문자 O 표기법은 알고리즘의 대략적인 성능을 표시하는 방법으로, 세밀한 계산 횟수나 소요 시간을 표시하기보다

 

입력 크기 n과 필요한 계산 횟수와의 관계에 더 주목하는 표현법입니다.

 

O(n) : 필요한 계산 횟수가 입력 크기 n과 비례할 때

O(1) : 필요한 계산 횟수가 입력 크기 n과 무관할 때

 

그렇다면 어떤 것이 더 빠른 알고리즘일까요?

 

문제에 주어지는 평균 입력 크기나 각 알고리즘의 실제 계산 방식 등에 따라 차이는 있지만,

 

보통 입력 크기가 큰 문제를 풀 때는 O(1)인 알고리즘이 더 빠릅니다.

 

오늘은 아주 간단한 문제를 풀기 위해 알고리즘의 정의부터 자세히 알아보았는데요,

 

자료구조와 알고리즘이 프로그래밍에 있어서 아주 중요하다고 생각되는 만큼 열심히 공부해서

 

어려운 문제도 뚝딱뚝딱 해결할 수 있는 개발자가 되어 봐요! ^_^

 

 

 

출처:이승찬, 『모두의 파이썬X알고리즘』