파이썬 알고리즘 1 부터 n까지의 합 구하기 #2

파이썬 알고리즘 1 부터 n까지의 합 구하기 #2

 

안녕하세요.

 

아마 프로그래밍 언어를 많이 공부하신 분들은 지겨우실 수도 있는 주제가 되겠네요.

 

사실.. 정보처리기사에서도 자주 출제되는 문제이기도 하구요.

 

개념을 잘 알고 있지만, 파이썬이라는 걸 처음 접하거나, 생소하신 분들은 이걸 어떻게 구현해야 하나? 고민이 많으실 수 있습니다.

 

그래도 우리가 파이썬을 시작하였으니, 하나하나 벽돌 쌓아 집을 짓듯 그렇게 한 발짝씩 나아가 보겠습니다.

 

1부터 n까지 합을 구하는 알고리즘 역시 많은 방법이 있습니다.

 

이미 여러분들 머릿속에 있는 것들부터 한번 볼까요?

 

만약 n이 100이라고 가정한다면, 그 과정은 아래와 같을 수 있습니다.

 

자, 위의 그림과 같이 1+2를 한 결과 3을 기억하고,

 

3+3을 한 결과 6을 기억하고..

 

그렇게 100까지 하나씩 더하는 방법이 있을 것이고요.

 

1부터 100까지 나열해 둔 상태에서 처음수와 마지막수을 더한 결과 101을 50번 곱해주는 방법도 있겠네요!

 

1편에서도 말씀드렸었지만 알고리즘은 정말 많이 있습니다.

 

이런 다양한 알고리즘 속에서 과연 어떤 방법이 효율적이고, 프로그램으로 구현이 가능한지, 판단해야 합니다.

 

자, 그럼 위 두 가지 방법을 파이썬 코드로 구현해볼 차례입니다.

 

def sum_num(n):
    s = 0  # 합의 결과를 저장하는 변수
    for i in range(1, n + 1):  # 반복문
        s = s + i
    return s

print(sum_num(10))   # 1부터 10까지 합(입력:10, 출력:55)
print(sum_num(100))  # 1부터 100까지 합(입력:100, 출력:5050)

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

print(sum_num(10))   # 1부터 10까지 합(입력:10, 출력:55)
print(sum_num(100))  # 1부터 100까지 합(입력:100, 출력:5050)

자, 코드를 보면 어떤 게 어떤 그림과 매칭이 되는지 알 수 있으신가요?

 

많은 분들은 '에이, 저건 누구나 아는 거지..' 하실 분들도 많이 계시겠지만 처음 코딩을 접하시는 분들은 이런 것조차 어려울 수 있습니다.

 

한 줄 한줄 잘 읽어보면 알 수 있습니다. 산수와 비슷하다고 할까요?

 

자, 그럼 두 알고리즘의 답은 어차피 똑같이 나옵니다.

 

그리고 우리가 컴퓨터에서 실행해보신 분들은 아시겠지만 시간도 별 차이 나지 않는 것 같아요.

(물론, 변수가 100 정도로 작기 때문일 수 있습니다.)

 

두 알고리즘의 차이를 계산 차원에서 생각해 보면, 어떨까요?

 

첫 번째 알고리즘의 답을 구하기 위해서는 n-1번만큼의 계산 과정을 거쳐야 답이 나옵니다.

 

1+2, 3+3, 6+4,.................... 이렇게...

 

두 번째 알고리즘은 n과 상관없이 더하기, 곱하기, 나누기 이렇게 한 번씩만 하면 답이 나오겠죠?

 

단 세 번의 계산으로 정답을 알 수 있습니다.

 

지금 방금 제가 설명드리고 여러분들이 이해한 것이 알고리즘의 분석 과정입니다.

 

그리고 계산을 몇 번 해야 하는지에 대한 것도 우리는 계산 복잡도라는 용어로 표현할 수 있습니다.

 

첫 번째 알고리즘의 계산 복잡도는 O(n)이라 표현할 수 있습니다.

 

"O"는 계산 횟수를 나타내는 기호이고, 괄호 안에 들어가는 n은 그 횟수를 말합니다.

 

누군가 저 기호를 보면 몇 번 계산을 해야 답이 나온다 라고 생각이 들겠죠?

 

 O(n) 이라 표현한 것은 입력되는 변수에 따라 n번 계산한다가 되겠습니다.

 

그리고 두 번째 알고리즘의 계산 복잡도 표현은 어떻게 하는 게 좋을까요?

 

O(3) 일까요? 아닙니다. O(1)로 표현합니다.

 

숫자는 계산 횟수라기보다 입력값에 상관없이 계산 횟수는 같다고 표현하는 기호라고 생각하시면 될 것 같습니다.

 

자 그럼, 이젠 어떤 알고리즘을 선택해야 하는지 감이 오시나요?

 

그렇죠! O(1)의 계산 복잡도를 가진 두 번째 알고리즘을 선택하는 것이 훨씬 효율적이라고 볼 수 있겠죠.

 

자, 오늘은 여기까지 하겠습니다.

 

다음에 다시 다른 알고리즘으로 찾아오겠습니다.

 

감사합니다.

 

 

 

# 포스팅은 길벗출판사의 모두의 파이썬X알고리즘 도서를 참고로 작성하였습니다.

 

by.sTricky