[Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편] 01. 알고리즘 기초

서적의 실습 자료(참고 코드)는 다음 링크에서 다운 가능 : http://www.easyspub.co.kr/30_Menu/DataList/PUB

파이썬 기초는 다음 링크에서 학습 가능 : https://wikidocs.net/book/2

 

01. 알고리즘 기초

01-1. 알고리즘이란?

알고리즘

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

올바른 알고리즘 : 어떠한 경우에도 실행 결과가 똑같이 나오는 것

# [Do it! 실습 1-1] 세 정수를 입력받아 최댓값 구하기

print('세 정수의 최댓값을 구합니다.')
a = int(input('정수 a의 값을 입력하세요.: ')) # 형 변환
b = int(input('정수 b의 값을 입력하세요.: '))
c = int(input('정수 c의 값을 입력하세요.: '))

# 순차 구조 및 선택 구조
maximum = a                 # maximum에 a의 값을 대입
if b > maximum: maximum = b # b의 값이 maximum보다 크면, maximum에 b의 값을 대입
if c > maximum: maximum = c # c의 값이 maximum보다 크면, maximum에 c의 값을 대입

print(f'최댓값은 {maximum}입니다.')

 

순차 구조 sequential structure

한 문장씩 순서대로 처리되는 구조

 

선택 구조 select structure

조건식으로 평가한 결과에 따라 프로그램의 실행 흐름이 변경됨

 

형 변환 type conversion

문자열형을 정수형으로 변환하는 과정

• int(문자열) => 정수형 반환
• 2, 8, 10, 16진수를 나타내는 문자열의 경우 int(문자열, 진수) => 정수형 반환
• float(문자열) => 실수형 반환

>>> int('17')
17
>>> int('0b110', 2)
6
>>> int('0o75', 8)
61
>>> int('13', 10)
13
>>> int('0x3F', 16)
63
>>> float('3.14')
3.14

 

양 갈래 선택

조건식에 따라 알고리즘 흐름이 두 갈래로 나뉘는 것

>>> if a > b:                     # 만약 a가 b보다 크면
...     print('a')                # 'a'를 출력한다.
... else:                         # 그렇지 않으면
...     print('b')                # 'b'를 출력한다.

 

복합문의 구조

복합문

if 문이나 while 문 등을 뜻함

 

헤더 header

if나 while과 같은 키워드로 시작하여 콜론(:)으로 끝나는 복합문의  첫 부분

헤더의 마지막 콜론은 '바로 뒤에 스위트가 이어집니다'는 의미

 

스위트 suite

헤더와 한 세트로 따라다니는 실행문

>>> if a > b:                     # if는 반드시 1개 필요
...     print('a')                # 스위트 부분
... elif:                         # 없거나, n개 존재
...     print('b')
... else:                         # 없거나, 1개 존재
...     print('b')

 

결정 트리 decision tree

의사 결정 규칙과 그 결과들을 트리 구조로 표현

 

 

중앙값 구하기

중앙값 median

주어진 값을 크기 순서대로 정렬했을 때 가장 중앙에 위치하는 값

# [Do it! 실습 1C-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): # 이 부분에서 이미 b, 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의 값을 입력하세요.: 34
정수 b의 값을 입력하세요.: 22
정수 c의 값을 입력하세요.: 55
중앙값은 34입니다.

 

조건문과 분기

분기 branching

프로그램의 실행 흐름을 다른 곳으로 변경하는 명령

# [Do it! 실습 1-5] 4개로 분기하는 조건문

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

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

#위의 코드는 아래 코드와 같다
# [Do it! 실습 1-6] 실습 1-5의 원래 모습

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

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

 

연산자와 피연산자

산술 연산자 operator

+나 - 등의 기호

 

피연산자 operand

연산 대상

 

단항 연산자 unary operator

피연산자 1개 ex. -a

 

이항 연산자 binary operator

피연산자 2개 ex. a < b

 

삼항 연산자 ternary operator

피연산자 3개 ex. a if b else c

 

조건 연산자 conditional operator

파이썬의 유일한 삼항 연산자

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

 

순서도 기호 살펴보기

순서도 flowchart

문제를 정의 · 분석하고 해결하는 방법을 그림으로 표현

사용하는 기호 목록

- 실제로 실행할 연산을 나타내는 기호

- 제어 흐름을 나타내는 선 기호

- 프로그램 순서도를 이해하거나 작성하는 데 편리한 특수 기호

 

01-2. 반복하는 알고리즘

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

# [Do it! 실습 1-7] 1부터 n까지 정수의 합 구하기 1(while 문)

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

sum = 0
i = 1

while i <= n:  # i가 n보다 작거나 같은 동안 반복
    sum += i   # sum에 i를 더함
    i += 1     # i에 1을 더함

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

