728x90
리스트
언어 | 동적배열 |
파이썬 | list() |
C++ | std::vector |
자바 | ArrayList |
순서대로 저장하는 시퀀스이자 변경 가능한 목록, 입력 순서가 유지되며 내부적으로 동적 배열로 구현되어 있다.
- 파이썬 리스트는 다양한 기능 제공하고 O(1)에 실행 가능한 연산들도 몇 가지 있다. 리스트 마지막에 요소를 .append()로 추가, pop()으로 추출, 인덱스의 요소 조회는 모두 O(1)이다. 다음 표는 리스트의 주요 연산 및 시간 복잡도이다.
연산 | 시간 복잡도 | 설명 |
len(a) | O(1) | 전체 요소 개수 리턴한다 |
a[i] | O(1) | 인덱스의 i 요소를 가져온다 |
a[i:j] | O(K) | i부터 j까지 슬라이스 길이만큼의 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)이다 |
del a[i] | O(n) | i에 따라 다르고 최악의 경우 O(n) |
a.sort() | O(nlogn) | 정렬, 최선의 경우 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]
a.append('안녕') # 문자도 가능하다
a # [1,2,3,4,'안녕']
- insert() 함수를 사용해 특정 위치의 인덱스를 지정해 요소 추가 할 수 있다.
a.insert(3,5)
a # [1,2,3,5,4]
- 슬라이싱 기능을 이용해 특정 범위 내의 값을 매우 편리하게 가져 올 수 있다.
a[1:3] # [2,3]
- 존재하지 않는 인덱스 조회할 경우 IndexError가 발생 할 수 있고 try 구문을 이용해 에러에 대한 예외 처리를 할 수 있다.
try:
print(a[9])
except IndexError:
print("존재하지 않는 인덱스")
리스트의 특징
- 파이썬 리스트같은 경우 연속된 공간에 요소를 배치하는 배열 의 장점, 다양한 타입을 연결해 배치하는 연결 리스트 의 장점을 모두 취한 형태를 띠고있다.
- 또한, 리스트는 객체로 되어 있는 모든 자료형을 다음과 같이 포인터로 연결한다.
- 파이썬은 모든 것이 객체며, 리스트는 이들 객체에 대한 포인터 목록으로 관리하는 형태로 되어 있다.
- 파이썬의 리스트는 연결 리스트에 대한 포인터 목록을 관리하기에 정수 뿐만 아니라 문자, 불리언 등 제각기 다양한 타입을 단일 리스트에서 관리하는게 가능하다.
- 하지만, 각 자료형의 크기는 서로 다르기에 연속된 메모리 공간에 할당하는 것은 불가능하다.
- 이러한 문제점으로 인덱스를 조회하는데에도 모든 포인터의 위치를 찾아가서 타입 코드를 확인해야 하므로 속도 측면에서 불리한 점이 있다.
딕셔너리
언어 | 동적배열 |
파이썬 | dict() |
C++ | std::unordered_map |
자바 | HashMap |
입력 순서가 유지되고 내부적으로 해시테이블이 구현되어있는 키/값 구조로 이루어진 딕셔너리를 말한다.
- 딕셔너리는 해시 할 수 있다면 숫자, 문자 ,집합까지 불변 객체를 모두 키로 사용할 수 있다. 이 과정을 해싱, 해시 테이블을 이용해 자료를 저장한다.
연산 | 시간 복잡도 | 설명 |
len(a) | O(1) | 요소의 개수 리턴한다 |
a[key] | O(1) | 키를 조회하여 값을 리턴한다 |
a[key] = value | O(1) | 키/값을 삽입한다 |
key in a | O(1) | 딕셔너리에 키가 존재하는지 확인한다 |
- 딕셔너리는 대부분 연산이 O(1)에 처리 가능한 매우 우수한 자료형이다, 키/값 구조의 데이터를 저장하는 유용한 자료형.
딕셔너리의 활용 방법
a = dict() # 선언 방법
a = {} # 좀 더 간단하게 선언
- 다음과 같이 key1, key2는 초기값으로 지정해 선언하거나 key3처럼 나중에 별도로 선언하여 value3라는 값을 할당할 수 있다.
a = {'key1': 'value1', 'key2': 'value2'}
a # {'key1': 'value1', 'key2': 'value2'}
a['key3'] = 'value3'
a # {'key1': 'value1', 'key2': 'value2', 'key3 : 'value3'}
- 딕셔너리의 키를 지정하면 값을 조회할 수 있다. 하지만 존재하지 않는 인덱스를 조회할 경우 IndexError가 발생하며 try구문으로 예외 처리를 할 수 있다.
try:
print(a['key4'])
except KeyError:
print('존재하지 않는 키')
- 딕셔너리에 있는 키/값은 for 반복문으로도 조회가 가능하고 items() 메소드를 사용하면 키/값을 각각 꺼내올 수 있다
for k, v in a.items():
print(k,v)
# key1 value1
# key2 value2
# key3 value3
딕셔너리 모듈
defaultdict 객체
- 존재하지 않는 키를 조회할 경우, 에러 메시지를 출력하는 대신 디폴트 값을 기준으로 해당 키에 대한 딕셔너리에 대한 아이템을 생성해준다.
- 마찬가지로 실제로는 collections.defaultdict 클래스를 갖는다.
a = collections.defaultdict(int)
a['A'] = 5
a['B'] = 4
a
# defaultdict(<class 'int'>, {'A': 5, 'B': 5})
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})
- 개수를 자동으로 계산해주기 때문에 매우 편리하며, most_common()을 사용하여 가장 빈도 수가 높은 요소를 추출할 수 있다.
b.most_common(2)
# [(5,3), (6,2)]
OrderedDict 객체
- OrderedDict를 이용해 입력 그대로 순서가 유지되게 할 수 있다.
- 하지만, 파이썬 3.7부터 딕셔너리는 내부적으로 인덱스를 이용하며 입력 순서가 유지되도록 개선됐다.
'알고리즘 공부 > 파이썬 알고리즘 인터뷰' 카테고리의 다른 글
파이썬 알고리즘 인터뷰 - 배열, 투 포인터 기법, 최댓값과 최솟값 (0) | 2022.01.30 |
---|---|
파이썬 알고리즘 인터뷰 - 문자열 조작 (0) | 2022.01.30 |
파이썬 알고리즘 인터뷰 - 자료형 (0) | 2022.01.22 |
파이썬 알고리즘 인터뷰를 통한 팁 (0) | 2022.01.20 |
04 가장 흔한 단어(Most common words) (2) | 2022.01.10 |