deque, 유클리드 호제법
deque
스택 알고리즘 시간 복잡도 O(1)
FIFO 방식인 queue와 달리, 양방향성을 가졌다.
from collections import deque
d=deque('python')
d
#deque(['p','y','t','h','o','n'])
append, appendleft
d.append('x')
#deque(['p','y','t','h','o','n','x'])
d.appendleft('y')
#deque(['y','p','y','t','h','o','n','x'])
pop, popleft
d.pop()
#deque(['y','p','y','t','h','o','n'])
d.popleft()
#deque(['p','y','t','h','o','n'])
rotate
d.rotate(2)
#deque(['o','n','p','y','t','h'])
유클리드 호제법
숫자 a,b가 있을 때 a를 b로 나눈 나머지와 b의 최대공약수는 a,b 최대공약수와 같다.
최대공약수
def gcd(a, b):
while b > 0:
a, b = b, a % b
return a
최대공약수
a와 b를 곱한 것에서 최대공약수를 나눈다.
def lcm(a, b):
return a * b / gcd(a, b)