01-1 알고리즘이란?

Jeongyun Heo·2021년 1월 5일

알고리즘

목록 보기

2/2

참고: Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편

알고리즘 기초

알고리즘이란?

여기서는 알고리즘(algorithm)이란 무엇인지 간단한 프로그램을 통해 알아보고 알고리즘의 기초를 학습한다.

세 정수의 최댓값 구하기

print('세 정수의 최댓값을 구합니다.')

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}입니다.')

👉
세 정수의 최댓값을 구합니다.
정수 a의 값을 입력하세요.: 1
정수 b의 값을 입력하세요.: 3
정수 c의 값을 입력하세요.: 2
최댓값은 3입니다.

input 함수는 문자열을 반환하므로 문자열을 정수형으로 변환해야 한다. 이 때 int() 함수를 사용한다.

한 문장씩 순서대로 처리되는 구조를 순차 구조(sequential structure)라고 한다.

if와 콜론(:) 사이에 있는 식을 조건식이라고 한다.

조건식으로 평가한 결과에 따라 프로그램의 실행 흐름이 변경되는데 이러한 구조를 선택 구조(select structure)라고 한다.

문자열과 숫자 입력받기

이름을 문자열로 입력받아 화면에 출력하는 프로그램이다.

# 이름을 입력받아 인사하기
print('이름을 입력하세요.: ', end='')
name = input()
print(f'안녕하세요? {name} 님.')

👉 
이름을 입력하세요.: 박서진
안녕하세요? 박서진 님.

input() 함수는 키보드로 '문자열'을 입력받아 반환한다.

input(문자열)로 호출하면 아래와 같이 print 함수 호출을 생략할 수 있다.

# 이름을 입력받아 인사하기
name = input('이름을 입력하세요.: ')
print(f'안녕하세요? {name} 님.')

input 함수는 문자열을 반환하므로 문자열을 정수형으로 변환해야 한다. 이 때 int() 함수를 사용한다. int() 함수는 인자로 문자열을 전달받는다.

형 변환(type conversion): 문자열형을 정수형으로 변환하는 과정

문자열을 정수로 '형 변환'해보자

2진수, 8진수, 10진수, 16진수를 나타내는 문자열을 각각 정수로 변환할 때는
int(문자열, 진수)와 같이 2개의 인수를 전달받는다.

>>> int('17')         # 10진수 문자열을 10진수 정수형으로 변환 (기본)
17
>>> int('0b110', 2)   # 2진수 문자열을 10진수 정수형으로 변환
6
>>> int('0o75', 8)    # 8진수 문자열을 10진수 정수형으로 변환
61
>>> int('13', 10)     # 10진수 문자열을 10진수 정수형으로 변환
13
>>> int('0x3F', 16)   # 16진수 문자열을 10진수 정수형으로 변환
63
>>> float('3.14')     # 문자열을 실수형으로 변환
3.14

숫자로 변환할 수 없는 문자열을 함수에 전달하면 오류가 발생한다.

float는 부동 소수점 방식을 사용한다.

부동 소수점(floating point)은 컴퓨터에서 실수를 근삿값으로 표현할 때 사용한다. 부동 소수점 방식은 실수를 가수 부분과 지수 부분으로 나누어 표현하는 것을 말한다.

알고리즘(프로그램)이 흐르는 방향은 조건식이 결정한다.
이때 작성한 조건식에 따라 알고리즘 흐름이 두 갈래로 나뉘는 것을 양 갈래 선택이라고 한다.

복합문의 구조

if문이나 while문 등 복합문의 첫 부분은 if나 while과 같은 키워드로 시작하여 콜론(:)으로 끝난다.
이 부분을 헤더(header)라고 한다.
헤더의 마지막 콜론(:)은 '바로 뒤에 스위트가 이어집니다'를 의미한다.

※ 스위트(suite)는 헤더와 한 세트로 따라다니는 '실행문'을 의미한다.

if식: 스위트    👈 if문 : 반드시 1개 필요
elif식: 스위트  👈 elif문 : 없어도 되고, 있으면 n개 가능
else식: 스위트  👈 else문 : 없어도 되고, 있으면 1개 가능

세 정수의 최댓값을 구하는 프로그램에 어떠한 숫자가 주어지더라도 최댓값을 잘 구할 수 있는지 확인하자.

일일이 값을 입력하면서 테스트하기보다는 프로그램처럼 작성하는 것이 좋다.

def max3(a, b, c):
    """a, b, c의 최댓값을 구하여 반환"""         # docstring
    maximum = a
    if b > maximum: maximum = b
    if c > maximum: maximum = c
    return maximum  # 최댓값 반환


