🧩 코딩 테스트 정복기 @21#B*04

파이썬 알고리즘 인터뷰

📚📚📚👈🏻 책 구매 링크

🤴🏻👸🏻👵🏻👴🏻 👈🏻 소스코드 깃허브

😥😱🤪👈🏻   책 정오표   

🏓📡📺  👈🏻   유투브 채널

---

 

빅오, 자료형

Big-O 빅오는 입력값이 커질 때 알고리즘의 실행 시간과 함께 공간 요구사항이 어떻게 증가하는지를 분류하는데 사용한다.

(간단히 말하면 알고리즘의 효율성을 평가하는 척도라고 보면된다.)

 

시간 복잡도 Time Complexity 

어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미한다. Computational Complexity

계산 복잡도를 표기하는 대표적인 방법이 빅오인 것이다.

 

O(1) : 입력이 아무리 커져도 일정하다는 의미이다. 최고의 알고리즘. 이상적인 알고리즘이다. 

O(log n) : 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 본다.  이정도면 매우 견고한 알고리즘이다.

O(n) : 입력값만큼 실행 시간에 영향을 받는다. 비례관계이므로, 보통 수준이라고 보면된다.

O(n log n) : 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 아무리 좋은 알고리즘도 이보다 빠른 순 없다.

O(n^2) : 버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.O(2^n) : 피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다. n^2와 혼동하는 경우가 있는데, 2^n이 훨씬 크다. O(n!) : 브루트 포스. 가장 느린 알고리즘이다. 

---

알고리즘은 '시간과 공간이 트레이드오프Space-Time Tradeoff 하는 관계'이다. 

상한과 최악

빅오는 상한 Upper Bound을 의미한다. 하한 Lower Bound을 나타내는 빅오메가,평균을 의미하는 빅세타가 있다. 

 

' 빅오를 최악의 경우와 혼동 하면 안된다. 적당히 정확하게 표현하는 방법일 뿐을 명심해야 한다. '최악의 경우와 평균적인 경우의 시간 복잡도와는 상관이 없다. 

 

f(n) 이라는 함수가 있을 때, 가장 빨리 실행되는 경우(하한), 가장 늦게 실행되는 경우(상한)을 뜻한다. 

상한은 빅오, 하한은 빅오메가, 평균은 빅세타로 지칭한다 보면된다. 

n0이하일 때는 값이 작은 경우이니 무시한다는 의미이고, 

빅오 표기법은 n이 매우 클 때의 전체적인 큰 그림에 집중한다. 

 

분할 상환 분석

Amortized Analysis 분할 상환 분석은 시간 또는 메모리를 분석하는 알고리즘의 복잡도를 계산할 때, 

알고리즘 전체를 보지 않고 최악의 경우만을 살펴보는 것은 지나치게 비관적이라는 이류로 분할 상환 분석 방법이

등장하는 계기가 됐다. 

최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산한다. 

 

병렬화

병렬화를 통해 실행 속도를 높일 수 있다. 최근 딥러닝의 인기로 주목 받고 있다. 

GPU는 병렬 연산을 위한 대표적인 장치이다. 

CPU가 비행기로 짐을 여러번 나른다면, GPU는 배로 수많은 짐을 한번에 나르는 것에 비유할 수 있다. 

즉, 알고리즘의 시간 복잡도 외에도 병렬화가 가능한지는 근래에 알고리즘의 우수성을 평가하는 중요한 척도가 되고 있다.

 

자료형

매핑 Mapping

키와 자료형으로 구성된 복합 자료형이다. 

파이썬에서는 딕셔너리가 유일하다. 

집합 

set은 중복된 값을 갖지 않는다. 비어있는 집합을 선언하는 방식은 a = set() 으로 한다. 비어있지 않은 경우a = {1,2,3} 의 형태로 {}을 사용한다. 

시퀀스

Sequence 수열의 의미이다. 파이썬에서는 시퀀스 타입이 사실상 배열의 역할을 한다. 파이썬에서는 list 로 사용한다.list는 Immutable 불편 과 Mutable 가변으로 구분한다. 

 

str, tuple, bytes 가 불변으로 구분된다. 이 말의 의미는 선언과 동시에 메모리 상에 자리를 차지하게 되며, 이를 다른 값으로 선언하더라도그 자리의 주소는 바뀌지 않는다는 의미이다. (엄연히 말하면 컴퓨터 상에서 주소는 안바뀌지만, 우리가 보는 눈으로는 변경가능한 것이다.)

 

원시 타입 

Primitive Type 은 Java, C에서 주로 사용되는데, 속도 향상에 이점을 준다고 생각하면 된다. 파이썬은 어떨까.파이썬은 원시 타입을 지원하지 않는다. 

객체

파이썬은 모든 것이 객체이다. 불변 객체, 가변 객체  두 가지로 구분할 수 있다. 

is 와  ==

is 와 == 이 둘은 파이썬의 비교 연산자 중 하나들이다. 

# 
a  = [1,2,3]
a == a	# True
a == list(a)	# True
a is a 	#True
a is list(a) 	# False

b = [ 1,2,3 ]
b == copy.deepcopy(b)	# True
b is compy.deepcopy(b) 	# False

 

파이썬의 객체 구조는 편리하고 강력하다.

그러나 속도가 떨어진다. (C 나 Java 에 비해서) 

그런데 왜 파이썬은 원시 타입 배열을 사용하지 않고, 굳이 리스트 같은 것을 사용하거나 객체를 사용할까?

 

 

자료구조, 자료형, 추상 자료형 

Data Structure

Data Type 

Abstract Data Type 

이 셋은 비슷해보이지만 명확히 차이가 있다.

 

자료구조는 데이터에 효율적으로 접근하고 조작하기 위한 데이터의 조직, 관리, 저장 구조를 말한다.

자료형은 컴파일러 또는 인터프리터에게 프로그래머가 데이터를 어떻게 사용하는지를 알려주는 일종의 데이터 속성이다.

추상 자료형은 일반적으로 ADT라 부른다. 해당 유형이 자료에 대한 연산들을 명기한 것이다. 

어떠한 행동만을 정의할 뿐 실제 구현 방법은 명시하지 않고 있다.

(Java  에서 추상화를 떠올리면 된다.)