[python] 파이썬 알고리즘 인터뷰 - 빅오, 자료형

 

 

 

빅오(O, big - O)

입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구사항(공간 복잡도)이 어떻게 증가하는 지를 분류하는 데 사용 

입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법

 

 

 

점근적 실행 시간을 표기할 때 사용하는 것이 빅오이다. 
점근적 실행 시간(알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산복잡도) 은 달리 말하면 시간복잡도 이다. 

 

 

 

빅오 표기법
최고차항만을 표기, 계수는 무시한다.

 

 

•  O(1) : 입력값이 아무리 커도 실행 시간은 일정함 
  예시) 해시 테이블의 조회 및 삽입
  
  
• O(log n) : 매우 큰 입력값에도 크게 영향을 받지 않는 편 
  예시 ) 이진 검색 
  
  
• O(n) : 입력값만큼 실행시간에 영향을 받음. 시간은 입력값에 비례 
  선형 시간 알고리즘이라고 함. 
  예시 ) 정렬되지 않은 리스트에서 최댓값 혹은 최솟값 찾기 
  
  
• O(nlogn) : 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 대부분 해당 
  적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 알고리즘은 O(nlogn) 보다 빠를 순 없음 
  
  
• O(n^2) : 버블 정렬 같은 비효율적인 정렬 알고리즘 
  
  
• O(2^n) : 피보나치 수를 재귀로 계산하는 알고리즘 
  
  
• O(n!) : 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루투 포스로 풀이할 때 해당 

 

 

시간과 공간 관계 : 트레이드 오프 
실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느리다. 

 

 

 

 

상한과 하한

 

• 빅오 : 상한을 의미 (가장 늦게 실행될 때)
• 빅오메가 : 하한을 의미 (가장 빨리 실행될 때)
• 빅세타 : 평균을 의미 

 

 

 

---

 

 

 

 

파이썬 자료형

 

 

1. 숫자 

파이썬에서는 숫자 정수형으로 int 만을 제공.

고정 정밀도 정수형은 지원하지 않게됨. 

 

bool 또한 int의 서브 클래스 

 

object > int > bool

 

 

 

---

 

 

2. 매핑

 

매핑이란 키와 자료형으로 구성된 복합 자료형 

파이썬에서 내장된 유일한 매핑 자료형은 딕셔너리 

 

 

---

 

 

3. 집합

 

 

중복된 값을 갖지 않는 자료형 
set 이 해당 

set은 입력 순서가 유지되지 않는다. 

 

 

# set 
a = {'a', 'b', 'c'}

# dictionary
a = {'a':'A', 'b':'B', 'c':'C'}

 

 

 

---

 

 

 

4. 시퀀스 

 

 

어떤 특정 대상의 순서 있는 나열. 수열 이라고도 함 

 

• str : 문자의 순서 있는 나열로 문자열을 이루는 자료형 
• list : 다양한 값들을 배열 형태의 순서 있는 나열로 구성하는 자료형. 자유롭게 값을 추가, 삭제 할 수 있는 동적 배열 

 

불변 시퀀스 : str, tuple, bytes

가변 시퀀스 : list 

 

 

# str의 참조 

a = 'abc'

a = 'def'

 

a가 'abc' 였다가 'def' 가 되었다고 해서 값 자체가 변경된 것이 아니라 
a가 참조하는 주소가 달라진 것이다. 

 

 

 

---

 

5. 객체 

파이썬은 모든 것이 객체.

 

언어	지원 타입 형태
C	원시 타입
자바	원시 타입, 객체
파이썬	객체

 

 

C나 자바는 성능에 대한 우선순위가 높은 언어이며 매우 빠른 연산이 가능. 하지만 공간을 많이 차지 한다. 
하지만 파이썬은 편리한 기능 제공에 우선순위를 둔 언어. 

 

 

 

파이썬은 불변 객체와 가변 객체로 구분

 

 

 

불변 객체

클래스	설명
bool	부울
int	정수
float	실수
tuple	리스트와 튜플 차이는 불변 여부
str	문자

 

 

 

가변 객체 

클래스	설명
list	리스트
set	중복된 값을 갖지 않는 집합
dict	딕셔너리

 

 

 

---

 

6. 불변 객체 

 

 

파이썬은 모든 것이 객체이기 때문에 원시 타입처럼 각각의 값들이 각 메모리의 다른 영역에 위치하는 게 아니라 
모두 같은 위치에 존재한다. 

 

10
a = 10
b = a

print(id(10), id(a), id(b))

 

 

 

 

 

 

 

 

그렇다면 만약 a 값을 11로 바꾸면 b 도 11로 바뀌어야 하는 게 아닌가?!

-> 그렇지 않다. 

 

 

 

 

파이썬의 숫자와 문자는 모두 불변이기 때문

 

 

 

 

값을 담고 있는 변수는 참조일 뿐이고, 실제로 값을 갖고 있는 int 와 str은 모두 불변. 
int, str, tuple 은 불변 객체이르모 dict 의 키나 set 의 값으로 사용 가능하다. 

 

 

 

---

 

7. 가변 객체 

 

 

list 는 다른 변수가 참조하고 있을 때 값을 변경하면 그 변수의 값이 변경될 수 있다. 

 

 

a = [1,2,3,4,5]
b = a
print(b)   # 변경 전 

a[2] = 4
print(a)   # 변경 후 
print(b)

 

 

 

 

 

 

 

 

 

리스트 a의 요소를 변경했더니 b 또한 같이 바뀌는 것을 볼 수 있다. 

 

 

 

 

 

 

출처 : 파이썬 알고리즘 인터뷰 | 박상길