알고리즘 입문!
“Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬편” 1장 공부내용을 정리한 글입니다.
단어/개념 정리
알고리즘: 어떠한 문제를 해결하기 위해 정해 놓은 일련의 절차
특히, ‘올바른 알고리즘’이란 어떠한 경우에도 실행 결과가 똑같이 나오는 것. 어떤 경우에는 맞고 어떤 경우에는 틀리면 올바른 알고리즘이라고 할 수 없다.
순차구조: 한 문장씩 순서대로 처리되는 구조
대입문: a=1 처럼 변수에 값을 대입
복합문: if문처럼 복합적인 문장
조건식: 예를 들어 if문에서, if _____ : 처럼 if 와 콜론(:) 사이에 있는 식
선택구조: 조건식으로 평가한 결과에 따라 실행 흐름이 변경되는 구조
형 변환(type conversion): int()와 같은 함수를 사용해서 데이터의 형태를 바꾸는 과정
헤더: if문이나 while문 등 복합문의 첫 부분 (if _____ :)
스위트: 헤더 다음에 따라오는 내용. 헤더의 콜론은 바로 뒤에 스위트가 이어짐을 의미.
f-string:
파이썬 3.6 이상 부터 지원되는 기능으로, 스트링 앞에 f를 붙이면(대문자 F도 가능하지만 소문자 사용이 기본 가이드) 스트링 안에 중괄호를 붙여서 변수, 함수 등을 입력할 수 있다.
name = '루카스'
print(f'안녕하세요, 저는 {name}입니다.')
PEP (Python Enhancement Proposals):
파이썬 스타일 가이드. 파이썬 코드의 공통적인 이해와 가독성을 위해 제시하는 가이드. 복합문 다음에 들여쓰기는 스페이스 4개를 기준으로 하거나 클래스명은 카멜 케이스(CamelCase) 형식으로 쓰고, 함수명은 스네이크(snake_case) 형식으로 써야한다는 등의 내용이 들어가있음.
연산자와 피연산자:
- 산술연산자(operator): + 나 - 등의 기호
- 조건연산자(conditional operator): if, else, and, or 등과 같은 조건
- 피연산자(operand): 연산의 대상
- 단항연산자(unary operator): 피연산자가 1개인 연산자 / -a, +b
- 이항연산자(binary operator): 피연산자가 2개인 연산자 / a<b
- 삼항 연산자(ternary operator): 피연산자가 3개인 연산자 / a if b else
드모르간의 법칙: ‘각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 주어하면 원래의 조건과 같다’
- x and y 와 not(not x or not y)의 논릿값은 같다
- x or y 와 not(not x and not y)의 논릿값은 같다
알고리즘 순서도
.jpg)
위와 같은 구조도를 ‘알고리즘 순서도’라고 한다.
- 직사각형 안에는 대입문과 같은 단순 작업이 들어감
- 마름모 안에는 조건식이 들어가고, 조건식의 평가 결과에 따라 해당하는 방향을 따라감. 이렇게 조건식에 따라 알고리즘의 흐름이 두 갈래로 나뉘는 것을 양 갈래 선택이라 함
- 순서도 기호 예
- 평행사변형: 데이터, 기억 장치를 지정하지 않은 데이터 자체를 표시
- 직사각형: 처리, 정보의 값, 형, 위치를 바꾸도록 정의한 연산이나 연산 집행의 실행 또는 연속하는 몇 가지 흐름 가운데 하나의 방향을 결정하는 연산이나 연산 집합의 실행을 표시
- 마름모: 판단, 하나의 입구와 하나 이상을 선택하는 출구가 존재. 판단 기호 안에 정의한 조건을 평가하여 하나의 출구를 선택하는 판단 기능(스위치형 기능)을 표시
- 열고 닫히는 육각형: 루프 범위, 안에는 루프의 초기값, 증가값, 종료값을 표기하고 시작 기호와 종료 기호 사이에 처리 내용이 들어감.
- 선: 제어의 흐름을 의미. 화살표를 이용하여 흐름의 방향을 분명히 나타낼 수 있음
- 둥근사각형: 단말, 외부 환경으로 나가거나 외부 환경에서 들어오는 것을 나타냄. 주로 프로그램 흐름의 시작과 종료 표시.
두 값 교환하기
변수 안에 저장된 값을 교환할 때는 다음과 같은 방법을 사용할 수 있다.
-
단일대입문
a = 1 b = 2 a,b = b,a하나의 대입문만 사용하여 a와 b의 값을 교환한다. 이 과정은 a, b를 튜플로 묶어서 교환이 이루어진다.
-
임시용 변수 사용
a = 1 b = 2 t = a # a값을 t에 저장 a = b # b값을 a에 대입 b = t # t에 저장한 처음 a값을 b에 대입
효율적인 코드 작성
효율적인 코드를 작성하려면 조건문에 대한 판단을 최소화 하는 것이 좋다
예1) 세 정수를 입력받아 중앙값 구하기
- 방법 1
def med3(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
- 방법 2
def med3(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
else:
return c
위 둘을 비교했을 때 코드는 방법2가 더 짧지만 효율은 방법1이 더 좋다. 왜냐하면 방법2에서는 b > a 와 a < b 에 대한 판단이 2행과 4행에서 반복된다. if 문에서 조건식이 성립하지 않는다면 이어지는 elif 문에서 이 판단을 반복해서 수행할 필요가 없기 때문에 효율적이지 못하다.
예2) a부터 b까지 정수의 합을 구하는 과정 및 최종값을 출력하기
- 방법 1
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)
- 방법 2
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)
방법 1의 경우 for문 안에서 ‘if i < b’는 마지막에 단 한번 실행되는 else문을 위해 존재한다. 이런경우 방법 2 처럼 실행조건을 for문 밖으로 분리시켜주면 if 조건 판단을 해야하는 경우가 n번에서 0으로 바뀌고 심지어 for 문의 반복 횟수 또한 1번 감소하기 때문에 훨씬 효율적이다.
예3) 줄바꿈 없이 +,- 연속으로 출력하기
- 방법 1
n = int(input('출력할 개수: '))
for i in range(1, n + 1):
if i % 2: # 홀수
print('+', end='')
else: # 짝수
print('-', end='')
print()
위 방법은 정상적으로 동작은 하지만 for 문이 n번 반복되는 만큼 if 문과 나눗셈도 n번 반복하게 된다.
- 방법 2
n = int(input('출력할 개수: '))
for _ in range(n // 2):
print('+-', end='') # n // 2개의 +-를 출력
if n % 2:
print('+', end='') # n이 홀수일 때만 +를 출력
print()
방법 2는 for 문은 n/2 번, if 문은 1번, 나눗셈은 2번만 실행된다
댓글남기기