리스트와 딕셔너리는 파이썬을 사용하다 보면 가장 빈번하게 접하게 되는 자료형이다
코딩 테스트 같은 문제 풀이 뿐만 아니라
pandas 같은 DataFrame의 형태도 리스트와 딕셔너리를 기반으로 돌아간다.
따라서 리스트와 딕셔너리의 기본 구조와 문법에 대해서 다시 한 번 숙지하려고 한다.
리스트
파이썬의 리스트(List)는 말 그대로 순서대로 저장하는 시퀀스이자 변경 가능한 목록을 말한다.
입력 순서가 유지되며, 내부적으로는 동적 배열로 구현되어 있다.
파이썬 리스트의 가장 좋은 점은 매우 다양한 기능을 제공한다는 점으로
리스트를 사용하면 사실상 스택을 사용할지 큐를 사용할지 고민하지 않아도 되며
스택과 큐에서 사용 가능한 모든 연산을 함께 제공한다.
※ 스택 : 한 쪽의 끝에서만 자료를 넣고 뺄 수 있는 LIFO (Last In First Out) 구조
가장 최근에 추가한 자료가 가장 먼저 제거되는 구조이다.
※ 큐 : 스택과 유사하지만 가정 먼저 추가한 자료가 가장 먼저 제거되는 FIFO (First In First Out) 구조
리스트는 이처럼 다양한 기능을 제공하면서도 시간복잡도 O(1) 에 실행 가능한 연산들도 몇 가지 있다.
문법 : 시간복잡도 : 의미
len(a) : O(1) : 전체 요소의 개수를 리턴한다
a[i] : O(1) : 인덱스 i의 요소를 가져온다.
a.append(elem) : O(1) : 리스트의 마지막에 elem을 추가한다.
a.pop() : O(1) : 리스트의 마지막 요소를 추출. 스택 연산
추가적인 연산들
a[i:j] : O(k) : 인덱스 i부터 j-1까지 슬라이스의 길이만큼인 k개의 요소를 가져온다.
이 경우 객체 k개에 대한 조회가 필요하므로 O(k)이다.
elem in a : O(n) : elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 n만큼 시간이 소요
a.count(elem) : O(n) : elem 요소의 개수를 리턴
a.index(elem) : O(n) : elem 요소의 index를 리턴
a.pop(0) : O(n) : 리스트 첫 번째 요소를 추출한다. 큐의 연산 이 경우 전체 복사가 필요하기 때문에 O(n)이다.
del a[i] : O(n) : 인덱스 i의 요소를 제거한다.
a.sort() : O(n log n) : 정렬한다. 팀소트(Timsort)를 사용하며, 최선의 경우 O(n)에도 실행될 수 있다.
min(a), max(a) : O(n) : 최솟값/최댓값을 계산하기 위해서는 전체를 선형 탐색해야 한다.
a.reverse() : O(n) : 뒤집는다. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 된다
리스트는 아래와 같이 선언할 수 있다.
a = list()
a = []
# 초깃값 지정과 추가
다음과 같이 초깃값을 지정해 선언하거나 append()로 추가할 수 있다.
a = [1, 2, 3]
a : [1, 2, 3]
a.append(4)
a : [1, 2, 3, 4]
※ 콜론(:) 뒤에 나오는 값은 결과 값이다.
# insert
insert() 함수를 사용하면 특정 위치의 인덱스를 지정해 요소를 추가할 수 있다.
인덱스는 0부터 시작한다.
a.insert(인덱스, 값)
a.insert(3, 5)
a : [1, 2, 3, 5, 4]
파이썬의 리스트는 숫자 외에도 다양한 자료형을 단일 리스트에 관리할 수 있어 편하다.
숫자외에도 문자와 boolean 등을 자유롭게 삽입할 수 있다.
다른 언어들은 동적 배열에 삽입할 수 있는 자료형을 동일한 타입으로 제한하는 경우가 많은 데 비해,
파이썬은 이처럼 자유롭게 삽입할 수 있다. 이 경우 다른 언어들은 타입을 변환한다든지 등의 별도의 부가 처리를
해줘야 하지만, 파이썬은 이런 부분에 신경쓰지 않고 유연하게 활용할 수 있다.
(사실 컴공 전공생이 아닌지라 Python만 좀 주력으로 다룰 줄 알고
C와 Java 등은 맛보기 정도만 아는 편인데
C와 Java 의 분명한 강점이 있음에도 불구하고 Python을 사용하다보면 " 이게 안돼 ? " 싶은 부분들이 있는 것은 어쩔 수 없는 것 같다.)
# 슬라이싱
파이썬 리스트에는 슬라이싱 기능이 있어 특정 범위 내의 값을 매우 편리하게 가져올 수 있다.
a[시작인덱스 : 끝인덱스 : 간격]
a[1:3] : [2, 3]
리스트는 앞서 설명했듯이 0부터 시작하고
끝인덱스 - 1 까지의 값만 가져오는 것이 슬라이싱의 특징이다.
a = [1, 2, 3, 5, 4] 였기 때문에 [2, 3]이 리턴된다.
세 번째의 간격 파라미터를 부여하면 단계의 의미로
a[1:4:2] 같이 지정할 경우 두 칸씩 건너뛰게 된다.
존재하지 않는 인덱스를 조회할 경우 IndexError가 발생한다.
a[9]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError : list index out of range
이럴 경우 try 구문으로 예외 처리가 가능하다
try:
print(a[9])
except IndexError:
print("존재하지 않는 인덱스")
리스트에서 요소를 제거하는 방법은 크게 2가지가 있다.
- 인덱스로 삭제하기
- 값으로 삭제하기
# del 함수 사용
del 는 인덱스를 사용해 값을 제거하는 방법으로 예시는 다음과 같다.
a : [1, 2, 3, 5, 4]
del a[1] : 1번 인덱스 제거
a : [1, 3, 5, 4]
# remove 함수 사용
remove 는 값에 해당하는 요소를 삭제할 수 있다.
a : [1, 2, 3, 5, 4]
a.remove(1)
a : [2, 3, 5, 4]
제거하려는 값이 2개 이상 있을 경우 처음으로 마주치는 값만 제거한다.
# pop 사용
pop 함수를 사용하면 스택의 pop 연산처럼 추출로 처리된다.
즉, 삭제할 값을 리턴한 후에 삭제가 진행된다.
a : [1, 2, 3, 5, 4]
a.pop(3) # () 안은 인덱스 번호
5 # 리턴한 결과
a : [1, 2, 3, 4]
암기식으로 문법을 외우거나
문법을 자주 사용하지 않다보면 간혹가다 까먹는 경우가 많다.
따라서 처음부터 원리를 이해하고 까먹지 않게 자주 사용해주는 것이 매우 좋다.
리스트의 특징
리스트는 연속된 공간에 요소를 배치하는 배열의 장점과 다양한 타입을 연결해 배치하는 연결 리스트의 장점을 모두 취한듯한 형태를 띠며, 리스트를 잘 사용하기만 해도 배열과 연결 리스트가 모두 필요 없을 정도로 강력하다.
때문에 파이썬은 아예 원시 타입 자료형은 제공하지도 않는다.
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
위는 CPython에서 리스트를 정의한 헤더 파일의 일부이며
CPython 에서 리스트는 요소에 대한 포인터 목록(ob_item)을 갖고 있는 구조체로 선언되어 있다.
리스트에 요소를 추가하거나 조작하면 ob_item의 사이즈를 조절해 나가는 형태로 구현되어 있다.
파이썬의 모든 자료형은 C처럼 원시 타입이 아닌 객체로 되어 있다.
리스트는 객체로 되어 있는 모든 자료형을 포인터로 연결한다.
파이썬은 모든 것이 객체며, 파이썬의 리스트는 이들 객체에 대한 포인터 목록을 관리하는 형태로 구현되어 있다.
일반적으로 정수형 배열이라고 하면 정수로만 이뤄진 값을 연속된 메모리 공간에 저장하는 경우를 말하며
정수가 아닌 값은 저장할 수 없지만
파이썬의 리스트는 연결 리스트에 대한 포인터 목록을 관리하기 때문에
정수, 문자, 불리언 등 제각기 다양한 타입을 동시에 단일 리스트에서 관리하는 것이 가능하다.
이러한 특징들은 쉽고 간편하게 사용할 수 있으나
각 자료형들의 크기는 저마다 서로 다르기 때문에 이들은 연속된 메모리 공간에 할당하는 것이 불가능하고
결국 각각의 객체에 대한 참조로 구현할 수밖에 없다.
당연히 인덱스를 조회하는 데에도 모든 포인터의 위치를 찾아가서 타입 코드를 확인하고
값을 일일이 살펴봐야 하는 등 추가적인 작업이 필요하기 때문에,
속도 면에서도 훨씬 더 불리하다.
'알고리즘' 카테고리의 다른 글
| [Python] 딕셔너리 (0) | 2022.11.22 |
|---|
