복잡도
시간 복잡도
- 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미
공간 복잡도
- 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미
빅오 표기법
python 문법
리스트 자료형
파이썬의 리스트 자료형은 배열 기능을 포함하고 있고, 내부적으로 연결 리스트 자료구조를 채택하여 append(), remove() 등의 메서드를 지원
리스트의 인덱싱과 슬라이싱
리스트 컴프리헨션
리스트 관련 기타 메서드
insert(), append(), remove()
insert() 함수를 사용할 때 원소의 개수가 N개면, 시간 복잡도는 O(N)이다.
자료형의 append()함수는 O(1)에 수행된다.
insert() 함수를 남발하면 '시간초과'!
remove()의 시간 복잡도 역시 O(N)
튜플 자료형
1) 튜플은 한 번 선언된 값을 변경할 수 없다.
2) 리스트는 대괄호([]) 를 이용하지만, 튜플은 소괄호 (())를 이용한다.
대입 연산자(=)를 사용하여 값을 변경할 수 없다는 의미
사전 자료형
집합 자료형
함수
람다식
- print((lambda a,b: a +b)(3, 7))
입출력
list(map(int, input(),split()))
input() 함수를 그대로 사용하지는 않는다. 파이썬의 기본 input() 함수는 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있기 때문이다.
이 경우에는 sys 라이브러리에 정의되어 있는 sys.stdin.readline()함수를 이용
sys 라이브러리는 다음과 같은 방식으로 사용하며 input() 함수와 같이 한 줄씩 입력 받기위해 사용한다.
import sys
data = sys.stdin.readline().rstrip()
print(data)주요 라이브러리
- 내장 함수 : print(),input() 등
- itertools: 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리 순열과 조합 라이브러리를 제공한다.
- heapq : 힙(Heap) 기능을 제공하는 라이브러리이다. 우선순위 큐 기능을 구현하기 위해 사용한다.
- bisect: 이진탐색 기능을 제공하는 라이브러리다.
- collections : 덱(deque),카운터(Counter)등의 유용한 자료구조를 포함하고 있는 라이브러리다
내장함수
sum() : 리스트와 같은 iterable 객체가 입력으로 주어졌을 때, 모든 원소의 합을 반환한다.
min() : 파라미터가 2개 이상 들어왔을 때 가장 작은 값 반환
max() : 파라미터가 2개 이상 들어왔을 때 가장 큰 값 반환
eval() : 수학 수식이 문자열 형식으로 들어오면 해당 수식을 계산한 결과를 반환
sorted() : iterable 객체가 들어왔을 때, 정렬된 결과를 반환한다. key 속성으로 정렬 기준을 명시할 수 있고, reverse 속성으로 정렬된 결과 리스트를 뒤집을지의 여부를 설정할 수 있다.
sort() : 리스트와 같은 iterable 객체는 기본으로 sort() 함수를 내장하고 있다.
itertools(순열,조합)
파이썬에서 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리
코딩테스트에서 가장 유용하게 사용할 수 잇는 클래스는 permutations, combinations
- permutations는 리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열)를 계산한다.
permutations는 클래스이므로 객체 초기화 이후에는 리스트 자료형으로 변환하여 사용한다.- combinations는 리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우를 계산한다.
- product 리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열)를 계산한다.
heapq
- 파이썬에서는 힙 기능을 위해 heapq라이브러리를 제공.
heapq는 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현할 때 사용
시간복잡도 O(NlogN)에 오름차순 정렬
힙에 원소를 삽입할 때는 heapq.heappush() 메서드를 이용
heapq.heappop()메서드 이용
파이썬에서는 최대 힙을 제공하진 않는다. heapq 라이브러리를 이용하여 최대 힙을 구현할 때는
원소의 부호를 임시로 변경하는 방식을 사용
힙에 원소를 삽입하기 전에 잠시 부호를 반대로 바꾸었다가 힙에서 원소를 꺼낸 뒤에 다시 원소의 부호를 바꾸면 된다.
bisect
- 파이썬에서는 이진탐색을 쉽게 구현할 수 있도록 bisect 라이브러리를 제공
bisect 라이브러리는 '정렬된 배열'에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용
bisect_left() 함수와 bistect_right() 함수가 가장 중요하게 사용, 시간복잡도는 O(logN)
collections
- 파이썬의 collections 라이브러리는 유용한 자료구조를 제공하는 표준 라이브러리다.
collections 라이브러리 기능중 deque와 Counter.
보통 파이썬에서는 deque를 사용해 Queue를 구현.
deque에서는 리스트 자료형과 다르게 인덱싱, 슬라이싱 등의 기능은 사용할 수 없다.
연속적으로 나열된 데이터의 시작 부분이나 끝 부분에 데이터를 삽입하거나 삭제할 때는 매우 효과적 deque는 스택이나 큐의 기능을 모두 포함한다고도 볼 수 있다.- deque는 popleft()로 첫 번째 원소를 제거하고 마지막 원소를 제거할 때는 pop()
첫 번째 인덱스에 원소 x를 삽입할 때는 appendleft(x)를 사용, 마지막 인덱스에 원소를 삽입할 때는 append(x)를 사용한다.
순열과 조합
- 파이썬에서 조합을 이용하기 위해서는 itertools의 combinations() 함수를 사용하면 된다.
