알고리즘 기초

알고리즘이란?

어떠한 문제를 해결하기 위한 일련의 절차

알고리즘

세 정수의 최댓값 구하기

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

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

maximum = a

위 행은 단순한 대입문이지만, 아래 행은 if 문으로 복합문이다.

if b > maximum: maximum = b
if c > maximum: maximum = c

또한, if와 콜론 ( : ) 사이에 있는 식을 조건식이라고 하며, 조건식으로 평가한 결과에 따라 프로그램의 실행 흐름이 변경되는 구조를 선택 구조 ( select structure ) 라고 한다.

알고리즘이 흐르는 방향은 조건식이 결정하며, 조건식에 따라 알고리즘 흐름이 두 갈래로 나뉘는 것을 양 갈래 선택이라 한다.

[ point 1 ] 문자열과 숫자 입력받기

print ('이름을 입력하세요.: ', end=" ")
name = input()
print(f"안녕하세요? {name} 님.")

input() 함수는 키보드로 문자열을 입력받아 반환하며, print 안의 문자열을 input 안에 넣어 아래와 같이 표현할 수 있다.

name = input('이름을 입력하세요.: ')
print(f"안녕하세요? {name} 님.")

만약 변수에 저장해야 할 데이터의 자료형이 문자열이 아니라 10진수 정수형이어야 한다면 input으로 받아온 문자열을 정수형으로 변환해줘야 한다.

이를 형 변환 ( type conversion ) 이라 하며, int() 함수를 사용한다.

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

print(int('17')) # 10진수 문자열을 10진수 정수형으로

print(int('0b110', 2)) # 2진수 문자열을 10진수 정수형으로

print(int('0o75', 8)) # 8진수 문자열을 10진수 정수형으로

print(int('13', 10)) # 10진수 문자열을 10진수 정수형으로

print(int('0x3F', 16)) # 16진수 문자열을 10진수 정수형으로

print(float('3.14')) # 문자형을 실수형으로

참고로 숫자로 변환할 수 없는 문자열을 int(), float() 함수에 전달하면 오류가 발생한다.

[ point 2 ] 복합문의 구조

if문이나 while문 등 복합문의 첫 부분은 if나 while과 같은 키워드로 시작하여 콜론 ( : ) 으로 끝난다. 이 부분을 헤더 ( header ) 라고 하며, 헤더의 마지막인 콜론은 바로 뒤에 스위트 ( suite, 실행문 ) 가 나올 것임을 의미한다.

[ point 3 ] 함수의 반환값과 함수 호출식 평가하기

def max3(a, b, c):
    maximum = a
    if b > maximum: maximum = b
    if c > maximum: maximum = c
    return maximum

함수 내부에서 처리한 값을 반환할 때에는 return 문을 사용하면 된다.

실제로 함수가 반환하는 값을 얻으려면 함수를 호출해야 하며, 이를 함수 호출식을 평가해야 함수가 반환한 값을 얻을 수 있다고 한다.

예를 들어, max3 (3, 2, 1)을 호출하면 세 값을 평가하여 3이라는 반환값을 얻을 수 있다.

[ point 4 ] 복합문을 작성할 때 지켜야 할 규칙

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

if a < b:
    min = a # 공백 4개로 들여쓰기
    max = b # 위와 동일한 들여쓰기여야 함께 실행됨

만약 스위트가 단순문이면 헤더와 같은 행에 둘 수 있으며, 단순문이 2개 이상이면 각각의 단순문을 세미콜론으로 구분하여 헤더와 같은 행에 둘 수 있다.

if a < b: min = a
if a < b: min = a; max = b
if a < b: min = a; max = b;

if a < b: if c < d: x = u #ERROR

[ point 5 ] 세 정수의 대소 관계와 중앙값

