[알고리즘] 알고리즘 설계하기&실전에서 유용한 파이썬 표준 라이브러리

sunnwave·2022년 5월 25일

알고리즘 코딩테스트

알고리즘

목록 보기

1/47

✔ 알고리즘 설계 Tip

코딩 테스트 문제에서 시간제한은 통상 1~5초 가량
- 혹여 문제에 명시되어 있지 않은 경우 대략 5초 정도라고 생각하고 문제를 푸는 것이 합리적
시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같다
- N의 범위가 500인 경우: 시간복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 2,000인 경우: 시간복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 100,000인 경우: 시간복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 10,000,000인 경우: 시간복잡도가 O(N)인 알고리즘을 설계하면 풀 수 있다.

✔내장함수

기본 입출력 함수부터 정렬 함수까지 기본적인 함수 제공

sum(), min(), max(), eval(), sorted(), sorted() with key

✔itertools

파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공

특히 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용됨

순열

from itertools import permutations
 data=['A','B','C']
 result=list(permutations(data,3)  #모든 순열 구하기
 
 #[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]

조합

 	from itertools import combinations
    data=['A','B','C']

    result=list(combinations(data,2)) #2개를 뽑는 조합 구하기
    print(result)

    #[('A', 'B'), ('A', 'C'), ('B', 'C')]

중복순열

	from itertools import product

	data=['A','B','C']

	result=list(product(data,repeat=2))  #2개를 뽑는 모든 순열 구하기(중복 허용)
	print(result)

	#[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]

중복조합

	from itertools import combinations_with_replacement

	data=['A','B','C']

	result=list(combinations_with_replacement(data,2))  #2개를 뽑는 모든 조합 구하기(중복 허용)
	print(result)

	#[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

✔ heapq

힙(Heap) 자료구조를 제공
일반적으로 우선순위 큐 기능을 구현하기 위해 사용됨

✔ bisect

이진 탐색(Binary Search) 기능을 제공

✔ collections

덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함

Counter()

등장 횟수를 세는 기능 제공
리스트와 같은 반복 가능한(iterable)객체가 주어졌을 때 내부의 원소가 몇 번씩 등장했는지를 알려줌

		from collections import Counter
		counter=Counter(['red','blue','red','green','blue','blue'])

		print(counter['blue']) #'blue'가 등장한 횟수 출력
		print(counter['green']) #'green'이 등장한 횟수 출력
		print(dict(counter)) #딕셔너리 형으로 변환
   
   		#3
		#1
   		#3{'red': 2, 'blue': 3, 'green': 1}