파이썬 코테 준비

코딩테스트 스터디를 시작했다. 언어는 파이썬으로 결정되었고, 백준과 프로그래머스 사이트 문제를 푸는것으로 좁혀졌다. 빨리 문제 풀기에 들어가고 싶어서 찾아보던 도중 코딩테스를 위한 파이썬 문법이 유튜브에 있어서 보고 팁을 정리했다.
동빈나 파이썬 코딩테스트

온라인 개발 환경 리플릿
리플릿
동빈나님의 팀 노트
팀 노트

복잡도

시간 복잡도

특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

공간 복잡도

특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

빅오 표기법

가장 빠르게 증가하는 항만을 고려한다.
연산 횟수가 3N^3 + 5N^2 + 1,000,000 인 알고리즘이 있다면 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N^3)으로 표현된다.

O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) > O(N^3) > O(2^n)

코테에서 시간제한은 통상 1~5초 가량이라고 생각하자. 문제에 시간제한이 명시되어 있지 않더라도 5초 안에 푸는게 합리적이다. PyPy를 지원하는 경우에는 때로는 C언어보다도 빠르지만 이를 항상 보장하지 않는다. 일반적으로 파이썬으로 먼저 제출 한 후에, 알고리즘에는 문제가 없는것 같다면 PyPy로 제출 해 보자.

시간제한 확인을 필수로 하자.

시간제한이 1초인 문제를 만났을 때 일반적인 기준
N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계해야 한다.
N의 범위가 2000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계해야 한다.
N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계해야 한다.
N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계해야 한다.

수행 시간 측정 소스코드 예제

import time
start_time = time.time() # 측정 시작
# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력

파이썬의 자료형

정수형, 실수형, 복소수형, 문자열, 리스트(c++의 vector가 제공하는 기능들을 내장), 튜플, 사전 등이 있다.

실수형

소수부가 0이거나, 정수부가 0인 소수는 0을 생략하고 작성할 수 있다. 실수 정보는 정확도에 한계를 가진다. 2진수 체계인 컴퓨터 시스템에서는 0.3 과 0.6을 더한 값은 0.9로 딱 떨어지지 않는다. 최대한 가깝게 표현하는 것 뿐이다.

a = 5. # 5.0
a = -.7 # -0.7

지수 표현 방식

e나 E를 이용한 지수 표현 방식을 이용할 수 있다. e나 E 다음에 오는 수는 10의 지수부를 의미한다.
1e9 라고 입력한다면 이는 10의 9제곱인 1,000,000,000 이 된다.

수 자료형의 연산

나누기 연산자 / 는 나눠진 결과를 실수형으로 반환한다.
몫을 얻기 위해서 몫 연산자인 // 를 사용한다.
거듭제곱 연산자로 ** 가능하다.

리스트 자료형

여러개의 데이터를 연속적으로 담아 처리하기 위해 사용한다. 배열 혹인 테이블이라고도 불린다.
C++의 STL vector와 기능적으로 유사하다.

arr = list() # 혹은
arr = [1, 2, 3, 4, 5]
el = arr[1] # 2. 인덱싱이 가능하다.
el2 = arr[-2] # 음의 정수도 가능하다. -1이 마지막원소고, 거꾸로 탐색한다.

리스트에서 슬라이싱을 이용해서 시작인덱스 부터 끝 인덱스 -1 까지 원소를 가져올 수 있다.

arr = [1, 2, 3, 4, 5]
arr[1:4] # [2, 3, 4] # 인덱스 1 부터 3까지 가져온다.

리스트 컴프리헨션

리스트를 초기화하는 방법 중 하나이다.

arr = [i for i in range(1, 4)]
print(arr) # [1, 2, 3]

arr = [i for i in range(20) if i  % 3 == 0]
print(arr) # 3의 배수 리스트 출력

# 2차원 리스트
n = 4
m = 3
arr = [n * [0] for _ in range(m)]

print(arr) # [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

리스트 메서드

append, sort, sort(reverse=True), reverse, insert, count, remove

a = [4, 3, 2, 1]
a.insert(2, 10) # 인덱스 2에 3을 추가한다. [4, 3, 10, 2, 1]

리스트에서 remove는 최초 하나의 값만 지워준다. 모두 제거하기 위한 방법으로 집합 자료형을 사용할 수 있다.