print(f'max3(3, 2, 1) = {max3(3, 2, 1)}')  # {} 안에 함수 호출한 거 넣어도 되는구나
print(f'max3(3, 2, 2) = {max3(3, 2, 2)}')
print(f'max3(3, 1, 2) = {max3(3, 1, 2)}')
print(f'max3(3, 2, 3) = {max3(3, 2, 3)}')
print(f'max3(2, 1, 3) = {max3(2, 1, 3)}')
print(f'max3(3, 3, 2) = {max3(3, 3, 2)}')
print(f'max3(3, 3, 3) = {max3(3, 3, 3)}')
print(f'max3(2, 2, 3) = {max3(2, 2, 3)}')
print(f'max3(2, 3, 1) = {max3(2, 3, 1)}')
print(f'max3(2, 3, 2) = {max3(2, 3, 2)}')
print(f'max3(1, 3, 2) = {max3(1, 3, 2)}')
print(f'max3(2, 3, 3) = {max3(2, 3, 3)}')
print(f'max3(1, 2, 3) = {max3(1, 2, 3)}')

👉
max3(3, 2, 1) = 3
max3(3, 2, 2) = 3
max3(3, 1, 2) = 3
max3(3, 2, 3) = 3
max3(2, 1, 3) = 3
max3(3, 3, 2) = 3
max3(3, 3, 3) = 3
max3(2, 2, 3) = 3
max3(2, 3, 1) = 3
max3(2, 3, 2) = 3
max3(1, 3, 2) = 3
max3(2, 3, 3) = 3
max3(1, 2, 3) = 3

