Alogorithm

[Python Algorithm Interview] 03. 리스트, 딕셔너리

리스트, 딕셔너리 리스트 C++에서는 std::vector, JAVA에서는 ArrayList에 해당합니다. 파이썬에서 리스트의 마지막 요소의 .append(), pop()에 대해서는 O(1)의 시간 복잡도를 갖습니다. 반면, 첫 번째 요소를 추출하는 pop(0)은 O(1)의 시간 복잡도라고 생각할 수 있으나, O(n)의 시간 복잡도를 갖습니다. 이 경우, Deque와 같은 자료형을 사용하여 성능을 높일 수 있습니다. 리스트의 주요 연산 시간 복잡도 연산 시간 복잡도 비고 len(a) O(1) a[i] O(1) a[i:j] O(k) i부터 j까지 슬라이싱한 길이인 k만큼 element in a O(n) 순차 탐색이라 n만큼 시간 소요 a.count(element) O(n) a.index(element) O..