[파이썬 알고리즘 인터뷰] 2부 5장 리스트, 딕셔너리

리스트

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

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

 

- 매우 다양한 기능 제공

- 리스트를 사용하면 스택과 큐의 사용 유무를 고민하지 않아도 됨

- 스택과 큐에서 사용 가능한 모든 연산 제공

 

O(1)에 실행 가능한 연산들

- 리스트 마지막 요소를 .append( )로 추가,

- 리스트의 마지막 요소를 pop( )으로 추출,

- 원하는 인덱스 조회하는 연산

 

( * 요소를 삭제하거나 큐의 연산이기도 한 첫 번째 요소를 추출하는 pop(1)은 O(n)에 해당 )

- 리스트에 큐의 연산을 사용할 때는 주의가 필요함

- 데크(Deque)와 같은 자료형으로 성능을 높일 수 있음

 

리스트의 주요 연산 시간 복잡도

연산	시간복잡도	설명
len(a)	O(1)	전체 요소의 개수 리턴
a[ i ]	O(1)	인덱스 i의 요소를 가져옴
a[ i : j ]	O(k)	인덱스 i부터 j-1까지 슬라이스의 길이만큼인 k개의 요소를 가져옴 (이 경우 객체 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)	정렬한다. 팀소트를 사용, 최선의 경우 O(n)에도 실행될 수 있음
min(a), max(a)	O(n)	최솟값 / 최댓값을 계산하기 위해서는 전체를 선형 탐색해야 함
a.reverse( )	O(n)	뒤집음. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 됨

- 리스트의 경우 탐색 시 값의 존재 유무를 확인하려면 정렬된 경우, 이진 탐색이 효율적

- 대체로 정렬된 상태가 아니기 때문에, 리스트의 경우 모든 엘리먼트를 순차적으로 조회하는 형태로 구현

- 최악의 경우 항상 O(n)이 소요됨

리스트 활용 방법

- 리스트 선언

 

a = list()

a = []

 

- 리스트 초깃값 지정과 append( )를 이용한 추가

- 파이썬은 자료형 타입을 신경쓰지 않고 자유롭게 삽입이 가능함

 

a = [1, 2, 3]
a.append(4)

>>> [1, 2, 3, 4]

# 숫자 이외의 다양한 자료형 삽입
a.append('안녕')
a.append(True)

 

- 특정 위치의 인덱스를 지정해 요소 추가

 

// 3번째 인덱스에 5를 삽입

a.insert(3, 5)
>>> [1, 2, 3, 5, 4]

 

- 슬라이싱

- 특정 범위 내의 값 가져오기

- 슬라이싱은 문자열에 유용하게 활용되는 기능

 

a = [1, 2, 3, 4, 5]

# 인덱스1에서 인덱스3 이전까지의 값 가져오기
a[1:3]
>> [2, 3]

# 처음부터 값을 가져옴
a[:3]
>> [1, 2, 3]

#(종료 인덱스 생략도 가능)
a[4:]
>> [5]

# 인덱스 1, 2, 3의 값
a[1:4]

# 인덱스 1, 3의 값
# 세 번째 파라미터, 단계를 지정할 수 있음
# 아래 예시는 2칸씩 건너뛰게 됨
# 1에서 시작해 1에서 두 칸 건너뛴 3까지의 값을 가졍ㅁ

a[1:4:2]

 

IndexError 발생시 try 구문으로 에러에 대한 예외처리

 

try:
	print(a[9])
except IndexError:
	print("존재하지 않는 인덱스")

 

- 리스트 요소 삭제

- 인덱스로 삭제

- 값으로 삭제

 

# del 키워드 사용

a = [1, 2, 3, 4, 5]

del a[0]
>> [2, 3, 4, 5]

# remove( ) 함수 사용

a.remove(5)
>> [2, 3, 4]

# pop( ) 함수 사용
a.pop(1)
>> [2, 4]

리스트 특징

- 연속된 공간에 요소를 배치하는 배열의 장점과 다양한 타입을 연결해 배치하는 연결 리스트의 장점을 모두 취한 듯한 형태

- 파이썬의 모든 자료형은 원시 타입이 아닌 객체로 되어 있음

- 정수, 문자, 불리언 등 제각기 다양한 타입을 동시에 단일 리스트에서 관리하는게 가능함

 

- 각 자료형의 크기는 저마다 서로 다르기 때문에 연속된 메모리 공간에 할당하는 것은 불가능

- 각각의 객체에 대한 참조로 구현

 

