알고리즘 입문 - 1부터 n까지 연속한 정수의 합

알고리즘이란?

입력 >> 알고리즘 >>출력

알고리즘은 어떤 문제를 풀기 위한 절차나 방법
알고리즘은 주어진 '입력'을 '출력'으로 만드는 과정
알고리즘의 각 단계는 구체적이고 명료해야 함

한 가지 문제를 푸는 여러 가지 방법, 즉 여러 가지 알고리즘 중에 상황에 맞는 적당한 알고리즘을 골라 쓰려면 어떤 알고리즘이 어떤 특징을 지니고 있으며 얼마나 계산이 빠르고 편한지 등을 알아야 한다.

이처럼 알고리즘의 성능이나 특징을 분석하는 것을 '알고리즘 분석' 이라고 한다.

1부터 n까지 연속한 숫자의 합을 구하는 문제를 풀기 위한 알고리즘

1. 첫번째 방법 (숫자를 차례로 더하는 방법)

• 입력 값 n이 커질수록 덧셈을 훨씬 더 많이 반복해야 함
• n번의 복잡도 (계산량, 수행 시간)를 지닌다.

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

def sum_n(n):
	s = 0					# 합을 계산할 변수
    for i in range(1, n+1): # 1부터 n까지 반복(n + 1은 제외)
    	s = s + i 
    return s

print(sum_n(10))			# 실행결과: 50
print(sum_n(100)			# 실행결과: 5050

2. 두번째 방법
   

• n 값의 크기와 관계없이 덧셈, 곱셈, 나눗셈을 각각 한 번씩만 하면 답을 얻을 수 있음
• 3번의 복잡도를 지닌다.

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

def sum_n(n):
    return (n * (n + 1)) // 2 	#슬래시 두 개(//)는 정수 나눗셈

print(sum_n(10))			# 실행결과: 50
print(sum_n(100)			# 실행결과: 5050

- 1에서 n까지의 수가 아니라 주어진 n개의 수라면?

• 주어진 수를 더해라
  ex) [ 4, 6, 1, 10, 4,...., 11 ]
• 수의 개수는 n개

두 번째 알고리즘으로 풀 수 없다.