파이썬 알고리즘 인터뷰 | 5장. 리스트, 딕셔너리

리스트

말 그래도 순서대로 저장하는 시퀀스이자 변경가능한 목록

입력 순서가 유지되며 내부적으로는 동적 배열로 구현

연속된 공간에 요소를 배치하는 배열의 장점과 다양한 타입을 연결해 배치하는 연결 리스트의 장점을 모두 취한 듯한 형태를 띠며, 실제로 리스트를 잘 사용하기만 해도 배열과 연결 리스트가 모두 필요 없을 정도로 강력하다.

 

주요 연산

연산	설명	시간복잡도
append("a")	리스트에 원소를 하나 삽입할 때 사용	O(1)
sort(a)	오름차순 정렬 / 내림차순 정렬	O(NlogN)
reverse()	리스트의 원소의 순서를 모두 뒤집어 놓음	O(N)
insert(삽입할 위치 인덱스, 삽입할 값)	특정한 인덱스 위치에 원소를 삽입할 때 사용	O(N)
count(a)	리스트에서 특정한 값을 가지는 데이터의 개수를 셀 때 사용	O(N)
remove("a")	특정한 값을 갖는 원소를 제거하는데, 값을 가진 원소가 여러 개면 하나만 제거	O(N)
pop()	리스트의 맨 마지막 요소를 리턴하고 그 요소는 삭제한다(스택의 연산)	O(1)
len(a)	전체 요소의 개수를 리턴	O(1)
elem in a	elem 요소가 있는지 확인한다.	O(n)
min(a), max(a)	최솟값 최대값	O(n)
a[i:j]	i부터 j-1까지 슬라이스, 그 길이 k 만큼의 요소를 가져옴	O(k)

딕셔너리

키/값 구조로 이뤄진 딕셔너리를 말한다.

입력 순서가 유지되며 내부적으로는 해시 테이블로 구현되어 있다.

문자를 포함해 다양한 타입을 키로 사용할 수 있다.

해시할 수만 있다면 숫자뿐만 아니라, 문자, 집합까지 불변 객체를 모두 키로 사용할 수 있다.

이 과정을 해싱이라고 하며, 해시 테이블을 이용해 자료를 저장한다.

무엇보다 해시 테이블은 다양한 타입을 키로 지원하면서도 입력과 조회 모두 O(1)에 가능하다.

키/값 구조의 데이터를 저장하는 유용한 자료형으로서, 코딩 테스트에서도 리스트만큼이나 매우 빈번하게 활용된다.

파이썬 3.6 이하에서는 입력 순서가 유지되지 않아 collections.OrderedDick()라는 별도 자료형을 제공

주요 연산

연산	설명	시간복잡도
len(a)	요소의 개수 리턴	O(1)
a[key]	키를 조회하여 값을 리턴	O(1)
a[key]=value	키/값을 삽입	O(1)
key in a	딕셔너리에 키가 존재하는지 확인	O(1)

딕셔너리에 있는 키/값을 조회하는 방법

for k,v in a.items():
	print(k,v)

딕셔너리 모듈

defauldict

존재하지 않는 키를 조회할 경우, 에러 메시지를 출력하는 대신 디폴트 값을 기준으로 해당 키에 대한 딕셔너리 아이템을 생성해 줌 

a = collections.defaultdict(int)
a['A'] = 5
a['C'] += 1
a = defaultdict(<class 'int'>,{ 'A':5, 'C':1 }

위와 같이 존재하지 않는 키를 +1 연산으로 키/값을 에러 없이 추가할 수 있다

 

Counter 객체

아이템에 대한 개수를 계산해 딕셔너리로 리턴함

아이템 값:아이템의 개수 형태의 딕셔너리를 생성한다.

collections.Counter 클래스를 갖는다.

가장 빈도 수가 높은 n개의 요소는 most_common(n)으로 추출한다.

 

collections.OrderedDick

3.7이상부터는 사실상 내부적으로 인덱스를 사용하며 순서가 유지되므로 하위 호환성을 위한 기능이니 참고하자