(1)파이썬알고리즘인터뷰 - 빅오와 자료형

 

 

빅오

 : 점근적 실행시간을 표기할 때 함수의 상한을 설명하는 수학적 표기 방법

 

점근적 실행시간이란 입력값이 무한대로 갈 때 함수의 실행시간의 추이를 의미한다 .

 

 

점근적 실행시간을 시간 복잡도라고 말 할 수 있는데

시간복잡도는 알고리즘을 수행하는데 걸리는 계산 복잡도로 이를 표기하는 대표적인 방법이 빅오다!

 

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

 

=> 시간복잡도를 표현하는 빅오!

 

 

자료형

 

1. 숫자

C와 같은 여느 언어들과 달리 파이썬에서는

숫자 정수형을 표현하는 자료형은 int 뿐이다. 

 

왜 long이 없을까?

-> 있었는데 사라짐 

 

2. 시퀀스

 

시퀀스는 '수열'과 같은 의미

 

str은 문자열을 이루는 자료형

list는 다양한 값들을 배열 형태의 순어 있는 나열로 구성하는 자료형이다. 

 

시퀀스는 불변형과 가변형으로 구분된다.

불변형은 str, tuple, bytes

가변형은 list가 있다. 

 

 

앞서 포스팅한 내용(처음배우는파이썬)처럼 파이썬은 모든 것이 객체이고

할당하는 것은 그 객체에 이름표를 붙이는 것이라고 생각하면된다.

 

그래서 불변형 객체는 변하지 않고 이름표만 다른 곳에 붙일 수있기에 

str이 불변형이 아닌 것처럼 보이는 것이다.

 

 

 

객체

파이썬은 모든 것이 객체다.

크게 불변객체, 가변객체로 구분할 수 있다.

 

list, set, dict가 대표적인 가변 객체이다. 

int, bool, float 등은 불변 객체이다.

 

   

-> list는 객체에 대한 포인터 목록을 관리하는 형태로 구현되어 있다. 

<연결리스트에 대한 포인터 목록 관리>

 

(내부적으로 동적배열로 구현되어있음)

 

.del a[Idx] -> 인덱스를 이용해 값 제거

a.remove(3) -> 값을 이용해 삭제할 수 있다.

 

 

-> 딕셔너리는 내부적으로 해쉬테이블로 구현되어있다.

대부분의 연산이 O(1)인 우수 자료형이다.

원래는 입력 순서가 유지되지않아 OrderedDict()라는 별도 자료형을 제공하였으나

3.7버젼부터는 입력 순서를 유지하도록 개선되었다.