# ver 1
def md3(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

# ver 2
def md3(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

ver 2의 코드는 ver 1의 코드보다 짧지만 프로그램의 효율은 더 좋지 않다.

왜냐 하면, 이미 a와 b의 비교를 마친 후, 다음 조건문에서 다시 비교하는 것이 비효율적이기 때문이다.

조건문과 분기

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

if n > 0:
    print("이 수는 양수입니다.") # 1
elif n < 0:
    print("이 수는 음수입니다.") # 2
else:
    print("이 수는 0입니다.") # 3

n이 양수면 1이, 음수면 2가, 0이면 3이 실행된다.

2개가 동시에 실행되거나 하나도 실행되지 않는 경우는 없다.

하지만 아래의 코드는 n이 1, 2, 3이 아니면 아무것도 출력하지 않는다.

똑같이 조건이 3개처럼 보여도 실제로는 4개로 분기되어 있는 코드이다.

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

if n == 1:
    print("이 수는 양수입니다.")
elif n == 2:
    print("이 수는 음수입니다.")
elif n == 3:
    print("이 수는 0입니다.")

else: pass가 생략되어 있으며, pass는 아무것도 수행하지 않고 지나치라는 것을 의미한다.

[ point 6 ] 연산자와 피연산자

+나 -등의 기호를 산술 연산자 ( operator ), 연산 대상을 피연산자 ( operand ) 라고 한다.

단항 연산자 ( unary operator ) : 피연산자 1개
이항 연산자 ( binary operator ) : 피연산자 2개
삼항 연산자 ( ternary operator ) : 피연산자 3개

이 중에서 조건 연산자 ( conditional operator ) 인 if~else 문은 파이선의 유일한 삼항 연산자이다.

a = x if x > y else y
print('c는 0입니다.' if c == 0 else 'c는 0이 아닙니다.')

순서도 기호 살펴보기

순서도 ( flowchart )는 문제를 정의 및 분석하고 해결하는 방법을 표현한 그림이다.

프로그램 순서도에는 실제로 실행한 연산을 나타내는 기호와 제어 흐름을 나타내는 선 기호, 프로그램 순서도를 이해하거나 작성하는 데 편리한 특수 기호로 이루어져 있다.

1 ) 데이터
기억 장치를 지정하지 않은 데이터 자체

2 ) 처리
여러 종류의 처리 기능을 나타내며, 정보의 값 / 형 / 위치를 바꾸도록 정의한 연산이나 연산 집합의 실행, 또는 연속하는 몇 가지 흐므 가운데 하나의 방향을 결정하는 연산이나 연산 집합의 실행을 나타낸다.

3 ) 미리 정의한 처리
다른 곳에서 이미 정의한 하나 이상의 연산 또는 명령으로 이루어진 처리

4 ) 판단
하나의 입구와 하나 이상을 선택하는 출구가 있으며, 판단 기호 안에 정의한 조건을 평가하여 하나의 출구를 선택하는 판단 기능을 나타냄

5 ) 루프 범위
두 부분으로 구성되어 루프의 시작과 종료를 나타냄.
시작 기호 또는 종료 기호 안에 초깃값, 증갓값, 종룍값을 표기함.

6 ) 선
제어의 흐름을 의미하며, 방향을 분명히 나타낼 때는 화살표를 사용함

7 ) 단말
외부 환경으로 나가거나 외부 환경에서 들어오는 것을 나타냄. 주로 프로그램 흐름의 시작과 종료를 나타냄

반복하는 알고리즘

1부터 n까지 정수의 합 구하기

print('1부터 n까지 정수의 합을 구합니다.')
n = int(input('n값을 입력하세요.: '))

sum = 0
i = 1

while i <= n:
    sum += i
    i += 1

print(f'1부터 {n}까지 정수의 합은 {sum}입니다.')

어떤 조건이 성립하는 동안 반복해서 처리하는 것을 반복 구조 ( repetition structure ) 라 하고 일반적으로 루프 ( loop ) 라고 한다.

while 문은 실행하기 전에 반복을 계속할 것인지를 판단하는데 이런 구조를 사전 판단 반복 구조라고 한다.

조건식의 평가 결과가 참인 동안 프로그램의 명령문이 반복된다.

반복 대상이 되는 명령문을 루프 본문이라고 한다.

합을 저장하는 sum 값을 0으로, 반복을 제어하는 i값을 1로 초기화한다.

i값이 n값 이하이며 i값을 1만큼 증가시키면서 루프 본문을 실항한다. 이 과정을 n번 반복 실행한다.

주의할 것은 반복문을 마친 뒤의 i값은 n이 아니라 n+1이다. i값이 n값을 초과해야 반복을 마칠 수 있기 때문이다.

반복을 제어할 때 사용하는 i를 카운터용 변수라고 한다.

print('1부터 n까지 정수의 합을 구합니다.')
n = int(input('n값을 입력하세요.: '))

sum = 0
for i in range(1, n + 1):
    sum += i