# 실행 결과
1부터 n까지 정수의 합을 구합니다.
n값을 입력하세요.: 6
1부터 6까지 정수의 합은 21입니다.

 

반복 구조 repetition structure

어떤 조건이 성립하는 동안 반복해서 처리(프로그램 명령문 또는 명령어의 집합)하는 것

= 루프 loop

 

사전 판단 반복 구조

실행하기 전에 반복을 계속할 것인지 판단하는 구조

ex. while 문

 

루프 본문

while 조건식 : 명령문

이때 반복 대상이 되는 명령문

 

for 문 반복 알아보기

변수가 하나만 있을 땐 while보다 for 문이 적합

# [Do it! 실습 1-8] 1부터 n까지의 합 구하기 2(for 문)

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

sum = 0
for i in range(1, n + 1):
    sum += i  # sum에 i를 더함

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

# 실행 결과
1부터 n까지의 합을 구합니다.
n값을 입력하세요.: 6
1부터 6까지 정수의 합은 21입니다.

 

이터러블 객체

반복할 수 있는 객체

range(a, b, step) : a 이상 b 미만인 수를 step 간격으로 나열하는 수열

대표적인 이터러블 자료형 : list, str, tuple 

 

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

# [Do it! 실습 1-9] a부터 b까지 정수의 합 구하기(for 문)

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

if a > b:
    a, b = b, a  # a와 b를 오름차순으로 정렬 => 단일 대입문 사용

sum = 0
for i in range(a, b + 1):
    sum += i  # sum에 i를 더함

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

 

a = b, b = a 수행 과정

1. 우변의 b, a에 의해 두 값을 압축한 튜플 (b, a)가 생성

2. 대입할 때 튜플 (b, a)를 다시 풀어 b, a로 만든 다음 각각 a와 b에 대입

 

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

a부터 b까지 정수의 합을 구하는 과정과 최종값을 출력하는 로직

# [Do it! 실습 1-10] a부터 b까지 정수의 합 구하기 1

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

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

sum = 0
for i in range(a, b + 1):  # b - a번 반복
    if i < b:              # i가 b보다 작으면 합을 구하는 과정을 출력
        print(f'{i} + ', end='')
    else:                  # i가 b보다 크거나 같으면 최종값 출력을 위해 i =를 출력
        print(f'{i} = ', end='')
    sum += i               # sum에 i를 더함

print(sum)

해당 로직은 a가 1, b가 10,000일 때 13행이 9,999번 실행되고 마지막 10,000번째에는 거짓이므로 15번 행은 단 1번만 실행됨 -> 15행을 위해 13행이 9,999번 실행되는 셈

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

# [Do it! 실습 1-11] a부터 b까지 정수의 합 구하기 2

print('a부터 b까지 정수의 합을 구합니다.')
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  # sum에 i를 더함

print(f'{b} = ', end ='')
sum += b      # sum에 b를 더함

print(sum)

i와 b를 비교하지 않기 때문에 효율이 좋음

출력 과정

1. 진행 중인 값 : for 문에서 a부터 b-1까지 값 두에 +를 붙여 출력함

2. 최종값 : b의 값 뒤에 =를 붙여 출력함

 

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

줄바꿈 없이 +, -를 연속으로 출력하는 로

# [Do it! 실습 1-12] +와 -를 번갈아 출력하기 1

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

for i in range(n):          # 반복 n번
    if i % 2:                 
        print('-', end='')  # 홀수인 경우 - 출력
    else:
        print('+', end='')  # 짝수인 경우 + 출력

print()

해당 로직의 문제점

1. for 문을 반복할 때마다 if 문 수행

2. 확장성이 떨어짐(유연한 수정이 어려움)

따라서 해당 문제점을 보완하여 아래 로직처럼 수정 가능

# [Do it! 실습 1-13] +와 -를 번갈아 출력하기 2

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

