.jpg)
01-1 알고리즘이란?
알고리즘(algorithm)은 무엇일까요?
Wikipedia에서 찾아본 알고리즘의 정의는,
어떠한 문제를 풀어맺기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것입니다
세 정수의 최댓값 구하기
다음은 세 정수의 최댓값을 구하는 문제에 대한 코드입니다.
이 예시를 통해, 알고리즘에 대해 자세히 알아보겠습니다!
# max3.py
a = int(input('정수 a의 값을 입력하세요: '))
b = int(input('정수 b의 값을 입력하세요: '))
c = int(input('정수 c의 값을 입력하세요: '))
maximum = a
if b > maximum : maximum = b
if c > maximum : maximum = c
print(f'최대값은 {maximum}입니다')
실행결과는 위와 같습니다.
알고리즘 순서도
또한 알고리즘 순서도를 통해 알고리즘의 흐름을 대략적으로 파악할 수 있습니다
순서도(flowchart)는 문제를 정의/분석하고 해결하는 방법을 그림으로 나타낸 것입니다
순서도에는 다음과 같은 기호가 있습니다
1) 실제로 실행할 연산을 나타내는 기호
2) 제어 흐름을 나타내는 선 기호
3) 프로그램 순서도를 이해하거나 작성하는데 편리한 특수기호
알고리즘 순서도의 기호들은 다음과 같이 정의할 수 있습니다.
- 처리 : 연산이나 연산 집합의 실행을 나타냅니다
- 판단 : 하나의 입구와 하나 이상의 출구가 있으며, 주로 예상되는 평가 결과는 경로를 나타낸 선 가까이에 표기합니다
- 단말(터미널) : 외부 환경으로 나가거나 들어오는 것을 나타냅니다. 주로 프로그램의 시작과 종료를 나타냅니다
마름모 기호인 Decision(판단)안에 작성한 조건식에 따라 흐름이 두 갈래로 나뉘는 것을 볼 수 있는데요, 이것을 양 갈래 선택이라 합니다.
이제 위에서 만든 max3.py를 제대로 만들었는지 확인하기 위해서, 먼저 함수를 정의한 후에,
다양한 Input을 주어 평가해 보겠습니다.
def max3(a, b, c):
""" a, b, c의 최댓값을 구하여 반환"""
maximum = a
if b > maximum : maximum = b
if c > maximum : maximum = c
print(f'max(3, 2, 1) = {max3(3,2,1)}')
print(f'max(2, 2, 3) = {max3(2,2,3)}')
print(f'max(1, 3, 2) = {max3(1,3,2)}')
print(f'max(3, 3, 3) = {max3(3,3,3)}')실행결과
다음과 같이 다양한 입력값에 대해 잘 작동하는 것을 확인할 수 있습니다
올바른 알고리즘
지금까지 해본 내용을 바탕으로 알고리즘을 다음과 같이 정의할 수 있습니다
알고리즘 : 어떠한 문제를 해결하기 위해 정해 놓은 일련의 절차
특히 올바른 알고리즘이란, 어떠한 경우에도 실행 결과가 똑같이 나오는 것을 말합니다.
만약 알고리즘의 실행 결과가 항상 참이 아닌 경우에는 올바른 알고리즘이라 부를 수 없습니다!!
이번에는 세 정수의 중앙값을 구하는 함수 2가지를 작성해볼까 하는데요, 이를 통해 알고리즘의 효율성을 비교해보도록 하겠습니다
세 정수의 중앙값 구하기
# 세 정수를 입력받아 중앙값 구하기 1
def med3(a, b, c):
"""a, b, c의 중앙값을 구하여 반환"""
if a >= b:
if b >= c:
return b
elif a <= c:
return a
else:
return c
elif a > c:
return a
elif b > c:
return c
else:
return b
print('세 정수의 중앙값을 구합니다.')
a = int(input('정수 a의 값을 구하세요: '))
b = int(input('정수 b의 값을 구하세요: '))
c = int(input('정수 c의 값을 구하세요: '))
print(f'중앙값은 {med3(a,b,c)}입니다.')실행결과
다음과 같이 세 정수의 중앙값을 구할 수도 있습니다
# 세 정수를 입력받아 중앙값 구하기 2
def med3(a, b, c):
"""a, b, c의 중앙값을 구하여 반환"""
if (b>=a and c <= a) or (b <= a and c >= a):
return a
elif (a > b and c < b) or (a < b and c > b):
return b
return c아래의 코드는 위의 것보다는 짧지만 프로그램의 효율은 위보다 좋지 않을 것입니다.
if (b>=a and c <= a) or (b <= a and c >= a):
elif (a > b and c < b) or (a < b and c > b):
위의 if문의 조건식이 성립하지 않는 경우 (a > b와 a < b)는 이어지는 elif문에서 판단할 필요가 없지만, 판단을 하고 있으므로 당연히 비효율적이게 될 것입니다.
즉 a와 b의 비교를 이미 마친상태에서 다시 비교하는 것이 효율적이지 못하다는 의미입니다.
01-2 반복하는 알고리즘
지금부터는 간단한 반복 알고리즘을 살펴보겠습니다!
1부터 n까지 정수의 합 구하기
1부터 n까지의 합을 구하는 코드를 작성해 보겠습니다.
# 1부터 n까지 정수의 합 구하기 (while문)
print('1부터 n까지 정수의 합을 구합니다')
n = int(input('n값을 입력하세요: '))
sum = 0
i = 1
while i <= n:
sum += i
i += 1 # i를 1씩 증가시킨다
print(f'1부터 {n}까지 정수의 합은 {sum}입니다.')실행결과
위 코드의 flowchart는 아래와 같습니다.
sum값에 i를 계속더하는데, i는 n보다 작을때까지 1씩 증가시킵니다.
이로써 1부터 n까지의 합을 구할 수 있는 것이었습니다.
위의 프로그램은 while문을 사용했는데요, 이제 for문을 이용해서도 작성해보겠습니다.
# 1부터 n까지 정수의 합 구하기 (for문)
print('1부터 n까지 정수의 합을 구합니다')
n = int(input('n값을 입력하세요: '))
sum = 0
for i in range(1, n+1):
sum += i
print(f'1부터 {n}까지 정수의 합은 {sum}입니다.')실행결과
for문을 사용한 코드와 순서도는 위와 같습니다.
또한 가우스의 덧셈을 이용하여 1부터 n까지의 합을 구할 수 있습니다
sum = n * (n+1) / 2
파이썬의 변수 알아보기
이 내용은 책 1장의 마지막 보충 내용으로 되어있었는데요, check up하면 좋은 내용이므로 정리하고 가겠습니다!
파이썬에서는 데이터, 함수, 클래스, 모듈 등 모두 객체로 취급합니다. 이런 특성으로 인해 우리는 흔히 파이썬은 객체 지향적인 언어라고 부르기도 합니다. 객체는 자료형(data type)을 가지며 메모리(저장 공간)을 가지고 있습니다.
파이썬의 변수는 값을 갖지 않는 특징이 있는데요, 예를 들면 x = 17이라 해도, x는 17이라는 값을 가지고 있지 않습니다! 변수는 객체를 참조하는 객체에 연결된 이름에 불과합니다. 또한 모든 객체는 메모리를 차지하고, 자료형뿐만 아니라 identity를 가집니다.identity는 다른 객체와 구별할 수 있는 객체의 고유 번호를 말합니다
아래의 예시를 통해 객체의 identity를 확인해보겠습니다!
n = 17
print(id(17))
print(id(n))140705304676528
140705304676528위의 결과를 통해 n과 17이 같은 객체를 나타내는 것을 알 수 있습니다!
즉 17의 identity와 n의 identity가 같다고 할 수 있습니다
위에서 보듯이 파이썬에서는 변수는 객체의 단순한 이름에 불과합니다. 만약 n의 값을 17이 아닌 다른 값으로 바꾸면, 새로운 값에 대한 객체를 n이 참조하게 될 것이며, n의 식별 번호 역시 갱신될 것입니다
다음 프로그램에서는 함수의 외부와 내부에서의 정의한 변수의 identity를 출력해보는 것입니다.
# 함수 내부/외부에서 정의한 변수와 객체의 식별 번호 출력하기
n = 1 # global variable
def printId():
x = 1 # local variable
print(f'id(x) = {id(x)}')
print(f'id(1) = {id(1)}')
print(f'id(n) = {id(n)}')
printId()실행결과
id(1) = 140705240188592 id(n) = 140705240188592 id(x) = 140705240188592함수 외부에서 정의한 전역 변수(global variable) n과 함수 내부에서 정의한 지역 변수(local variable) x는 int형 객체 1과 같은 identity를 갖는 것을 알 수 있습니다
따라서 n과 x는 int형 객체 1을 참조하는 이름에 불과하다는 것입니다!
C언어와 비교하면 이상한 부분이 있습니다! C언어의 경우 local variable은 함수가 종료되면서 소멸되는데요, 파이썬은 지역변수 x가 살아있다는 것을 확인할 수 있었습니다. int형 객체 1은 함수의 생성/소멸과 상관없이 존재하기 때문입니다!
마지막으로 1부터 10까지 id를 출력하는 프로그램을 만들어보겠습니다
# 1부터 10까지 id 출력하기
for i in range(1, 11):
print(f'i = {i:3} id(i)={id(i)}')실행결과
i = 1 id(i)=140705240188592 i = 2 id(i)=140705240188624 i = 3 id(i)=140705240188656 i = 4 id(i)=140705240188688 i = 5 id(i)=140705240188720 i = 6 id(i)=140705240188752 i = 7 id(i)=140705240188784 i = 8 id(i)=140705240188816 i = 9 id(i)=140705240188848 i = 10 id(i)=140705240188880i가 1씩 증가하면서 id값이 갱신되는 것을 알 수 있었습니다. 또한 id값이 32씩 증가함을 확인할 수 있었는데요, 32bit이기 때문인 것 같습니다!
Reference
- Do it! 자료구조와 함께 배우는 알고리즘 입문: 파이썬 편, Chapter 01
