[파이썬 알고리즘 인터뷰] 2부 - 파이썬 (~ 4장 - 빅오, 자료형)

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

4장 빅오, 자료형

1) 빅오

• 빅오란?
  • 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기법
    = 점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나
  • 시간 복잡도(Time Complexity) = 점근적 실행 시간
    어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity)
  • 빅오로 시간 복잡도를 표현할 때는 최고차항만 표기, 계수 무시
    (ex) $$4n^2+3n+4   \approx   O(n^2)$$
• 빅오의 종류
  
  

  1	O(1)	해시 테이블	상수 시간	매우 가치있음
  2	O(log n)	이진 탐색		입력에 영향이 적음
  3	O(n)	순차 탐색	선형 시간	입력값에 비례
  4	O(nlog n)	팀소트, 병합정렬		효율이 좋은 정렬 알고리즘이 해당
  5	O(n2)	버블 정렬	지수 시간	비효율적인 알고리즘
  6	O(2n)	피보나치 + 재귀
  7	O(n!)	TSP + brute force		가장 느린 알고리즘

  
  
  • O(1) - 상수 시간
    
    1. 입력값이 커도 실행 시간이 일정
    2. 매우 가치가 큰만큼 신중해야함
    3. 상수 시간이 매우 크면 의미가 없음
    4. (ex) 해시 테이블
  • O(log n)
    1. 큰 입력값에도 영향이 적은 편
    2. (ex) 이진 검색
  • O(n) - 선형 시간
    1. 실행 시간이 입력값에 비례
    2. 모든 입력값을 적어도 한 번 이상 살펴봐야하는 경우
    3. (ex) 정렬되지 않은 리스트에서 최댓값/최소값 찾을 때?
       - 단순한 순차탐색의 경우를 의미하는 듯
  • O(nlog n)
    1. 대부분 효율 좋은 정렬 알고리즘의 시간복잡도
    2. 적어도 한 번 이상 비교해야하는 비교 기반 정렬 알고리즘은 이보다 빠를 수 없음
    3. 그러나 입력값이 최선인 경우 비교를 건너 뛰어 O(n)이 될 수 있음
       - 팀소트(Timsort)
    4. (ex) 병합 정렬
  • O(n²)
    1. 비효율적인 알고리즘의 시간복잡도
    2. (ex) 버블 정렬
  • O(2ⁿ)
    
    1. (ex)피보나치 수를 재귀로 계산하는 알고리즘의 시간복잡도
       - 각 함수호출마다 최대 2번 재귀호출
       - n값이 커질 때마다 재귀호출의 depth가 늘어남
    2. n²과 비교할 때
       - n = 4까지는 큰 차이가 없음
       - n = 15일 때, 225와 32768로 145배 이상 차이가 벌어짐
  • O(n!)
    1. (ex) TSP를 brute force로 해결하는 알고리즘의 시간복잡도
    2. 가장 느린 알고리즘?
       - 가장 느린지는 모르겠지만, NP problem 중 대표적인 문제에 해당
• 공간 복잡도
  • 빅오는 공간 복잡도를 표현하는 데에도 쓰임
  • 보통 시간과 공간은 트레이드 오프 관계
• 상한과 최악
  • 빅오(O)는 상한(Upper Bound)를 의미
  • 빅오메가(Ω)는 하한(Lower Bound), 빅세타(Θ)는 평균
  • 학계와 달리 업계는 빅세타와 빅오를 합쳐서, 상한 시간으로 단순 표현
  • [주의] 상한을 최악의 경우와 혼동하는 것
    1. 빅오 표기법은 복잡한 함수를 적당히 표현한 방법임
    2. 최악의 경우/ 평균적인 경우의 시간 복잡도와 아무 관계가 없는 개념
    3. 참고자료
       2021.07.02 - [개발/개발지식] - 빅오(O)는 왜 최악의 경우가 아닐까

빅오(O)는 왜 최악의 경우가 아닐까

