자료구조와 알고리즘을 공부하기 위해 보고있는 책 파이썬알고리즘인터뷰에서 파이썬 문법이나 구조에 대해 다시 한번 정리해주는 파트가 있어서 다시 한번 공부를 했다. 그 중에서 다시 한번 기억해야 할 부분이나 알고 있어야 하는 부분에 대해서 정리를 하려 한다.
자료형
파이썬 자료형
숫자
파이썬에서는 숫자 정수형으로 int 만을 제공한다. int 는 임의 정밀도를 지원하며, 더 이상 파이썬에서 고정 정밀도 정수형은 지원하지 않는다.
임의 정밀도 정수형은 무제한 자릿수를 제공하는 정수형을 말한다. 숫자를 임의 정밀도로 처리하면 계산속도가 저하된다. 그러나 숫자를 단일형으로 처리할 수 있어서 언어를 매우 단순한 구조로 만들 수 있을 뿐 아니라, 언어를 사용하는 입장에서도 더 이상 오버플로를 고민할 필요가 없어 잘못된 계산 오류를 방지할 수 있다.
bool 은 엄밀히 따지면 논리 자료형이지만 파이썬에서는 내부적으로 1(TRUE), 0(FALSE) 로 처리되는 int 의 서브 클래스이다. int는 object 의 하위 클래스이기도 하기 때문에 object > int > bool 과 같은 구조를 띈다.
>>> True == 1
TRUE
>>> False == 0
TRUE
# 논리 자료형은 내부적으로 정수값을 갖고 있기 때문에 성립매핑
매핑Mapping 타입은 키와 자료형으로 구성된 복합 자료형. 파이썬에서는 유일한 매핑 자료형으로 딕셔너리가 있다.
집합
집합 자료형은 set 은 중복된 값을 갖지 않는 자료형이다.
시퀀스
시퀀스Sequence는 우리말로 하면 '수열' 같은 의미. 어떤 특정 대상의 순서있는 나열을 말한다. 배열이 없는 파이썬에서는 list라는 시퀀스 타입이 배열의 역할을 수행한다.
원시 타입
원시타입은 메모리에 정확하게 타입 크기만큼의 공간을 할당하고 그 공간을 오로지 값으로 채워넣는다.
파이썬은 원시 타입을 지원하지 않는다. 애초에 편리한 기능 제공에 우선순위를 둔 언어이기 때문에 느린 속도와 더 많은 메모리를 차지하더라도 훨씬 더 다양한 기능을 제공할 수 있는 객체에 관심을 둔다. 파이썬은 원시 타입의 속도를 포기하는 대신 객체의 다양한 기능과 편의성을 택했다.
| 언어 | 지원 타입 형태 |
|---|---|
| C | 원시 타입 |
| 자바 | 원시 타입, 객체 |
| 파이썬 | 객체 |
객체
파이썬은 모든 것이 객체이다.
⭐️ 파이썬 자료형의 불변 객체 여부 ⭐️
| 클래스 | 설명 | 불변 객체 |
|---|---|---|
| bool | 부울 | O |
| int | 정수 | O |
| float | 실수 | O |
| list | 리스트 | X |
| tuple | 리스트와 튜플의 차이는 불변여부. 이외에는 거의 동일. 튜플은 불변이므로 생성할 때 설정한 값 변경 X | O |
| str | 문자 | O |
| set | 중복된 값을 갖지 않는 집합 자료형 | X |
| dict | 딕셔너리 | X |
불변 객체
파이썬에서 변수를 할당하는 작업은 해당 객체에 대해 참조를 한다는 의미. 값을 담고 있는 변수는 사실은 참조일 뿐이고 실제로 값을 갖고 있는 int 와 str 은 모두 불변 객체이다. 불변 객체로는 tuple 도 있다. tuple 은 값이 변하지 않기 때문에 dict의 키나 set의 값으로도 사용할 수 있다. ❗️ list는 언제든 값이 변할 수 있어서 dict의 키로 정하거나 set의 값으로는 추가할 수 없다.
⭐️ is 와 == ⭐️
is는 id()값을 비교하는 함수이다. None은 널(Null)이라서 값 자체가 정의되어 있지 않아서 ==로는 비교 불가능하다.
>>> a = [1,2,3]
>>> a == a
True
>>> a == list(a)
True
>>> a is a
True
>>> a is list(a)
False값은 동일하지만 list()로 한 번 더 묶어주면 별도의 객체로 복사가 되고 다른 ID를 갖게 된다. 따라서 is는 False가 된다.
⭐️ 자료구조, 자료형, 추상 자료형 ⭐️
<자료구조>
컴퓨터과학에서는 데이터에 효율적으로 접근하고 조작하기 위한 데이터의 조직, 관리, 저장구조를 말한다. 학문으로서의 자료구조를 뜻함. 일반적으로 원시자료형을 기반으로 하는 배열, 연결리스트, 객체 등을 말한다.
<자료형>
컴파일러 또는 인터프리터에게 프로그래머가 데이터를 어떻게 사용하는지를 알려주는 일종의 데이터 속성이다. 특정언어에서 자료형이라 함은 정수, 실수, 문자열 등 해당 언어에서 지원하는 원시 자료형까지 포함하는 모든 자료의 유형을 말한다.
<추상 자료형>
일반적으로 줄여서 ADT라고 함. 해당 유형의 자료에 대한 연산들을 명기한 것. 행동만을 정의할 뿐 실제 구현방법은 명시하지 않는다. OOP(객체지향프로그래밍)의 추상화와 비슷한 개념.
리스트
말 그래도 순서대로 저장하는 시퀀스이자 변경 가능한 목록. 입력순서가 유지되며, 내부적으로는 동적 배열로 구현되어 있음.
파이썬 리스트의 가장 좋은 점은 매우 다양한 기능을 제공한다는 점. 리스트를 사용하면 스택을 사용할지, 큐를 사용할지 고민하지 않아도 된다. 스택과 큐에서 사용 가능한 모든 연산을 함께 제공.
⭐️ 리스트의 주요 연산 시간 복잡도 ⭐️
| 연산 | 시간복잡도 | 설명 |
|---|---|---|
| len(a) | O(1) | 전체 요소의 개수 리턴 |
| a[i] | O(1) | 인덱스 i의 요소를 가져옴 |
| a[i:j] | O(k) | i부터 j까지 슬라이스의 길이만큼의 k개의 요소를 가져옴. 객체 k개에 대한 조회가 필요하므로 O(k)이다. |
| elem in a | O(n) | elem 요소가 존재하는지 확인. 처음부터 순차탐색하므로 n만큼 시간이 소요됨 |
| a.count(elem) | O(n) | elem 요소의 개수 리턴 |
| a.index(elem) | O(n) | elem 요소의 인덱스 리턴 |
| a.append(elem) | O(1) | 리스트 마지막에 elem 요소 추가 |
| a.pop() | O(1) | 리스트 마지막 요소 추출. 스택의 연산이다 |
| a.pop(0) | O(n) | 리스트 첫번째 요소 추출. 큐의 연산이다. 전체 복사가 필요하므로 O(n)이다. 큐의 연산을 주로 사용한다면 리스트보다는 O(1)에 가능한 데크(deque) 권장 |
| del a[i] | O(n) | i에 따라 다름. 최악의 경우 O(n)이다 |
| a.sort() | O(n log n) | 정렬한다. 팀소트(Timsort)를 사용. 최선의 경우 O(n)에도 실행될 수 있다 |
| min(a), max(a) | O(n) | 최소값/최대값을 계산하기 위해서는 전체를 선형탐색해야함 |
| a.reverse() | O(n) | 뒤집는다. 리스트는 입력순서가 유지되므로 뒤집게되면 입력순서가 반대로 된다. |
❗️ 리스트의 경우 탐색시 값의 존재유무를 확인하려면 정렬된 경우에는 이진검색이 효율적. 그러나 매번 정렬이 필요하고 대개는 리스트가 정렬된 상태가 아니기 때문에, 리스트의 경우에는 모든 엘리먼트를 순차적으로 조회하는 형태로 구현되어 있다. 최악의 경우 항상 O(n)이 소요된다.
딕셔너리
내부적으로는 해시 테이블로 구현되어 있다. 해시할 수만 있다면 숫자뿐 아니라 문자, 집합까지 불변객체를 모두 키로 사용할 수 있다. 이 과정을 해싱이라고 하며, 해시 테이블을 이용해 자료를 저장한다. 무엇보다 해시테이블은 다양한 타입을 키로 지원하면서도 입력과 조회 모두 O(1)에 가능하다. 최악의 경우 O(n)이 될 수 있으나 대부분 훨씬 더 빨리 실행된다. 분할상환분석에 따른 시간 복잡도는 O(1)이다.
⭐️ 딕셔너리의 주요 연산 시간 복잡도 ⭐️
| 연산 | 시간복잡도 | 설명 |
|---|---|---|
| len(a) | O(1) | 요소의 개수 리턴 |
| a[key] | O(1) | 키를 조회하며 값을 리턴 |
| a[key] = value | O(1) | 키/값을 삽입 |
| key in a | O(1) | 딕셔너리에 키가 존재하는지 확인 |
딕셔너리 모듈
defaultdict 객체
import collections
a = collections.defaultdict(int)
a['A'] = 5
a['B'] = 4
-> a 값을 출력하면
-> defaultdict(<class 'int'>, {'A': 5, 'B': 4})
a['C'] += 1 # 존재하지 않는 키인 C를 조회
-> a 값을 출력하면
-> defaultdict(<class 'int'>, {'A': 5, 'B': 4, 'C': 1})
# 원래의 딕셔너리라면 KeyError 발생. defualtdict 객체는 에러없이 바로 +1 연산이 가능하고 디폴트인 0을 기준으로 자동 생성 후 1을 더해 최종적으로 1이 만들어짐Counter 객체
아이템에 대한 개수를 계산해 딕셔너리로 리턴.
a = [1,2,3,4,5,5,5,6,6]
b = collections.Counter(a)
-> b를 출력하면
-> Counter({5: 3, 6: 2, 1: 1, 2: 1, 3: 1, 4: 1})
# 키에는 아이템 값, 값에는 해당 아이템의 개수가 들어간 딕셔너리 생성
b.most_common(2) # 가장 빈도수가 높은 2개의 요소 추출
-> [(5, 3), (6, 2)]
<참조문헌>
박상길, '파이썬알고리즘인터뷰', 책만, 2020