a = [1, 2, 3, 4, 5, 5, 5]
remove_set = { 3, 5 }
result = [i for i in a if i not in remove_set] # [1, 2, 4]

문자열 연산

• 문자열에 덧셈을 이용하면 문자열이 더해져서 연결된다.
• 문자열 변수를 양의 정수와 곱한다면, 문자열이 그 값만큼 여러번 더해진다.
• 인덱싱과 슬라이싱을 이용할 수 있다. 다만 인덱스의 값을 변경할 수 없다.

str = "string"
str*3 # "stringstringstring"

튜플 자료형

리스트와 유사하지만 한 번 선언된 값은 변경할 수 없다. 또한 소괄호를 이용한다.
리스트에 비해 상대적으로 공간 효율적이다.

서로 다른 성질의 데이터를 묶어서 관리해야 할 때
최단 경로 알고리즘에서 (비용, 노드번호) 형태로 튜플을 자주 사용한다.
데이터의 나열을 해싱의 키 값으로 사용해야 할 때
리스트 보다 메모리를 효율적으로 사용해야 할 때

사전 자료형

• 리스트나 튜플이 값을 순차적으로 저장하는 것과는 대비되는 자료형이다.
• Key와 value의 쌍을 데이터로 가진다.
• 변경 불가능한 자료형을 키로 사용할 수 있다.
• 내부적으로 해시 테이블을 이용하므로 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다.

str = '사과'

data = {
  str: 'Apple',
  '바나나': 'Banana'
}

print(data) # {'사과': 'Apple', '바나나': 'Banana'}

# 또는
data = dict()
data['사과'] = 'Apple'
data['바나나'] = 'Banana'

키 데이터만 뽑아서 리스트로 만들때는 keys() 함수를, 값 데이터만 뽑아서 리스트로 만들때는 values() 함수를 이용하자.

집합 자료형

• 중복을 허용하지 않는다.
• 순서가 없다.
• 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다.

# 초기화
data = set([1, 2, 3, 4, 4, 4, 5]) # {1, 2, 3, 4, 5}. 4중복 제거
data = {1, 1, 2, 2, 3, 4, 4, 5, 5 } # {1, 2, 3, 4, 5}

집합 자료형의 연산

합, 교, 차집합

a = {1, 2, 3, 4 }
b = {1, 4, 5, 6 }
# 합
a | b

#교
a & b

#차
a - b

집합 자료형 메서드

data = set([1, 2, 3, 4, 5])
data.add(6)

# 새로운 원소 여러개 추가
data.update([7, 8])

data.remove(8)

사전 자료형과 집합자료형

이 둘은 순서가 없기 때문에 인덱싱으로 값을 얻을 수 없다.
사전의 키 혹은 집합의 원소를 이용해 O(1)의 시간 복잡도로 조회한다.

입출력

• input() 함수는 한 줄의 문자열을 입력받는다.
• map() 함수는 리스트의 모든 원소에 각각 특정한 함수를 적용한다.

# 입력수가 적다면 (여기선 3개라면 3개로 언패킹한다.)
a, b, c = map(int, input().split())
# 많다면 list로 치환
data = list(map(int, input().split()))

입력량만으로도 시간초과가 날 수 있다.

최대한 빠르게 입력을 받아야 할 경우 sys 라이브러리에 정의되어 있는 sys.stdin.readline() 메서드를 사용한다.
입력 후 줄바꿈 처리 되므로 rstript() 메서드 함께 사용 해 주자.

import sys
data = sys.stdin.readline().rstrip()
print(data)

기본 출력

기본출력은 print() 함수다. print()는 기본적으로 출력 이후에 줄 바꿈을 수행한다. 줄바꿈을 원치 않는 경우 'end' 속성 사용한다.

print(8, end=" ")

fstring

answer = 7;
print(f"정답은 {answer}입니다.") # 수 데이터를 문자열로 치환하지 않고 사용 가능하다.

논리 연산자

• X and Y
• X or Y
• not X

기타 연산자

리스트, 튜플, 문자열, 딕셔너리 모두 사용 가능하다.

• x in 리스트
• x not in 문자열

pass

분기점에서 아무것도 처리하고 싶지 않을 때 사용할 수 있다.