• 분할 상환 분석 (Amortized Analysis)
  • 알고리즘의 복잡도를 계산할 때, 최악의 경우만 살펴보는 것이 비관적이란 이유로 등장한 분석 방법
  • 분할 상환 분석이 유용한 대표적인 예 : 동적 배열
    - 동적 배열에서 doubling이 일어나는 일은 어쩌다 한 번 뿐임
    - 그럼에도 doubling으로 인해 아이템 삽입 시간 복잡도가 O(n)
    - 이 경우, 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 시간 복잡도를 계산(분할 상환, 또는 상환이라 함)
    - 이로 인해 동적 배열의 삽입 시간 복잡도는 O(1)
  • 참고자료
    2021.07.09 - [개발/개발지식] - [번역 - Cornell Univ.] 분할 상환 분석 (Amortized Analysis)

[번역 - Cornell Univ.] 분할 상환 분석 (Amortized Analysis)

• 병렬화
  • 일부 알고리즘은 병렬화로 실행 속도를 높일 수 있음
  • 딥러닝의 인기와 함께 병렬화가 주목받고 있음
  • GPU는 병렬 연산을 위한 대표적인 장치
    - GPU의 각 코어는 CPU보다 느리지만 수천여 개로, CPU보다 수백 배 더 많은 연산을 동시에 수행
  • 알고리즘이 병렬화가 가능한지는 근래 알고리즘의 우수성 평가에 매우 중요한 척도 중 하나

2) 자료형

• 파이썬 자료형
  

  

  출처 : <파이썬 알고리즘 인터뷰>  p.107, 책만, 2020

  • 숫자
    - 파이썬에는 숫자 정수형으로 int만 제공
    - PEP 237을 통해, 임의 정밀도(Arbitrary-Precision) 정수형인 int 하나만 제공
    - bool은 내부적으로 int의 서브 클래스
    - True == 1, False == 0 (True == 2는 False)
  • 매핑
    - key와 자료형으로 구성된 복합 자료형
    - 딕셔너리가 해당
  • 집합
    - 중복된 값을 갖지 않는 자료형
    - 선언 : a = set() 또는 a = {1, 2, 3}
    - 딕셔너리와 동일하게 중괄호를 사용하는 것 주의
    - 입력 순서가 유지되지 않음
  • 시퀀스
    - 순열 같은 의미 : 어떤 특정 대상의 순서 있는 나열
    - str과 list 비교 : str은 문자의 순서 있는 나열, list는 다양한 값의 순서 있는 나열
    - 시퀀스는 Mutable과 Immutable로 나뉨
    - Immutable : str, tuple, bytes
    - "str은 값을 바꿀 수 있는데?"라는 의문 ->2021.06.29 - [개발/개발지식] - 구글 파이썬 스타일 가이드 - 2.12 Default Argument Values (Mutable vs Immutable)
    - 또한 str은 Immutable 객체로 str[0] = 'd'와 같은 값의 변경이 불가능
• 원시 타입
  • C나 Java에서 제공하는 int, float, long 등과 같은 타입형
    

    C	원시 타입
    Java	원시 타입, 객체
    Python	객체

  • 원시 타입을 객체로 변환했을 때
    
    1. Pros
       - 문자로 변환
       - 16진수로 변환
       - shifting 같은 비트 조작
    2. Cons
       - 메모리 점유율
       - 계산 속도 감소
• 객체
  • 불변객체와 가변객체 ->2021.06.29 - [개발/개발지식] - 구글 파이썬 스타일 가이드 - 2.12 Default Argument Values (Mutable vs Immutable)
  •  is와 ==
    - is는 id를 비교하는 함수
    - ==는 값을 비교하는 연산자
    - None은 null로서 값이 정의되지 않으므로 ==로 비교 불가
  • Python은 객체로 이루어져있어 속도가 느림
  • 원시 타입은 메모리에서 값을 꺼내 한 번 연산하면 끝이지만, Python은 객체에서 값을 꺼내는 것도 오래걸림
  • NumPy의 경우 빠른 속도로 유명한데, C로 만든 모듈로 내부적으로 C의 원시 타입으로 처리하기 때문
  • 자료구조, 자료형, 추상 자료형
    - 자료구조 : 데이터에 효율적으로 접근하고 조작하기 위한 데이터의 조직, 관리, 저장구조
    - 자료형 : 컴파일러 또는 인터프리터에게 프로그래머가 데이터를 어떻게 사용하는지 알려주는 일종의 데이터 속성
    - 추상 자료형(ADT) : 자료형에 대한 수학적 모델, 해당 유형의 자료에 대한 연산들을 명기한 것
    참고자료: (제작중.......)