"""은 파이썬의 docstring으로 여러 줄의 주석을 입력할 때도 사용한다. 들여쓰기에 주의하여 입력하자.

함수의 반환값과 함수 호출식 평가하기

함수 내부에서 처리한 값을 반환할 때에는 return문을 사용하면 된다. 또한 실제로 함수가 반환하는 값을 얻으려면 함수를 호출해야 하며, 이를 '함수 호출식을 평가해야 함수가 반환한 값을 얻을 수 있다'고 한다.
예를 들어 max3(3, 2, 1)과 같이 함수를 호출하면 세 값을 평가하여 3이라는 반환값을 얻을 수 있다.

지금까지 배운 내용을 바탕으로 알고리즘을 정의하면 다음과 같다.

알고리즘: 어떠한 문제를 해결하기 위해 정해 놓은 일련의 절차

특히 올바른 알고리즘이란 '어떠한 경우에도 실행 결과가 똑같이 나오는 것'을 말한다.
max3() 함수에 어떤 값을 넣더라도 최댓값을 잘 구하는지 확인한 이유도 그 때문이다.

복합문을 작성할 때 지켜야 할 규칙

복합문의 스위트는 반드시 행마다 같은 수준으로 들여쓰기를 해야 한다.
PEP 8(파이썬의 코드 작성 규칙)에서는 공백(Spacebar) 4개를 들여쓰기로 사용할 것을 권장한다.

if a < b:
    min2 = a  # 공백 4개로 들여쓰기
    max2 = b  # 이 문장도 공백 4개로 들여쓰기를 해야 if a < b:에 종속되어 실행됨

만약 스위트가 단순문이면 헤더와 같은 행에 둘 수 있다. 또한 단순문이 2개 이상이면 각각의 단순문을 세미콜론(;)으로 구분하여 다음과 같이 헤더와 같은 행에 둘 수 있다. 이때 세미콜론은 마지막 단순문 뒤에 놓을 수도 있다.

if a < b: min2 = a             # 단순문 1개
if a < b: min2 = a; max2 = b   # 단순문 2개
if a < b: min2 = a; max2 = b;  # 단순문 2개(세미콜론을 추가한 단순문)

하지만 스위트가 복합문이면 헤더와 스위트를 같은 행에 포함시킬 수 없다. 다음과 같은 코드는 콜론 뒤에 복합문이 포함되었으므로 오류가 발생한다.

if a < b: if c < d: x = u  # 오류 발생! 헤더와 같은 행에 복합문을 둘 수 없음

👉 SyntaxError: invalid syntax

파이썬 스타일 가이드 PEP 8

파이썬에서는 PEP 8 문서를 통해 파이썬의 일관된 규칙을 가이드로 제공한다.
예를 들어 클래스명은 카멜 케이스(CamelCase) 형식으로 쓰고, 함수명은 스네이크 케이스(snake_case) 형식으로 쓸 것을 권장한다. 또한 들여쓰기를 할 때 공백(Spacebar)을 4개 사용하도록 권장하는 내용도 PEP 8 문서에 있다.

PEP 8 -- Style Guide for Python Code
https://www.python.org/dev/peps/pep-0008/

세 정수의 대소 관계와 중앙값

세 정수의 대소 관계 나열하기
세 정수 a, b, c의 대소 관계 조합 13가지
조합을 나열한 모습이 나무처럼 생겨서 결정 트리(decision tree)라고 한다.
결정 트리는 왼쪽에서 시작하여 오른쪽으로 나아간다. 조건이 성립하면 위쪽 선을 따라가고, 성립하지 않으면 아래쪽 선을 따라간다.
오른쪽 끝은 정수 a, b, c의 대소 관계를 나타낸다. 즉, 이 프로그램에서는 A~M으로 표시한 대소 관계 조합 13가지의 최댓값을 구한다.

세 정수의 중앙값 구하기
중앙값을 구하는 절차는 최댓값, 최솟값을 구할 때에 비해 복잡하다. 그래서 다양한 알고리즘을 생각할 수 있다.
다음은 a, b, c의 중앙값을 구하는 프로그램이다.
※ 중앙값(median)은 주어진 값을 크기 순서대로 정렬했을 때 가장 중앙에 위치하는 값을 의미한다. 평균값(mean)과 헷갈리지 말자.

# 세 정수를 입력받아 중앙값 구하기 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)}입니다.')

👉
세 정수의 중앙값을 구합니다.
정수 a의 값을 입력하세요.: 1
정수 b의 값을 입력하세요.: 3
정수 c의 값을 입력하세요.: 2
중앙값은 2입니다.

med3() 함수는 다음과 같이 작성해도 된다. 위 프로그램과 비교해보자.

# 세 정수를 입력받아 중앙값 구하기 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

print('세 정수의 중앙값을 구합니다.')
a = int(input('정수 a의 값을 입력하세요.: '))
b = int(input('정수 b의 값을 입력하세요.: '))
c = int(input('정수 c의 값을 입력하세요.: '))

print(f'중앙값은 {med3(a, b, c)}입니다.')

👉
세 정수의 중앙값을 구합니다.
정수 a의 값을 입력하세요.: 1
정수 b의 값을 입력하세요.: 3
정수 c의 값을 입력하세요.: 2
중앙값은 2입니다.

위 프로그램의 코드는 짧지만 프로그램의 효율은 첫 번째 프로그램보다 좋지 않다.

처음 나오는 if문에서 a와 b의 비교를 마쳤고 거짓이어서 elif문으로 넘어가는데 굳이 또 elif문에서 a와 b를 비교하고 있다. 이미 위에 있는 if문에서 비교를 했는데 또 비교하는 건 당연히 효율적이지 않다.

조건문과 분기

if 조건문은 분기를 위한 문법이다.
분기는 '둘 이상으로 갈라지다'라는 뜻으로 프로그램의 흐름을 둘 이상으로 나누는 것을 말한다.

분기(branching)는 프로그램의 실행 흐름을 다른 곳으로 변경하는 명령을 뜻한다.

다음은 입력받은 정숫값의 부호(양수, 음수, 0)를 판단하여 출력하는 프로그램이다. 프로그램 흐름의 분기를 자세히 살펴보자.

# 입력받은 정수의 부호(양수, 음수, 0) 출력하기

n = int(input('정수를 입력하세요.: '))

if n > 0:
    print('이 수는 양수입니다.')
elif n < 0:
    print('이 수는 음수입니다.')
else:
    print('이 수는 0입니다.')

👉
정수를 입력하세요.: 17
이 수는 양수입니다.
정수를 입력하세요.: -5
이 수는 음수입니다.
정수를 입력하세요.: 0
이 수는 0입니다.

2개가 동시에 실행되거나 하나도 실행되지 않는 경우는 없다. 왜냐하면 프로그램의 흐름은 3개로 분기하기 때문이다.

다음 두 프로그램의 동작을 확인해보자.

# 3개로 분기하는 조건문

n = int(input('정수를 입력하세요.: '))

if n == 1:
    print('A')
elif n == 2:
    print('B')
else:
    print('C')

👉
정수를 입력하세요.: 3
C
정수를 입력하세요.: 4
C

위 프로그램은 n이 1, 2가 아니면 모두 C를 출력한다. 즉, 프로그램의 흐름이 3개로 분기한다. 다음 프로그램은 어떤지 보자.

# 4개로 분기하는 조건문

n = int(input('정수를 입력하세요.: '))

if n == 1:
    print('A')
elif n == 2:
    print('B')
elif n == 3:
    print('C')

👉
정수를 입력하세요.: 3
C
정수를 입력하세요.: 4    # 아무것도 출력하지 않음

위 프로그램은 n이 1, 2, 3이 아니면 아무것도 출력하지 않는다. 코드를 얼핏 보면 프로그램의 흐름이 3개로 분기할 것 같지만 사실은 그렇지 않다. 이 프로그램을 조금 더 분명하게 보이도록 재구성한 것이 다음 프로그램이다. 위 프로그램에는 분기에 포함되지 않은 else문이 숨어 있다. 즉, 이 프로그램의 흐름은 4개로 분기한다.

# 위 프로그램의 원래 모습

n = int(input('정수를 입력하세요.: '))

if n == 1:
    print('A')
elif n == 2:
    print('B')
elif n == 3:
    print('C')
else:
    pass             # 아무것도 수행하지 말고 그냥 지나치라는 의미

👉
정수를 입력하세요.: 3
C
정수를 입력하세요.: 4    # else문의 pass문이 실행된다.