Python Basic/파이썬 알고리즘 인터뷰

[2부] 04장 빅오, 자료형

EASYH 2021. 2. 4. 15:30

빅오 (big-O)

점근적 실행 시간 (Asymptotic Running Time)을 표기할 때, 가장 널리 쓰이는 수학적 표기법 중 하나. 

 

점근적 실행시간이란?

  • 입력값 n이 커질 때 (즉, 입력값이 무한대를 향할 때), 함수의 실행 시간의 추이

알고리즘은 궁긍적으로 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면, 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝남. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때. 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 남.

 

점근적 실행 시간은 달리 말하면 시간 복잡도 (Time Complexity)라고 함.

시간 복잡도란?

  • 사전적 정의: 어떤 알고리즘을 수행하는데 걸리는 시간을 계산 복잡도(Computational Complexity).
  • 이 때 계산 복잡도를 표기하는 대표적인 방법이 빅오 (Big O)

빅오로 시간 복잡도를 표기할 때는 최고차항만을 표기하며, 상수항은 무시.

 

빅오 표기법의 종류

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

O(1) -> 해시테이블의 조회 및 삽입 (11장)

입력값이 아무리 커도 실행 히간은 일정함. 최고의 알고리즘. 

다만, 만약 상수 시간에 실행된다 해도 상수값이 상상을 넘어설 정도로 매우 크다면, 사실상 일정한 시간의 의미가 없음. 최고의 알고리즘이 될 수 있지만, 그만큼 신중해야 함. 

 

O(log n) -> 이진 검색 (18장)

여기서부터 실행 시간은 입력값에 영향을 받음. 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편으로, 웬만한 n의 크기에 대해서도 매우 견고함. 

 

O(n)

입력값만큼 실행 시간에 영향, 알고리즘을 수행하는데 걸리는 시간은 입력값에 비례함. 

이러한 알고리즘을 선형 시간 (Linear-Time) 알고리즘이라고 함. 

정렬되지 않은 리스트에서 최댓값 또는 최솟값 경우가 이에 해당, 이 값을 찾기 위해서 모든 입력값을 적어도 한 번 이상은 살펴봐야 함. 

 

O(n log n) -> 병합 정렬 (17장)

대부분의 효율 좋은 정렬 알고리즘이 이에 해당. 

적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘이라도 O(n log n) 보다 빠를 수 없음. 

 

O(n^2) -> 버블 정렬 (17장)

버블 정렬과 같은 비효율적인 정렬 알고리즘

 

O(2^n) -> 피보나치 수를 재귀로 계산하는 알고리즘 (23장)

 

O(n!) -> Travelling Salesman Problem (TSP) 문제를 브루트 포스로 풀이할 때 (12장)

TSP: 각 도시를 방문하고 돌아오는 가장 잛은 경로를 찾는 외판원 문제

가장 느린 알고리즘. 

 

알고리즘은 흔히 '시간과 공간이 트레이드 오프 관계 (Space-Time Tradeoff)' 라고 함. 

즉, 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느림. 

 

상한과 최악

빅오 표기법은 주어진 (최선/최악/평균) 경우의 수행 시간의 상한을 나타냄. 

  • e.g. 퀵 정렬의 로무토 파티션에서 
    • [1,4,3,7,8,6,5] 의 입력값은 18번의 비교 또는 스왑 연산이 필요하고, 이 경우 최선의 경우임. 
    • [1,2,3,4,5,6,7] 의 입력값은 48번 연산이 필요하고, 이 경우 최악의 경우임. 
  • 빅오 표기는 함수 f(n)이 있을 경우, 이 함수의 실행 상한(가장 늦게 실행될 때)를 나타냄. 
    • 이 함수가 가장 빨리 실행될 때 (실행 하한)는 빅오메가 라고하고, 평균적으로는 빅세타로 지칭함. 
  • 빅오 표기법은 n이 매우 클 때의 전체적인 큰 그림에 집중함. 

분할 상환 분석

시간, 메모리를 분석하는 알고리즘의 복잡도를 계산할 때, 알고리즘 전체를 보지 않고,

