오뚝이개발자

deque(double ended queue)는 양방향 연결리스트로 구현되어 있어 양 끝단에 접근이 가능하고 데이터의 삽입, 삭제가 용이하다.(단, 중간 데이터는 제외) 여기선 대표적으로 많이 쓰이는 5가지 operation에 대해 사용법을 정리하려고 한다. 아, 참고로 deque를 사용하려면 import collections.deque를 해주어야 한다. append(x), appendleft(x) append(x)는 오른쪽 끝에 데이터 x를 추가, appendleft(x)는 왼쪽 끝에 데이터 x를 추가한다. 리스트와 달리 deque는 doubly linked list라 둘의 시간복잡도는 모두 O(1)이다. pop(), popleft() pop()은 일반적으로 알고있는 그 pop 연산이 맞다. 즉, st..

시간복잡도 아래는 자주 등장하는 시간복잡도 표기들이다. 표에서 아래로 갈수록 수행시간이 오래 걸린다. list 리스트는 배열이다. 그렇기 때문에 사이즈가 커질수록 삽입과 삭제 연산이 비효율적으로 된다. 이럴 땐 차라리 deque를 쓰는 것이 효율적이다. Operation Average Worst Copy O(n) O(n) Append O(1) O(1) Pop last O(1) O(1) Pop intermediate O(k) O(k) Get item O(1) O(1) Set item O(1) O(1) Delete item O(n) O(n) sort O(nlogn) O(nlogn) min,max O(n) O(n) len O(1) O(1) collections.deque deque(double ended qu..

정렬 방법 중 가장 빠른 것은 O(nlogn)의 시간복잡도를 갖는다고 생각할 수 있다. 하지만 이보다 빠른 O(n)의 시간복잡도를 갖는 정렬방법도 있다. 바로 계수 정렬 다른 말로, 카운팅 정렬이다. 하지만 이러한 계수 정렬은 약간 제한된 조건 하에서 사용가능하다. 1 5 2 3 2 5 1 4 4 2 5 1 위와 같은 수가 나열되어있고 이를 정렬해보자. 그런데 자세히 보면, 위에서 등장하는 수의 범위가 1~5까지라는 것을 알 수 있다. 이처럼 수의 범위가 정해져 있는 경우 계수 정렬을 사용하면 효율적으로 정렬할 수 있다. 카운팅 정렬이란 말 그대로 수가 등장하는 횟수를 카운트 하는 것이다. 카운팅이 다 끝나면 크기 순서대로, 해당 수가 등장하는 횟수만큼 print해주면 된다. 위의 경우, 등장하는 수를 ..

파이썬에는 in 연산자가 있다. 보통 리스트, 튜플, 집합, 딕셔너리 같이 연속적인 자료구조에 속한 멤버를 확인하거나 순회할 때 사용한다. 그렇다면 in 연산자의 시간복잡도는 어떻게 될까? List l = [1, 2, 3, 4, 5] # 멤버 확인 if 1 in l : print("1 is in l") # 순회 for i in l : print(i) Tuple t = (1, 2, 3, 4, 5) # 멤버 확인 if 1 in t : print("1 is in t") # 순회 for i in t : print(i) Set s = {1, 2, 3, 4, 5} # 멤버 확인 if 1 in s : print("1 is in s") # 순회 for i in s : print(i) Dictionary d = {1: ..