파이썬 코딩테스트 팁
입력 받기
- import sys
- input = sys.stdin.readline
2차원 배열 입력
- [list(map(int,input())) for _ in range(n)]
출력
- print(len(ans),*ans,sep='\n') : 1개씩 출력
- ''".join(list) : 모두 붙여서 출력, 시간복잡도 n
- 리스트 내에서 앞뒤로 비교해야 하는 경우 변수를 만들어 사용하기 or zip 활용하기 (슬라이싱 곁들임)
for문 활용법
두개의 값 출력
- L = [[1,2],[3,4],[5,6],[7,8]]
- for i,j in L:
문자열을 돌리는 for문에서 중간에 문자열을 편집해버리면(ex : pop) 문자열이 변경되며 out of range가 나올 수 있기 때문에 유의해야 한다.
enumerate
- 인덱스와 값을 같이 뽑아준다.
from itertools import accummulate
누적합
while 문
조건이 여러개인 경우 순서를 잘 생각해야 한다.
시간 복잡도
정렬은 시간 복잡도가 O(nlogn)이다.
형변환은 시간 복잡도가 O(n)이다.
join은 시간 복잡도가 O(n)이다.
Dictionary, DefaultDict
해시함수를 사용할 경우 사용된다.
이외에도 value의 자료형을 저장할 수 있는 DeafultDict가 있다.
.get(x,0) : x라는 key가 딕셔너리에 없는 경우 0을 돌려준다.
.itens() : key와 value값을 돌려준다.
에라토스테네스의 체
prime_num = [False,False] + [True]*(n-1)
is_prime=[]
for i in range(2,n+1):
if a[i]:
is_prime.append(i)
for j in range(2*i, n+1, i):
a[j] = False
print(is_prime)
파이썬 리스트 원본을 건드리지 않고
list_a = [1,2,3,4]
list_b = sorted(list_a)
역순 출력
list(map(list,zip(*mylist)))
덱
deque(maxlen = )
이 옵션으로 최대 덱의 크기를 조절할 수 있다.
힙
import heapq
heapq.heapify (힙 자료형으로 변경)
heapq.heappop(가장 작은 값 뽑음)
heapq,heappush(값을 넣음 알아서 힙 기준에 맞추어 정렬됨)
iterable
자신의 멤버를 한 번에 하나씩 리턴할 수 있는 객체, list, str, tuple, dict
sequence
int 타입 인덱스를 통해 원소에 접근할 수 있는 iterable, list,str,tuple에 해당한다.
map, filter, reduce
모든 원소에 어떤 함수를 적용할 경우 사용 (가독성 위주로 코드를 생각하자!)
int
문자열인 경우 int( a, 진법)으로 하면 진법에 맞춰 변환된 정수 값을 반환한다.
ljust,center,rjust
왼쪽가운데오른쪽 정렬
곱집합
import itertools
itertools.product(a,b)
2차원을 1차원으로
1. sum(list_a, [])
2. import iter tools
list(itertools.chain.from_iterable(list_a))
3. import iter tools
list(itertools.chain(*my_list))
4. [element for array in list_a for element in array]
5. from functools import reduce
list(reduce(lambda x, y: x+y, list_a))
6. from functools import reduce
import operater
list(reduce(opereater.add, list_a))
순열과 조합
- import itertools
- list(map(''.join, itertools.permutations(list_a)))
- list(map(''.join, itertools.permutations(list_a,2)))
- list(itertools.permutations(list_a,len(list)))
- or combination 사용
순열과 조합이 쓰이겠다 싶으면 dfs bfs를 먼저 생각해보자
for-else
- if - else 구조 만이 아닌 for 문이 다 돌고나서도 break이 없으면 else 에 있는 구문을 출력할 수 있다.
- 이때 for 과 else는 같은 선상에 있어야 한다
이진 탐색하기
import bisect
bisect.bisecct(list_a,탐색 지점))
알고리즘 없이 된다. ㅎ
가장 큰 수
'inf' 활용
람다 정렬
sorted(리스트, key= lambda x: (-x[2],-x[0],-x[1])
map(lambda x : x.split()[1], list) 와 같은 형태로 람다 객체도 반환 가능
숫자는 리스트 내의 값의 순서
+ 오름차순, - 내림차순
딕셔너리
{k : 0 for k in list} 와 같은 형태로 초기화도 가능
힙에서 최대값 빼기
heap = heapq.nlargest(len(heap), heap)[1:]
heapq.heapify(heap)
함수 정의하는 방법
def dfs(a : String, b : int) -> None
타입과 반환값을 정리해주면 좋다.
DFS
진행조건, 탈출 조건, 엣지케이스 생각하기