최악의 경우만을 살펴보는 것은 지나치게 비관적이라는 이유로 분할 상환 분석 방법이 등장함. 

  • i.g. 평소에는 빠른 알고리즘이 정말 가끔 발생하는 최악의 경우로 인해 상대적으로 실제 가치보다 저평가되는 알고리즘을 위한 표기법. 
  • e.g. 평소에는 O(1) 알고리즘을 지속적으로 가지다가 100번에 1번 정도만 O(n)을 가진다면..? 이 때도 빅오 표기법과 같이 O(n)으로 표기해야 하는가?

최악의 경우에 드는 비용을 최악의 경우가 발생하는 횟수로 나누어 계산. 

  • e.g. N번에 한 번 최악의 경우 O(n)이 나오는 알고리즘의 경우 
    • 빅오 표기로는 O(n)
    • 분할 상환 분석으로는 O(1)이 됨. 

병렬화

일부 알고리즘들은 병렬화로 실행 속도를 높일 수 있음. 

  • GPU는 병렬 연산을 위한 대표적인 장치, GPU 각각의 코어는 CPU보다 훨씬 더 느리지만, GPU의 코어는 수천여 개로 구성되어 있어, 많아 봐야 수십여 개에 불과한 CPU보다 수백 배 더 많은 연산을 동시에 수행할 수 있음. 
  • 최근 딥러닝 알고리즘을 비롯해 병렬 연산이 가능한 알고리즘이 큰 주목을 받고 있음. 
  • 알고리즘 자체의 시간 복잡도 외에도 알고리즘이 병렬화가 가능한지는 근래에 알고리즘의 우수성을 평가하는데 매우 중요한 척도 중 하나. 

자료형

파이썬 자료형

출처: 파이썬 알고리즘 인터뷰

1. 숫자

  • 파이썬에서의 숫자 정수형: int
    • 그렇다면 int 보다 더 큰 값은 어떤 자료형에 보관해야 할까? 파이썬에는 long이 없나?
    • 이를 위해 고정 정밀도 (Fixed-Precision) 정수형과 임의 정밀도 (Arbitrary-Precision) 정수형의 개념 공부!
  • 임의 정밀도 정수형이란?
    • 무제한 자릿수를 제공하는 정수형. 
    • 정수를 숫자의 배열로 간주. 즉, 자릿수 단위로 쪼개어 배열 형태로 표현. 

    e.g. 123456789101112131415 라는 큰 수를 파이썬에서 배열로 표현하는 방법

 

  • 고정 정밀도 정수형이란?
    • 고정된 자리수의 수를 나타내는 것
  • 기존 파이썬의 int는 C 스타일의 고정 정밀도 정수형이었고, long은 임의 정밀도 정수형임.
  • PEP 237을 통해 버전 2.4 부터는 int가 충분하지 않으면 자동으로 long 타입으로 변경되는 구조 -> 덕분에 오버플로 (Overflow)가 발생하는 일이 사라짐. 
  • 이후 버전 3부터는 아예 int 단일형으로 통합. int는 임의 정밀도를 지원하며, 더 이상 파이썬에서 고정 정밀도 정수형은 지원하지 않게 됨. 

 

  • bool 자료형
    • 논리 자료형, 파이썬에서는 내부적으로 1 (True), 0 (False) 로 처리되는 int의 서브 클래스. 
    • int 는 object의 하위 클래스이기도 하기 때문에 다음과 같은 구조를 띔.
object > int > bool

 

2. 매핑

매핑 타입 (Mapping type) 은 키와 자료형으로 구성된 복합 자료형. 

파이썬에 내장된 유일한 매핑 자료형은 바로 딕셔너리. (딕셔너리는 5장에서 설명)

 

3. 집합형

집합 자료형 set: 중복된 값을 갖지 않는 자료형.

  • 순서가 없는, 중복이 불가능한 collection 자료형.
  • mutable (가변성): 요소를 삭제하거나 변경할 수 있음. 
  • set은 입력 순서가 유지되지 않음. -> 따라서, indexing 이 불가 -> not iterable
  • set은 add (요소 1개 추가), update (여러 요소 추가), remove 메소드를 활용하여 요소를 추가/삭제함. 

4. 시퀀스

