[ALGORITHMS]문제 01 1부터 n까지의 합 구하기

오늘부터 모두의 알고리즘 with 파이썬이란 책으로 알고리즘 공부를 시작하도록 하겠습니다.

문제 1

1부터 n까지의 합 구하기

1.알고리즘의 중요 포인트

-문제

1부터 n까지 연속한 숫자의 합 구하기

-입력

n을 입력 

-출력

1부터 n까지의 연속한 숫자의 합 출력 하기

2. 구체적이고 명료한 계산 과정

ex)1부터 10까지 합 구하기

1) 1+2를 계산한 결과 3을 기억하고 있습니다

2) 기억해둔 3에 숫자 3을 더해 6을 기억합니다

3) 숫자 10까지 반복합니다

4) 마지막에 기억된 55를 출력합니다

3.1부터 n까지 합을 구하는 알고리즘

1) 합을 기록할 변수 s를 만들고 0을 저장합니다

2) 변수 i를 만들어 i부터 n까지의 숫자를 1씩 증가시킵니다

3) [반복]기존의 s에 i를 더하여 얻은 값을 다시 s에 저장합니다.

4) 반복이 끝났을 때 s에 저장된 값을 출력합니다

*1부터 n까지 연속한 숫자의 합을 구하는 알고리즘 1

4.알고리즘 분석

알고리즘은 문제를 푸는 절차나 방법입니다.

문제를 푸는 방법이 한가지만 있는게 아니듯이

1부터 n까지 연속된 숫자의 합을 구하는 알고리즘은 최소 2가지가 있습니다

가우스의 합 공식을 쓴 알고리즘( n(n+1)/2)를 이용해서 프로그램을 짜보도록 하겠습니다

*1부터 n까지 연속한 숫자의 합을 구하는 알고리즘 2

이렇게 주어진 문제를 푸는 여러가지 방법 중 어떤 방법이 더 좋은 것인지 판단 할 때 필요한 것이 알고리즘 분석입니다

5.입력 크기와 계산 횟수

알고리즘에는 입력이 필요한데 입력 크기가 알고리즘의 수행 성능에 영향을 미칠 때가 많습니다

입력 크기가 커지면 당연히 알고리즘 계산도 복잡해집니다

1부터 n까지의 합을 구하는 문제에서는 n의 크기가 입력 크기입니다

첫번째 알고리즘에서 10까지의 합을 구하려면 덧셈을 10번, 100까지 합을 구하려면 덧셈을 100번 해야합니다

그러나 두번째 알고리즘은 입력 크기 n이 아무리 큰 수여도 덧셈을 한번 곱셈을 한 번

나눗셈을 한번하면 결과를 얻을 수 있습니다.

첫번쨰 알고리즘 : 덧셈 n번

두번째 알고리즘 : 덧셈, 곱셉, 나눗셈 각 한번(총 3번)

입력 크기 n이 작을 떄에는 두 가지 방법이 큰 차이가 나지 않지만

입력 크기 n이 커지면 커질 수록 엄청난 차이가 나게 됩니다

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

어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한지 나타낸 정도를 '계산 복잡도'(complexity)'라고 합니다. 계산 복잡도를 표현하는 방법에는 여러가지가 있는데, 그중 대문자 O 표기법을 가장 많이사용합니다(빅 오 표기법이라고 합니다)

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

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

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

*연습문제

1-1 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램을 for 반복문으로 만들어보세요

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

정답: n가 비례하므로 O(n)입니다

1-3 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 공식은 n(n+1)(2n+1)/6으로 알려져 있습니다. for 반복문 대신 이 공식을 이용하면 알고리즘의 계산 복잡도는 O(1)과 O(n) 중 무엇이 될까요?

정답: n과 무관해지므로 O(1)이 됩니다