if score >= 80:
	pass
else:
	print('성적이 80점 미만')

조건부 표현식

참인 경우가 앞에 쓰이고 조건문이 중간에 들어간다.

score = 85
result = "Success" if score >= 80 else "Fail"

global 키워드

• 함수 내부에서 함수 바깥쪽에 있는 변수를 사용하고자 한다면 global 키워드를 사용한다.
• 값을 가지고 지지고볶고 할게 아니라, 단순 출력하거나 참조만 하는 경우에는 global 없이 참조 가능하다.
• list의 내부 메서드를 호출해 사용하는것 또한 오류가 나지 않는다.

a = 0
def func():
	golbal a
    a += 1
    
b = 10
def func2():
	print(b+20)
    
arr = [1, 2 ,3, 4, 5]
def func3():
	array.append(10)

여러개의 반환 값

파이썬에서 함수는 여러개의 반환 값을 가질 수 있다.

def operator(a, b):
	add = a + b
    subtract = a - b
    multiply = a * b
    divide = a / b
    return add, substract, multiply, divide
    a , b, c, d = operator(10, 3)

람다 표현식

• 함수를 간단하게 작성할 수 있다.
• 함수가 한번만 쓰이고 마는 경우 가능에 한줄로 표현 가능하다.
• 함수 자체를 입력으로 받는 함수에서 유용하다.

print((lambda a, b: a+ b)(3, 7)) # 10

여러개의 리스트에 적용

list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9, 10]
# 각각의 원소를 더한다.
result = list(map(lambda a,b: a + b, list1, list2))
print(result) # [7, 9, 11, 13, 15]

실전에서 유용한 표준 라이브러리

itertools

• 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들 제공
• 특히 순열과 조합 라이브러리 (완전탐색 유형인 모든 경우의 수를 고려 할 때)

heapq

• 힙 자료구조 제공
• 일반적으로 우선순위 큐 기능을 구현하기 위해 사용 (다익스트라)

bisect

• 기본적인 이진 탐색 기능을 제공

collections

• deque이나 Counter 등의 유용한 자료구조를 포함

math

• 필수적인 수학적 기능을 제공
• 팩토리얼, 제곱근, 최대공약수, 삼각함수 관련 함수부터 파이와 같은 상수를 포함

내장함수

sum, min, max, eval(수식으로 표현된 식이 있을 때 계산한 결과를 반환), sorted(arr, key(정렬기준으로 일반적으로 람다), reverse),

순열과 조합

순열

서로 다른 n개에서 서로 다른 r개를 선택해서 일렬로 나열
{'A', 'B', 'B'}에서 세 개를 선택해 나열. 'ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA'

from itertools import permutations
data = ['A', 'B', 'C']
result = list(permutations(data, 3))

중복 순열

순서를 고려하고 중복을 허용해서 2개를 뽑는 모든 경우의 수
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]

from itertools import product
data = ['A', 'B', 'C']
result = list(product(arr, repeat=2))

조합

서로 다른 n개에서 순서에 상관 없이 서로 다른 r개를 선택하는 것
{'A', 'B', 'B'}에서 순서를 고려하지 않고 두 개를 뽑는 경우. 'AB', 'AC', 'BC'

from itertools import combinations
data = ['A', 'B', 'C']
result = list(combinations(data, 2))

중복 조합

순서에 상관없이 중복 허용해서 2개를 뽑는 모든 경우의 수
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

from itertools import combinations_with_replacement
result = list(combinations_with_replacement(arr, 2))
print(result)

Counter

collections 라이브러리의 Counter는 등장 횟수를 세는 기능을 제공한다. 리스트와 같은 반복 가능한 객체가 주어졌을 때 내부의 원소가 몇 번씩 등장했는지를 반환 해 준다.

from collections import Counter
arr = ['red', 'red', 'blue', 'blue', 'blue', 'blue']
counter = Counter(arr)
print(counter['red']) # 2
print(counter['blue']) # 4

최대 공약수

math 라이브러리의 gdc() 함수를 이용할 수 있다.

import math
def lcm(a, b):
  return a * b // math.gcd(a, b)

a = 21
b = 14

print(math.gcd(21, 14)) # 7
print(lcm(21,14)) # 42