print(f'1부터 {n}까지 정수의 합은 {sum}입니다.')

변수가 하나만 있을 때는 while문보다 for문을 사용하는 것이 좋다.

[ point 7 ] range() 함수로 이터러블 객체 생성하기

range() 함수는 이터러블 객체를 생성한다.

range(n) : 0 이상 n 미만인 수를 차례로 나열
range(a, b) : a 이상 b 미만인 수를 차례로 나열
range(a, b, step ) : a 이상 b 미만인 수를 step 간격으로 나열

이터러블 객체는 반복할 수 있는 객체를 말하며, list, str, tuple 등이 대표적은 이터러블 자료형이다.

연속하는 정수의 합을 구하기 위해 값 정렬하기

연속하응 정수의 합을 구할 때 시작하는 값이 1이 아닌 정수를 입력받았다면 range() 함수에 전달할 시작값과 끝값을 오름차순으로 정렬해야 한다.

print('1부터 n까지 정수의 합을 구합니다.')
a = int(input('정수 a를 입력하세요.: '))
b = int(input('정수 b를 입력하세요.: '))

if a > b:
    a, b = b, a

sum = 0
for i in range(a, b + 1):
    sum += i

print(f'{a}부터 {b}까지 정수의 합은 {sum}입니다.')

a가 b보다 크면 둘을 교환하여 a와 b를 오름차순으로 정렬한다.

[ point 8 ] 두 값 교환하기 1

a와 b를 교환할 때 사용한 단일 대입문 a, b = b, a는 다음과 같은 과정으로 수행된다.

1 ) 우변의 b, a에 의해 두 값을 압축한 튜플 ( b, a )가 생성됨
2 ) 대입할 때 튜플 ( b, a )를 다시 풀어 b, a로 만든 다음 각각 a와 b에 대입함

반복 과정에서 조건 판단하기 1

print('1부터 n까지 정수의 합을 구합니다.')
a = int(input('정수 a를 입력하세요.: '))
b = int(input('정수 b를 입력하세요.: '))

if a > b:
    a, b = b, a

sum = 0
for i in range(a, b + 1):
    if i < b:
        print(f'{i} + ', end='')
    else:
        print(f'{i} = ', end='')
    sum += i

print(sum)

1 ) 진행 중인 값 : 수 뒤에 +를 출력
2 ) 최종값 : 수 뒤에 =을 출력

위의 코드는 추천되지 않는 코드이다.

왜냐하면 else문은 마지막에 단 1번 실행되는데 조건을 넣으면 for문 안에 넣는 것은 너무 비효율적이기 때문이다.

따라서, for문 안에 있는 if문을 제외하여 별도로 두는 것이 좋다.

print('1부터 n까지 정수의 합을 구합니다.')
a = int(input('정수 a를 입력하세요.: '))
b = int(input('정수 b를 입력하세요.: '))

if a > b:
    a, b = b, a

sum = 0
for i in range(a, b ):
    print(f'{i} + ', end='')
    sum += i

print(f'{b} = ', end='')
sum += b

print(sum)

1 ) 진행 중인 값 : a부터 b-1까지 값 뒤에 +를 붙여 출력
2 ) 최종값 : b의 값 뒤에 =를 붙여 출력

[ point 9 ] 두 값 교환하기 2

임시용 변수 t를 이용하여 a와 b의 값을 교환할 수도 있다.

1 ) a값을 t에 저장
2 ) b값을 a에 대입
3 ) t에 저장한 처음 a 값을 b에 대입

반복 과정에서 조건 판단하기 2

특정 문자를 줄바꿈 없이 연속으로 출력하는 프로그램이다.

print('+와 -를 번갈아 출력합니다.')
n = int(input("몇 개를 출력할까요? : "))

for i in range(n):
    if i % 2:
        print('-', end='')
    else:
        print('+', end='')

print()

1 ) i가 홀수면 '-'를 출력
2 ) i가 짝수면 '-'fmf cnffur

이 프로그램은 두 가지 문제점이 있다.

첫 번째는 for문을 반복할 때마다 if문을 수행해 비효율적이라는 점이고, 두 번째는 상황에 따라 유연하게 수정하기 어렵다는 점이다.

아래 코드는 두 가지 문제를 해결한 코드이다.

print('+와 -를 번갈아 출력합니다.')
n = int(input("몇 개를 출력할까요? : "))