for _ in range(n // 2):
    print('+-', end='')  # n // 2개의 +-를 출력

if n % 2:
    print('+', end='')  # n이 홀수일 때만 +를 출력

print()

언더스코어(_)를 사용하여 for 문에서 무시하고 싶은 값(사용하지 않는 인덱스)을 표현 가능

 

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

*를 n개 출력하되 w개마다 줄바꿈 하는 로직

# [Do it! 실습 1-14] *를 n개 출력하되 w개마다 줄바꿈하기 1

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

for i in range(n):      # n번 반복
    print('*', end='')
    if i % w == w - 1:  # n번 판단
        print()         # 줄바꿈

if n % w:
    print()             # 줄바꿈

for 문과 if문을 분리하여 다음처럼 효율적으로 개선 가능

# *를 n개 출력하되 w개마다 줄바꿈하기 2

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

for _ in range(n // w):  # 반복 n // w번 반복
    print('*' * w)

rest = n % w
if rest:
    print('*' * rest)  # if 문 1번 판단

 

양수만 입력받기

위의 1-8 로직의 경우 입력하는 값이 양수로 한정되어야 함

따라서 양수가 아닐 경우 while문을 이용하여 재입력을 받도록 수정

# [Do it! 실습 1-16] 1부터 n까지 정수의 합 구하기(n값은 양수만 입력받음)

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

while True:
    n = int(input('n값을 입력하세요.: '))
    if n > 0:
        break  # n이 0보다 커질 때까지 반복

sum = 0
i = 1

for i in range(1, n + 1):
    sum += i  # sum에 i를 더함
    i += 1    # i에 1을 더함

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

# 실행 결과
1부터 n까지 정수의 합을 구합니다.
n값을 입력하세요.: -4
n값을 입력하세요.: 0
n값을 입력하세요.: 10
1부터 10까지 정수의 합은 55입니다.

 

무한 루프와 break 문 알아보기

무한 루프

반복문이 무한 반복되도록 만드는 것

ex. while True:

 

break 문

반복문 안에서 반복문을 종료하는 역할

 

사후 판단 반복문

루프 본문을 한 번 실행한 다음 계속 반복할지 판단함

break 문을 사용할 필요 없음

단 파이썬에서는 음

ex. do ~ while 문, repeat ~ until 문 등

 

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

변의 길이와 넓이가 모두 정수인 직사각형에서 변의 길이를 구하는 로직

이때

= 약수를 나열하는 로직

# [Do it! 실습 1-17] 가로 세로가 정수이고 넓이가 area인 직사각형에서 변의 길이를 나열하기

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

for i in range(1, area + 1):  # 1부터 사각형의 넓이 계산
    if i * i > area: break
    if area % i: continue
    print(f'{i} × {area // i}')
    
# 실행 결과
직사각형의 넓이를 입력하세요.: 32
1 × 32
2 × 16
4 × 8

 

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

# [Do it! 실습 1-19] 1~12까지 8을 건너뛰고 출력하기 1

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

 

드모르간의 법칙 De Morgan's laws

각 논리 연산자들을 어떻게 결합하고 변환할 수 있는지에 대한 규칙

다음과 같은 두 가지 기본 형태가 존재

NOT (A AND B) = (NOT A) OR (NOT B) # A와 B 모두 참인 상황을 부정하는 것 = A를 부정하거나 B를 부정하는 것
NOT (A OR B) = (NOT A) AND (NOT B) # A나 B 중 하나라도 참인 상황을 부정하는 것 = A와 B를 각각 부정하는 것

 

코드 예시

# 2자리 양수(10 ~ 99) 입력받기 2

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

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

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

 

해당 코드에서

    if 10 <= no <= 99:

이 부분은 드모르간의 법칙을 사용하여 다음처럼 표현할 수 있다:

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

 

구조적 프로그래밍 structured programming

입력과 출력으로 이루어진 구성 요소를 계층으로 배치하여 프로그램을 구성하는 방법

세 종류의 제어 흐름 사용 : 순차, 선택, 반복

 

다중 루프 알아보기

# [Do it! 실습 1-21] 구구단 곱셈표 출력하기

print('-' * 27)
for i in range(1, 10):      # 행 루프
    for j in range(1, 10):  # 열 루프
        print(f'{i * j : 3}', end='')
    print()                 # 행 변경
print('-' * 27)

# 실행 결과
---------------------------
  1  2  3  4  5  6  7  8  9
  2  4  6  8 10 12 14 16 18
  3  6  9 12 15 18 21 24 27
  4  8 12 16 20 24 28 32 36
  5 10 15 20 25 30 35 40 45
  6 12 18 24 30 36 42 48 54
  7 14 21 28 35 42 49 56 63
  8 16 24 32 40 48 56 64 72
  9 18 27 36 45 54 63 72 81
---------------------------

 

파이썬의 변수 알아보기

파이썬에서 데이터, 함수, 클래스, 모듈, 패키지 등은 모두 객체 object로 취급

 

객체 object

자료형 data type을 가지며 메모리(저장 공간)를 차지함

파이썬의 변수는 값을 갖지 않음

 

변수

변수는 객체를 참조하는 객체에 연결된 이름에 불과함

모든 객체는 메모리를 차지하고, 자료형뿐만 아니라 식별 번호 identity를 가짐

 # [Do it! 실습 1C-4] 함수의 내부·외부에서 정의한 변수와 객체의 식별 번호를 출력

n = 1      # 전역 변수(함수 내부·외부에서 사용)
def put_id():
    x = 1  # 지역 변수(함수 내부에서만 사용)
    print(f'id(x) = {id(x)}')
    
print(f'id(1) = {id(1)}')
print(f'id(n) = {id(n)}')
put_id()

# 실행 결과
id(1) = 140721159223736
id(n) = 140721159223736
id(x) = 140721159223736