파이썬 알고리즘 인터뷰. 4장 요약

빅오

빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며, 상수항은 무시한다.

$O(1)$: 입력값이 아무리 커도 실행시간 일정. 대표적으로 해시 테이블의 조회 및 삽입이 이에 해당함

$O(log n)$: 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 웬만한 n의 크기에 대해서도 매우 견고. 대표적으로 이진 검색이 이에 해당함

$O(n)$: 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례함. 이러한 알고리즘을 선형 시간 알고리즘이라고 함. 정렬되지 않은 리스트에서 최대값 또는 최소값 경우가 이에 해당하며 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴봐야 함

$O(n log n)$: 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당함. 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 $O(n log n)$보다 빠를 수 없다. 물론 입력값이 최선인 경우, 비교를 건너뛰어 $O(n)$ 이 될 수 있으며 팀소트가 이런 로직을 갖고 있음

$O(n^2)$: 버블 정렬과 같은 비효율적인 정렬 알고리즘이 이에 해당함

$O(2^n)$: 피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당함. 간혹 $n^2$과 혼당하는 경우가 있는데 처음에는 비슷해 보이지만 $2^n$이 훨씬 더 큼.

$O(n!)$: 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제 (Traveling Salesman Problem)을 브루트 포스로 풀이할 때가 이에 해당함

자료형

숫자

파이썬에서는 숫자 정수형으로 int만을 제공한다. PEP 237을 통해 버전 2.4부터는 int가 충분하지 않으면 자동으로 long 타입으로 변경되는 구조가 됐으며 덕분에 C와 달리 오버플로가 발생하는 일은 사라졌다.
bool은 엄밀히 따지면 논리 자료형인데 파이썬에서는 내부적으로 1(True)과 0(False)으로 처리되는 int의 서브 클래스다. int는 object의 하위클래스이기도 하기 때문에 결국 다음과 같은 구조를 띰
object > int > bool

매핑

매핑 타입은 키와 자료형으로 구성된 복합 자료형이며, 파이썬에 내장된 유일한 매핑 자료형은 딕셔너리임. 딕셔너리는 앞서 얘기한 리스트와 함께 가장 빈번하게 쓰이는 자료형임

집합

파이썬의 집합 자료형인 set은 중복된 값을 갖지 않는 자료형. 파이썬에서는 빈 집합은 다음과 같은 형태로 선언함

a = set()

set은 입력 순서가 유지되지 않으며, 중복된 값이 있을 경우 하나의 값만 유지됨

시퀀스

시퀀스는 불변과 가변으로 구분하는데 말 그대로 불변은 값을 변경할 수 없다. 여기에는 str, tuple, bytes가 해당되는데 한번 이 타입으로 선언되는 값은 변경할 수가 없음.

a = 'abc'
a = 'def'
type(a)

결과 : <class ‘str’>

a 변수는 str 자료형인데 처음에 abc를 할당했다가 이후에 def를 할당했다. 다소 혼동될 수 있는 내용인데 여기서 맨 처음에 a변수에 할당된 str타입인 abc는 변경된 적이 없다. 불변이다. 이후에 a 변수는 다른 str타입인 def를 다시 참조했을 뿐 실제로 abc도 def도 한번 생성된 후에 변경된 적이 없다. 불변이므로 변경될 수도 없다.

a = 'abc'
id('abc')

결과 : 4317530408

a = 'abc'
id(a)

결과 : 4317530408