for _ in range(n // 2):
    print('+-', end='')

if n % 2:
    print('+', end='')

print()

n이 짝수일 경우 '+-'를 n // 2번 출력하고, n이 홀수 인 경우 마지막에 '+'를 추가 출력해준다.

반복 과정에서 조건 판단하기 3

*를 n개 출력하되 w개마다 줄바꿈을 하는 프로그램이다.

print('*을 출력합니다.')
n = int(input('몇 개를 출력할까요? : '))
w = int(input('몇 개마다 줄바꿈할까요? : '))

for i in range(n):
    print('*', end='')
    if i % w == w - 1:
        print()

if n % w:
    print()

i를 w로 나눈 나머지가 w-1일 때 줄바꿈한다.

하지만 n이 w의 재수가 아니면 줄바꿈을 for문 밖에서 따로 수행해야 한다.

위의 코드는 for문을 반복할 때마다 if문을 실행하므로 효율적이지 않다.

이는 다음과 같이 개선할 수 있다.

print('*을 출력합니다.')
n = int(input('몇 개를 출력할까요? : '))
w = int(input('몇 개마다 줄바꿈할까요? : '))

for _ in range(n // w):
    print('*' * w)

rest = n % w
if rest:
    print('*' * rest)

*를 n // w번 반복하며 출력하고 n이 w의 배수가 아닌 경우 마지막 행을 출력한다.

n을 w로 나눈 나머지를 rest에 저장하고 *를 rest개 출력한 다음 줄바꿈한다.

양수만 입력받기

앞선 1부터 n까지 정수의 합을 구하는 예제에서 -5를 입력하면 값이 0으로 나온다.

이 프로그램에서는 입력하는 n값을 양수로 한정해야 한다.

print('1부터 n까지 정수의 합을 구합니다.')

while True:
    n = int(input('n값을 입력하세요.: '))
    if n > 0:
        break

sum = 0
i = 1

for i in range(1, n+ 1):
    sum += i
    i += 1

print(f'1부터 {n}까지 정수의 합은 {sum}입니다.')

while True는 프로그래머가 의도적으로 while 문이 무한 반복되도록 만든 것이며 무한 루프 ( infinite loop ) 라고 한다.

위의 코드에서는 break문을 실행하면 반복문을 종료할 수 있다는 점을 이용하여 무한 루프에서 탈출했다.

이 프로그램은 사용자가 양수를 입력할 때까지 다시 입력받는 구조이다.

대부분 루프 본문을 한 번 실행한 다음 계속 반복할지 판단하는 사후 판단 반복문을 지원한다.

do~while문, repeat~until문 등이 대표적인 사후 판단 반복문이다.

하지만 파이썬은 사후 판단 반복문을 제공하지 않으므로 break문을 사용해야만 양수를 입력받는 프로그램을 만들 수 있다.

[ point 10 ] for 문이 종료된 이후 카운터용 변수 i값 살펴보기

while문이 종료될 떄 카운터 용 변수 i는 n이 아니라 n+1이다.

하지만 for i in range(1, n+1)의 for문이 종료될 때 카운터용 변수 i는 n이다.

이는 for문은 이터러블 객체의 값을 하나씩 꺼내 i에 넣고 반복하기 때문이다.

직사각형 넓이로 변의 길이 구하기

area = int(input('직사각형의 넓이를 입력하세요.: '))

for i in range(1, area + 1):
    if i * i > area: break
    if area % i: continue
    print(f'{i} * {area // i}')

위의 코드는 약수를 나열하는 프로그램이다.

i * i가 area를 초과하면 for 문을 강제로 종료한다.

continue문은 area가 i로 나누어 떨어지지 않으면 for문의 다음 반복으로 진행된다.

반복문에서 continu 문이 실행되면 루프 본문의 나머지 부분을 건너뛰고 조건식으로 돌아간다.

참고로 while문이나 for 문 등 반복문의 끝부분에는 else 문을 두어 조건식에 의해 반복문이 종료되는 경우 실행되도록 할 수 있다.

import random

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

for _ in range(n):
    r = random.randint(10, 99)
    print(r, end = ' ')
    if r == 13:
        print('\n프로그램을 중단합니다.')
        break
else:
    print('\n난수 생성을 종료합니다.')

위의 코드에서 13이 생성될 경우 break문으로 반복문을 강제 종료한다.

만약 13이 생성되지 않으면 반복이 끝난 다음 else문이 실행되어 '난수 생성을 종료합니다.'를 출력한다.

반복문 건너뛰기와 여러 범위 스캔하기

for문을 반복하는 과정에서 특정 조건일 때 반복문을 건너뛰도록 만들 수 있다.

for i in range(1, 13):
    if i == 8:
        continue
    print(i, end=' ')

print()

# 1 2 3 4 5 6 7 9 10 11 12 

실행결과를 보면 8만 빼고 출력한 것을 알 수 있다.

하지만 이 코드는 앞선 for문 안의 조건문 코드처럼 비효율적이다.

for i in list(range(1, 7)) + list(range(9, 13)):
    print(i, end=' ')

print()

위의 코드에서는 단순히 리스트를 사용하여 8을 건너 뛰었다.

다만 for 문은 생성한 리스트의 원소를 하나씩 꺼내 반복하므로 반복을 위한 연산 비용은 여전이 발생한다.

[ point 11 ] 비교 연산자를 연속으로 사용하는 방법과 드모르간의 법칙

print('2자리 양수를 입력하세요.')

while True:
    no = int(input('값을 입력하세요.: '))
    if no >= 10 and no <= 99:
        break

print(f'입력받은 양수는 {no}입니다.')

위의 코드는 no >= 10 and no <= 99처럼 비교 연산자 >=와 <=를 and 연산자로 연결했다.

하지만 이를 다르게 표현할 수도 있다.

1 ) 비교 연산자를 연속으로 사용한 방법

if 10 <= no <= 99:

2) 드모르간의 법칙을 사용한 방법

