순차적으로 메모리를 할당하는 배열과 달리 구조체는 메모리의 어느 영역에나 어떤 크기로든 할당할 수 있는 사실상 유일한 복합 자료형이다.
파이썬에서 구조체와 같은 형태를 정의하려면 네임드 튜플(named tuple)을 사용해야 한다.
리스트 컴프리헨션
파이썬은 map, filter와 같은 함수형 기능을 지원하며 람다 표현식(lambda expression)도 지원한다.
list(map(lambda x: x + 10, [1, 2, 3]))리스트 컴프리헨션이란 기존 리스트를 기반으로 새로운 리스트를 만들어내는 구문이다.
[n * 2 for n in range(1, 10 + 1) if n % 2 == 1]enumerate
enumerate()는 '열거하다'는 뜻의 함수로, 순서가 있는 자료형(list, set, tuple 등)을 인덱스를 포함한 enumerate 객체로 리턴한다.
arr = [1, 3, 5, 7, 2, 4, 6, 8]
list(enumerate(arr))빅오, 자료형
빅오(big-O)는 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구사항(공간 복잡도)이 어떻게 증가하는지를 분류하는 데 사용된다.
빅오란 점근적 실행 시간(asymptotic running time: 입력값이 무한대로 향할 때 함수의 상한)를 표기할 때 가장 널리 쓰이는 수학적 표기법이다.
점근적 실행 시간을 달리 말해 시간 복잡도라 할 수 있다.
시간 복잡도(time complexity)는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(computational complexity)를 의미한다.
빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며, 상수항은 무시한다.
O(1): 상수 시간을 갖는 알고리즘으로 입력값이 아무리 커도 실행 시간은 일정하다.
O(log n): 실행 시간은 입력값에 영향을 받는다. 그러나 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 웬만한 n의 크기에 대해서도 매우 견고하다. 대표적으로 이진 검색이 이에 해당한다.
O(n): 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간(linear-time) 알고리즘이라 한다. 정렬되지 않은 리스트에서 최댓값 또한 최솟값 경우가 이에 해당하며 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상 살펴봐야 한다.
O(n log n): 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(n log n)보다 빠를 수 없다.
O(n^2): 버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.
O(2^n): 피보나치 수를 재귀로 계싼하는 알고리즘이 이에 해당한다.
O(n!): 외판원 문제를 브루트 포스로 풀이할 때가 이에 해당한다.
알고리즘은 흔히 '시간과 공간이 트레이드오프(space-time tradeoff)' 관계다.
실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느리다.
빅오 표기법은 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다.