시퀀스 (Sequence): '수열' 같은 의미, 어떤 특정 대상의 순서 있는 나열.

  • e.g. str은 문자의 순서 있는 나열로 문자열을 이루는 자료형, list는 다양한 값들을 배열 형태의 순서 있는 나열로 구성하는 자료형. 
  • 시퀀스는 Immutable (불변)과 Mutable (가변) 으로 구분.
    • Immutable: 값을 변경할 수 없음, str, tuple, bytes -> 한번 이 타입으로 선언되는 값은 변경할 수 없음. 
      • '불변'한다는 의미는

  • a 변수에 할당된 str 이 변한 것이 아님. 이는 a 변수가 다른 str 타입인 def를 다시 참조했을 뿐, 실제로 abc, def 는 한번 생성된 후에 변경된 적이 없음. 

즉 a = 'abc'는 아래 이미지와 같고,

a = 'def'는 아래 이미지와 같음.

각자의 메모리 주소를 출력해보면 a 변수는 처음에는 abc를 참조했다가, 이후에는 def를 참조하도록 변경되었을 뿐. abc 자체 값이 변한 것 아님 => immutable.

 

str을 변경하려면, 참조하고 있는 str에 대해 다음과 같은 할당자가 처리되어야 하는데, 여기서는 오류가 발생함. 

  • 따라서, str은 변경할 수 없으며, 불변. 
  • list는 가변. -> 리스트는 자유롭게 값을 추가, 삭제할 수 있는 동적 배열. (5장에서 다룸)

원시 타입 & 객체

2개의 단락에 나눠, 원시 타입과 객체를 설명하고 있는데, 개인적으로 다시 정리함. 

1. 원시 타입과 참조 타입

Note) 파이썬에 한정된 이야기 아님! 프로그래밍 자료형!

자료형은 원시 타입과 참조 타입으로 구분할 수 있음.

1) 원시 타입 (Primitive Type)

2) 참조 타입 (Reference Type)

 

아주 간단하게, 수식을 표현함

변수 b에 변수 a를 할당할 때, b가 a를 복사함.

 

이 때, b가 a를 복사하는 것은 동일한데, (변수 a 의 타입에 따라서) 복사하는 값이 달라짐! 

 

복사하는 값 2가지 종류

1) 실체 값 전부 -> a가 원시 타입일 때

2) 값을 가리키고 있는 대상(주소) -> a가 참조 타입일 때

 

1) 실체 값 전부

실체 값 전부 (x가 원시 타입일 때), 출처: http://codingnuri.com/javascript-tutorial/javascript-primitive-types-and-reference-types.html

  • 실체 값 전부를 복사하는 것을 Call by Value 라고 함. 

2) 값을 가리키고 있는 대상

값을 가리키고 있는 대상 (x가 참조 타입일 때) 출처: http://codingnuri.com/javascript-tutorial/javascript-primitive-types-and-reference-types.html

  • 이 때, a 를 address, reference, pointer (포인터), object라고 부름. 
  • 또한 값을 가리키고 있는 대상을 복사하는 것을 Call by Address 라고 함. 

* Call by Value와 Call by Address의 장 단점 *

  Call by Value Call by Address
장점 1) 메모리 점유율이 적음.
2) 계산 속도 빠름.		 1) 원시 타입보다 여러 가지 작업을 수행할 수 있음.
- 문자로 변환
- 16진수로 변환
- 비트 조작 (Shifting)
단점 참조 타입보다 수행 가능한 기능이 떨어짐. 1) 메모리 점유율이 늘어남.
- 책 예시) 자바의 int 타입은 32비트인데 반해, JOL (Java Object Layout) 실행 결과의 객체인 Integer은 128비트임. 단순히 비교해도 4배의 공간을 더 차지함.
2) 계산 속도 감소.

 

* 프로그래밍 언어별 지원하는 자료형 타입 *

  우선순위 원시 타입 참조 타입 (객체)
자바 성능 O O
C 성능 O X (의문! C의 포인터는 참조 타입이 아닌가?)
파이썬 편리한 기능 제공 X O
  • 파이썬은 원시 타입을 사용하지 않고, 객체로 계산하기 때문에 속도가 느림. 
  • 같은 이유로, 자바를 원시 타입이 아닌 객체로 계산하게 되면 훨씬 느려지는데, 자바는 원시 타입도 함께 제공하기 때문에 속도를 위해서는 원시 타입으로 계산을 진행하여, C와 거의 유사한 수준으로 빠른 속도를 낼 수 있음. 
    • 마찬가지로, 파이썬의 NumPy 모듈은 빠른 속도로 유명한데, 넘파이는 C로 만든 모듈이며 내부적으로 리스트를 C의 원시 타입으로 처리하기 때문. 