if not(no < 10 or no > 99):

드모르간의 법칙 ( De Morgan's Laws ) 은 각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다는 것이다.

다중 루프 알아보기

반복문 안에서 다시 반복문을 사용하는 것을 다중 루프라고 한다.

다음은 이중 루프로 구구단 곱셈표를 출력하는 프로그램이다.

print('-' * 27)
for i in range(1, 10):
    for j in range(1, 10):
        print(f'{i * j: 3}', end='')
    print()
print('-' * 27)

바깥 쪽의 for문은 세로 방향의 반복문이고, 안쪽 for문은 각 행에서 가로 방향의 반복문이다.

i값을 1~9 까지 증가시키는 행 루프는 9번 반복하고, j값을 1~9까지 증가시키는 열 루프는 9번 반복한다.

이중 루프를 응용하면 특수 문자로 표현한 삼각형이나 사격형을 출력할 수 있다.

# 왼쪽 아래가 직각인 이등변 삼각형
print('왼쪽 아래가 직각인 이등변 삼각형을 출력합니다.')
n = int(input('짧은 변의 길이를 입력하세요.: '))

for i in range(n):
    for j in range(i + 1):
        print('*', end='')
    print()
    
# 오른쪽 아래가 직각인 이등변 삼각형
print('오른쪽 아래가 직각인 이등변 삼각형을 출력합니다.')
n = int(input('짧은 변의 길이를 입력하세요.: '))

for i in range(n):
    for _ in range(n - i - 1):
        print(' ', end='')
    for _ in range(i + 1):
        print('*', end='')
    print()

[ point 12 ] 난수를 생성하는 random.randint() 함수 알아보기

random 모듈에 포함된 randint(a, b) 함수는 a 이상 b 이하인 난수를 생성하여 반환한다.

[ point 13 ] 파이썬의 변수 알아보기

파이썬에서는 데이터, 함수, 클래스, 모듈, 패키지 등을 모두 객체 ( object )로 취급한다.

객체는 자료형 ( data type )을 가지며 메모리 ( 저장 공간 ) 를 차지한다.

이런 특징 때문에 파이썬의 변수를 값을 갖지 않는다는 특징이 있다.

변수는 객체를 참조하는 객체에 연결된 이름에 불과하다.
모든 객체는 메모리를 차지하고, 자료형뿐만 아니라 식별 번호 ( identity ) 를 가진다.

파이썬은 값을 복사하여 대입하는 것이 아니라 변수 이름을 결합 ( bind ) 한다.

따라서 n = 17일 때, n과 17의 식별 번호가 동일하다.

상자라는 표현을 사용해보자면 int 형 객체 자체가 상자이고 변수는 단순한 이름에 불과하다.

만약 n을 다른 값으로 갱신하면 새로운 값을 갖는 객체가 생성되고, 그 값을 n이 참조한다.