[알고리즘:파이썬] 01. 1부터 n까지의 합 구하기

안녕하세요. 쏘피입니다. 오늘은 01. 1부터 n까지의 합 구하기 문제를 풀어보겠습니다.

---

문제: 1부터 n까지 연속한 정수의 합을 구하는 알고리즘을 만드시오.

 

---

풀이:

 

1) 입력값: N

 

2) 출력값: 1+.....+N

 

3) 계산과정:

    [1] 1+2인 3을 기억

    [2] 3+3인 6을 기억

    ...

    [N]  N-1까지 더한 것을 기억 후 +N

 

4) 계산 알고리즘:

    [1] 합을 기록할 변수 S 생성 후 0 저장

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

    [3] 기존 s+i 후 s에 값 저장

    [4] 반복이 끝났을 때 s에 저장된 값이 결괏값

 

5) 파이썬으로 구현:

  

def sum_m(n):                # def로 n 넣는 함수 만들기     s = 0                    # 값 저장할 s에 0 할당     for i in range(1, n + 1): # 1부터 n까지 반복(range는 마지막값 제외 즉 n+1은 제외)         s = s + i     return s print(sum_m(10)) #1에서부터 n까지 합하기

---

이 방법 말고 다른 방법도 있지 않을까요? 위의 방법을 방법1. 처음부터 순서대로 더하기 로 명명하겠습니다.

 

방법2. 가우스 방법으로 더하기

1)2) 입력, 출력값은 같습니다. 

3) 계산과정: 가우스 방법-> ((1+n) *n )/2 

4) 파이썬 구현:

##방법2 # 입력:n 출력: 1부터 n 더한 값 def sum_n(n):     return n * (n + 1) // 2 #슬래시 두개는 버림 나눗셈(floor division)이라고 부르며 나눗셈의 결과에서 소수점 이하는 버립니다. print(sum_n(10)) print(sum_n(11))

 

---

 

---

알고리즘 분석

---

• 방법1과 방법2 중 더 효율적인 것은?

[n= 100일때의 사칙 연산의 횟수(입력크기)]

방법1: 입력 값 n이 커질수록 덧셈 반복을 많이 해야 합니다./덧셈 100번

방법2: n 값의 크기와 관계없이 덧셈, 곱셈, 나눗셈을 각각 한 번씩만 하면 답을 얻습니다./ 덧셈,곱셈,나눗셈->3번

 

 

---

대문자 O 표기법: 계산 복잡도 표현

---

• 계산 복잡도: 어떤 알고리즘이 문제를 풀기 위해 해야 하는 계산이 얼마나 복잡한지 나타낸 정도
• 1) 시간 복잡도: 어떤 알고리즘을 수행하는데 얼마나 오랜 시간이 걸리는지 분석
• 2) 공간 복잡도: 어떤 알고리즘을 수행하는데 얼마나 많은 공간(메모리/기억 장소)가 필요한지 분석
• =>계산 복잡도는 특별한 말이 없는 한 시간 복잡도를 의미함
• 표현 방식: O() 빅오라고도 부름. 알고리즘의 대략적인 성능을 표시하는 방법, 세밀한 계산횟수나 소요 시간을 표현하기보다는 입력 크기 n과 필요한 계산 횟수의 관계에 더 주목하는 표현

- 방법1의 빅오: 입력 크기 n에 대해 사칙연산을 n번해야 함. 계산횟수가 입력 크기 n과 정비례하면 모두 O(n) 표시

- 방법2의 빅오: 입력크기 n과 무관하게 사칙연산 3번 진행-> O(1) 표시: 입력크기가 커져도 계산 시간이 더 늘어나지 않음

 

---

---

추가 연습문제

---

1-1. 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램을 for로 만들어 보시오.

 

1-2. 연습문제 1-1 프로그램의 계산 복잡도는 O(1)과 O(n) 중 무엇일까요?

 

1-3. 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 공식은 (n(n+1)(2n+1))/6 로 알려져 있습니다. 이 공식의 계산 복잡도는 무엇입니까?

 

 

---

추가 연습문제 풀이

---

 

1-1. 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램을 for로 만들어 보시오. 

# 추가 연습 문제 #1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램을 for로 만들어 보시오. #입력값: n #출력값: 1제곱+....+n 제곱 def prd(n):     s = 0     for i  in range(1, n + 1):         s = s + i*i     return s prd(3) # 1+4+9 =  14

1-2.  연습문제 1-1 프로그램의 계산 복잡도는 O(1)과 O(n) 중 무엇일까요?

O(n). 곱셈 n번, 덧셈 n번으로 사칙연산 총 2n이 필요하지만 O(n)으로 표현

 

1-3. 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 공식은 (n(n+1)(2n+1))/6 로 알려져 있습니다. 이 공식의 계산 복잡도는 무엇입니까?

O(1). 덧셈 2번 곱셈 3번 나눗셈 1번으로 사칙연산 총 6번 필요하지만 n 크기와 관계없이 일정한 값이므로 O(1)로 표현

 

문제 출처: 모두의 알고리즘 with 파이썬

이로써 첫번째 챕터는 마무리되었습니다! 아무래도 첫번째 문제다보니 친근하고 쉬운 감이 있었는데요.

앞으로 남은 17개의 챕터도 꾸준히 포스팅해보겠습니다!