[python] 알고리즘 및 자료구조 정리 -2- 필수 라이브러리 및 파이썬의 이점

입출력 최적화: sys.stdin.readline()으로 속도 향상

input() 함수는 편리하지만 프롬프트 처리와 예외 처리로 인해 속도가 느림

반면, sys.stdin.readline()은 표준 입력 버퍼에서 원시 바이트를 직접 읽어오므로 대량의 입력을 처리할 때 훨씬 빠름

하지만 sys.stdin.readline()이 줄 끝의 개행 문자(\n)를 포함 하기 strip()이나 .rstrip()을 사용하여 이 문자를 제거해야함

 

lambda 활용

lambda 함수는

lambda x: x

구문으로 정의되는 익명의 인라인 함수

코딩 테스트에서 lambda의 주된 용도는 정렬 함수의 key 인자로 사용되며

튜플 리스트를 두 번째 요소 기준으로 정렬하는 것과 같은 복잡한 정렬 기준을 한 줄로 간결하게 표현가능

또한 map(), filter() 등과 함께 사용되어 간결한 함수형 스타일의 코드를 작성하는데 사용 가능

collections 모듈: 고성능 컨테이너

deque

양방향 큐로, 이중 연결 리스트로 구현되어 append(), pop(), appendleft(), popleft() 연산을 O(1)시간 복잡도로 제공

이로 인해 스택과 큐를 모두 구현하는 데 이상적인 고성능 도구가 되며,

pop(0)이나 insert(0,...) 연산이 O(n)인 표준 list보다 우수

Counter

해시 가능한 객체의 개수를 세는 데 특화된 딕셔너리 하위 클래스

Counter(my_list)는 리스트의 요소별 빈도를 담은 해시 맵을 즉시 생성하여 빈도수 계산 작업을 매우 간단하게 가능

defaultdict

존재하지 않는 키에 대해 기본값을 제공하는 딕셔너리

defaultdict(int)는 기본값으로 0을, defaultdict(list)는 빈 리스트를 제공하여, 데이터를 집계할 때

다음과 같이 사용 가능

if key in dict:
    print("Key exists in the dictionary.")

 

이터레이터(순서대로 다음 값을 리턴할 수 있는 객체)

permutations(iterable, r)

입력 이터러블에서 길이 r의 모든 가능한 순서(순열)를 생성

 

combinations(iterable, r)

길이 r의 모든 고유한 조합을 생성

이들은 모든 가능한 부분 집합이나 배열을 테스트해야 하는 무차별 대입 솔루션에 필수

heapq 모듈: 우선순위 큐

 

최소 힙을 구현

가장 작은 요소가 항상 루트(heap)에 위치

heapq.heappush()와 heapq.heappop()은 O(log n) 시간 복잡도로 힙 속성을 유지

최대 힙을 구현하기 위한 중요한 기법은 값에 음수를 취하여 푸시

"가장 작은"(가장 음수인) 값을 pop한 후 다시 음수를 취하면 원래의 가장 큰 값을 얻을 수 있음