- 때문에 인덱스를 조회하는 데에도 모든 포인터의 위치를 찾아가서 타입 코드를 확인하고 값을 일일이 살펴봐야 하는 추가적인 작업 필요 - 속도면에서 불리함

- 리스트와 객체에 대한 참조로 인해 속도를 희생하게 됨

딕셔너리

- 키/값 구조로 이뤄진 딕셔너리

- 입력 순서가 유지, 내부적으로 해쉬 테이블로 구현

 

- 인덱스를 숫자로만 지정할 수 있는 리스트와 달리 

- 딕셔너리는 문자를 포함해 다양한 타입을 키로 사용할 수 있음

 

- 파이썬의 딕셔너리는 해시할 수 있다면 숫자, 문자, 집합까지 불변 객체를 모두 키로 사용 가능

- 이 과정을 해싱, 해시 테이블을 이용해 자료를 저장함

 

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

- 해시 테이블은 최악의 경우 O(n)이 될 수 있으나 대부분의 경우 훨씬 더 빨리 실행됨

- 분할 상환 분석에 따른 시간 복잡도는 O(1)

 

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

- 딕셔너리는 대부분의 연산이 O(1)에 처리 가능한 자료형

- * 딕셔너리의 입력 순서가 유지될 것이라고 가정하고 문제를 푸는 것을 권장 X

딕셔너리 활용 방법

- 딕셔너리 선언

 

a = dict()

a = {}

 

- 딕셔너리 key1, key2 초깃값 지정과 새로운 key3 별도 선언 후 값 지정

 

a = {'key1' : 'value1', 'key2' : 'value2'}

a['key3'] = 'value3'

>> {'key1' : 'value1', 'key2' : 'value2', 'key3' : 'value3'}

 

딕셔너리의 키 지정 후 값 조회 (존재하지 않는 키 조회시 에러 발생)

 

a['key1']
>> 'value1'

# 반복문을 이용한 조회
for k, v in a.items():
	print(k, v)

 

딕셔너리에 KeyError 에러가 발생하면 try 구문으로 예외 처리할 수 있음

 

try:
	print(a['key4])
except KeyError:
	print('존재하지 않는 키')
    
# 키가 존재하는지 미리 확인하는 코드
if 'key4' in a:
	print('존재하는 키')
else:
	print('존재하지 않는 키')

 

딕셔너리의 키 삭제

 

del a['key1']
>> {'key2' : 'value2', 'key3' : 'value3'}

딕셔너리 모듈

특수한 형태의 컨테이너 자료형 defaultdict, Counter, OrderedDict

defaultdict 객체

- 존재하지 않는 키를 조회할 경우, 에러 메세지 출력 대신

- 디폴트 값을 기준으로 해당 키에 대한 딕셔너리 아이템을 생성해줌

- 실제로는 collections.defaultdict 클래스를 가짐

 

# A와 B에 5와 4를 할당, 딕셔너리에 2개의 아이템 존재
a = collections.defaultdict(int)
>> a['A'] = 5
>> a['B'] = 4

# 존재하지 않는 C
>> a['C'] += 1

>>>defaultdict(<class 'int'>, {'A' : 5, 'B' : 4, 'C' : 1})

 

- 존재하지 않은 값 C에 1을 더하는 코드가 들어왔을 때,

- 원래라면 KeyError가 발생해야되는데 defaultdict 객체는 에러 없이 바로 +1 연산 수행

- 이 경우는 디폴트가 0을 기준으로 자동으로 생성한 후 여기에 1을 더해

- 최종적으로 1이 만들어짐 - {'A' : 5, 'B' : 4, 'C' : 1} 

Counter 객체

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

- 키에는 아이템 값, 값에는 해당 아이템의 개수가 들어간 딕셔너리

 

a = [1, 5, 5, 5, 6, 6]
b = collections.Counter(a)

Counter({5:3, 6:2, 1:1})

가장 빈도수가 높은 요소 추출

# 가장 빈도가 높으 2개의 요소 추출
b.most)common(2)
>> [(5, 3), (6, 2)]

OderedDict 객체

- 해시 테이블을 이용한 자료형은 입력 순서가 유지되지 않음 (파이썬 3.6 이하는 이에 해당)

- 입력 순서가 유지되는 OrderedDict 객체 제공

- 코딩 테스트가 하위 버전을 사용한다면 이에 주의해야 함 (입력 순서대로 결과를 추출해 풀이를 제출해야 하는 경우)

 

collections.OrderedDict({'banana' : 3, 'apple' : 4})

OrderedDict([('banana', 3), ('apple', 4)])