코딩 테스트) 빅오, 자료형

 

빅오, 자료형

 

 

빅오란?

 

 컴퓨터과학에서 빅오는 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구사항(공간 복잡도)이 어떻게 증가하는지를 분류하는 데 사용되며, 알고리즘의 효율성을 분석하는 데에도 매우 유용하게 활용된다.

 

 먼저 빅오(O, big-O)란, 점근적 실행 시간을 표기하는 대표적인 수학적 표기법이다. 여기서 점근적 실행 시간이란, 입력값이 무한대를 향할때 lim 함수의 실행 시간의 추이를 의미한다.(어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도이다.) 관심의 대상은 입력의 크기가 충분히 클 때인데, 이렇게 입력이 큰 경우에는 알고리즘의 효율성에 다라 수행 시간이 크게 차이가 날 수 있다. 

 

파일이 작다면 온라인으로 전송하는 것이 비행기를 통해서 전달하는 것 보다 좋을 것이다. 파일이 크다면 온라인 전송 보다는 오프라인 전송이 더 빠를 것이다. 비행기를 통해서 전달하는 경우, 파일의 크기와 상관없이 일정한 시간이 소요되지만 온라인으로 전송할 경우에는 파일이 클 수록 소요 시간이 늘어난다.

 

 빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며, 상수항은 무시한다. 또한 빅오는 시간 복잡도 외에도 공간 복잡도를 표현하는 데에도 널리 쓰인다. 알고리즘은 '시간과 공간의 트레이드 오프' 관계이기에 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느리다.

 

다음은 빅오의 표기법 종류이다.

• O(1) : 입력값이 아무리 커도 실행 시간은 일정
• O(log_n) : 실행 시간은 입력값에 영향을 받음 (웬만한 n의 크기에 대해서 매우 견고)
• O(n) : 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례(선형 시간 알고리즘) -> 모든 입력값을 적어도 한 번 이상은 살펴봐야 함
• O(n log_n) : 효율 좋은 정렬 알고리즘
• O(n**2) : 비효율적인 정렬 알고리즘
• O(2**n) : 피보나치 수를 재귀로 계산하는 알고리즘
• O(n!) : 가장 느린 알고리즘으로 입력값이 조금만 커져도 웬만한 다항 시간 내에는 계산이 어려움

 

빅오, 상한과 최악

 

 빅오는 상한(Upper bound)을 의미한다. 하한(Lower bound)은 빅오메가, 평균은 빅세타가 있다. 이러한 모든 것을 단순화해서 표현하기 위해 빅세타, 빅오메가와 빅오를 하나로 합쳐서 단순화해서 표현하려는 경향이 있다. 빅오를 함수의 실행으로 보면 다음과 같다.

 

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

 

 빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 '적당히 정확하게' 표현하는 방법일 뿐, 최악의 경우/평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념이다. 따라서 빅오 표기법은 "주어진 (최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다."고 할 수 있다.

 

 

분할 상환 분석

 

 시간 또는 메모리를 분석하는 알고리즘의 복잡도를 계산할 때, 알고리즘 전체를 보지 않고 최악의 경우 만을 살펴보는 것은 지나치게 비관적이라는 이유로 '분할 상환 분석 방법'이 등장하는 계기가 됐다. 분할 상환 분석 방법은 빅오와 함께 함수의 동작을 설명할 때 중요한 분석 방법 중 하나이다. 최악의 경우를 여러 번에 걸쳐 나눠주는 형태로 알고리즘의 시간 복잡도를 계산한다. 

 

 

자료형

 

파이썬3 표준 타입 계층 구조

1. 숫자

 파이썬에서는 숫자 정수형으로 int만을 제공한다. bool은 엄밀히 따지면 논리 자료형인데 파이썬에서는 내부적으로 1(True)과 0(False)로 처리되는 int의 서브 클래스이다. int는 object의 하위 클래스이기도 하기 때문에 결국 다음과 같은 구조를 띈다.

object > int > bool

 

'임의 정밀도'란? 임의 정밀도 정수형이란 쉽게 말해 무제한 자릿수를 제공하는 정수형을 말한다.

 

2. 매핑(Mapping)

 매핑 타입은 키와 자료형으로 구성된 복합 자료형이며, 파이썬에 내장된 유일한 매핑 자료형은 바로 딕셔너리이다.

 

3. 집합(Set)

 파이썬의 집합 자료형인 set은 중복된 값을 갖지 않는 자료형이다. 빈 집합이 아닌 값이 포함된 집합을 선언할 때는 a={1,2,3} 형태로 하는데, 집합은 딕셔너리와 동일하게 중괄호({})를 사용하므로 이 점에 유의해야 한다. 또한 set은 입력 순서가 유지되지 않으며, 중복된 값이 있을 경우 하나의 값만 유지한다.

 

4. 시퀀스

 시퀀스(Sequence)는 어떤 특정 대상의 순서 있는 나열을 뜻한다. 이는 불변과 가변으로 구분하는데 말 그대로 불변은 값을 변경할 수 없다. 불변에서 값을 변경할 수 없다는 것은 변수의 인덱스 하나만 변경할 수 없다는 것을 의미한다.

a = 'abc' >> a[1] = 't'

>> error

 

• 불변 : str, tuple, bytes, float, int, 
• 가변 : list, set, dict

 

불변 객체와 가변 객체

 

1. 불변 객체

 

 파이썬은 모든 것이 객체다. 불변 객체와 가변 객체로 구분할 수 있다. 파이썬에서 변수를 할당하는 작업은 해당 객체에 대해 참조를 한다는 의미이다. 값을 담고 있는 변수는 사실은 참조일 뿐이고, 실제로 값을 갖고 있는 int와 str은 모두 불변 객체이다. 이외에도 불변 객체로 tuple이 있다. 말 그대로, 한번 값을 담아두면 더 이상 값을 변경할 수 없다. 이와 반대로 list는 값을 변경할 수 있기에 dict의 키로 정하거나 set의 값으로는 추가할 수 없다. 

 

2. 가변 객체

 

 int, str과 달리 list는 값이 바뀔 수 있으며 이 말은 다른 변수가 참조하고 있을 때 그 변수의 값 또한 변경된다는 얘기다. 

a = [1,2,3]

b=a

b

>> [1,2,3]

a[2] = 4

print(a)

print(b)

>> [1,2,4]

>> [1,2,4]

 

위의 예시와 같이 가변 객체의 경우 참조 변수 중 값을 일부 변경하면, 참조 대상의 변수도 변한다.

 

 

파이썬에서 is와 ==
 is는 id() 값을 비교하는 함수다. None은 null로서 값 자체가 정의되어 있지 않으므로 ==로 비교가 불가능하다. 따라서 is로만 비교가 가능하다.
if a is None:
    pass

 ==은 값을 비교하는 연산자다. 아래의 예시를 보면 이해가 빠를 것이다.
a = [1,2,3]
a == list(a)
>> True
a is a
>> True
a is list(a)
>> False

값은 동일하지만 list()로 한 번 더 묶어주면, 별도의 객체로 복사가 되고 다른 ID를 갖게 된다. 따라서 is는 False가 된다. 

copy.deepcopy()
copy.deepcopy()를 복사하면 값은 같지만 ID는 다르게 되기 때문에, ==로 비교하면 True, is로 비교할 경우 False가 된다.

a = [1,2,3]
a == copy.deepcopy(a)
>>True
a is 
copy.deepcopy(a)
>>False