2. 파이썬 with 객체 - 불변 객체와 가변 객체

파이썬은 모든 것이 객체임. 
즉, 파이썬에서 변수를 할당하는 작업은 해당 객체에 대해 참조 (Reference)를 한다는 의미.

파이썬의 객체는 불변 객체와 가변 객체로 구분됨. 

 

1) 불변 객체 (Immutable Object)

2) 가변 객체 (Mutable Object)

 

1) 불변 객체

  • 생성 후, 그 상태를 바꿀 수 없는 객체
  • 파이썬에서는 int, str, tuple이 모두 불변 객체임. 
  • 즉, 값을 담고 있는 변수는 참조일 뿐이고, 실제로 값을 갖고 있는 int와 str은 모두 불변 객체임. 한번 값을 담아두면, 더 이상 값을 변경할 수 없음.

  • e.g.) str을 변경하려면, 참조하고 있는 str에 대해 다음과 같은 할당자가 처리되어야 하는데, 여기서는 오류가 발생함.

  • 따라서, str은 변경할 수 없으며, 불변. 

2) 가변 객체

  • 값이 바뀔 수 있음.
  • 즉, 다른 변수가 참조하고 있을 때, 그 변수의 값 또한 변경됨. 

is 와 ==

파이썬의 비교 연산자 중 is 와 == 이 있음. 

  • is
    • is 는 id() 값을 비교하는 함수
    • None은 널(null)로서 값 자체가 정의되어 있지 않으므로, == 로는 비교 불가능, is 로 비교 가능. 
  • == 
    • 값을 비교하는 연산자

3. 자료구조와 추상 자료형, 알고리즘

자료구조와 알고리즘

컴퓨터가 기본적으로 하는 일은 '데이터 저장'과 '데이터 연산'임.

  • 데이터 저장 -> 자료구조
  • 데이터 연산 -> 알고리즘

자료구조

  • 사전적 의미) 데이터 단위와 데이터 자체 사이의 물리적, 논리적인 관계
  • 즉, 데이터를 '저장' 하는 방법

알고리즘

  • 사전적 의미) 문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합
  • 즉, 데이터를 '연산'하기 위한 방법

자주 사용하는 비유

도서관에 비유)
자료구조: 도서관의 책장에 책을 꼽는 것으로 가정을 한다면, 도서관에 존재하는 책들은 일정한 규칙을 통해 책장에 정리될 수 있음. 예를 들어 ABC 순서, 연도 순서에 따라 책을 진열할 수 있고, 이렇게 데이터가 저장되는 형태, 즉 데이터 표현 및 저장 방식을 자료구조라고 함. 

알고리즘: 도서관에 책이 앞서 자료구조의 방식대로 진열되어 있다면, 알고리즘은 그 책을 찾는 것에 비유할 수 있음. 자신이 원하는 책을 찾을 때, 책장의 왼쪽, 오른쪽, 위쪽, 아래쪽으로 책을 찾을 수 있으며, 큰 책, 작은 책으로 검색이 가능하며 혹은 무작위로도 책을 찾을 수 있음. 이렇게 저장된 데이터를 명령 처리 및 제어하는 방법을 알고리즘이라고 함. 

자료구조와 추상 자료형

추상 자료형 (Abstract Data Type)

  • 기능의 구현 부분은 나타내지 않고, 데이터의 형태와 그 데이터의 연산들을 정의한 것
  • 구현 방법을 명시하고 있지 않음. 
  • 객체지향의 클래스(Class), 또는 사용설명서 (User's Guide) 와 유사

자료구조 (Data Structure)

  • 추상 자료형이 정의한 연산들을 구현한 구현체
  • 구현 방법을 명시함.
e.g.)
스택 (stack) 의 형태는 LIFO 값들의 모임이고 push, pop, size 등의 연산을 정의할 수 있음. -> 추상 자료형
스택이 내부적으로 배열로 구현되는지, 연결 리스트로 구현되는지, 또는 size 연산을 수행할 때 원소의 개수를 일일이 세는지, 혹은 개수를 따로 저장해 두는지와 같은 세부 사항 -> 자료구조