Junhyuk Yu

I will be an amazing person.

해당 내용은 ‘파이썬 알고리즘 인터뷰’ 책의 일부를 발췌하여 정리한 내용입니다.

리스트

파이선의 리스트(list)는 순서대로 저장하는 시퀀스이자 변경 가능한 목록(Mutable list)을 말한다. 입력 순서는 유지되며, 내부적으로는 동적 배열로 구현되어 있다. 파이썬 리스트를 사용하면 사실상 스택 또는 큐에 대한 고민을 하지 않아도 되며, 스택과 큐에서 사용 가능한 모든 연산을 함께 제공한다. 이는 코딩 테스트에서 다른 언어에 비해 매우 유리한 조건 중 하나이다. 다만, 큐의 연산을 사용할 경우 시간 복잡도에 대한 주의가 필요하다.

연산 시간복잡도 설명
len(a) O(1) 전체 요소의 개수를 리턴
a[i] O(1) 인덱스 i의 요소를 가져오기
a[i:j] O(j) 인덱스 i부터 j-1까지 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)이 나옴. (만약 큐의 연산을 사용하면 데크(deque) 사용을 권장)
del a[i] O(n) i에 따라 다르지만, 최악의 경우는 O(n)
a.sort() O(n log n) 정렬
min(a), max(a) O(n) 최소/최대값을 계산하기 위해서는 전체를 선형 탐색해야 함
a.reverse() O(n) 뒤집기

리스트 활용 방법

a = []
---
a = [1, 2, 3]
a

out:
[1, 2, 3]
---
a.append(4) # 초깃값을 지정해 선언하거나 추가
a

out:
[1, 2, 3, 4]
---
a.insert(3,5) # 3번째 인덱스에 5를 삽입
a

out:
[1, 2, 3, 5, 4]

숫자 외에도 문자와 불리언을 삽입할 수 있다.

a.append('안녕')
a.append(True)
a

out:
[1, 2, 3, 5, 4, '안녕', True]
---
a[3] # 3번째 인덱스에 있는 값 불러오기

out:
5

슬라이싱 기능을 이용하여 특정 구간에 있는 값을 불러올 수 있다.

a[1:3] # 1번째부터 3번째까지 값을 불러오기

out:
[2, 3]
---
a[:3] # 0번째부터 3번째까지 값을 불러오기

out:
[1, 2, 3]
---
a[4:] # 4번째부터 마지막까지 값 불러오기

out:
[4, '안녕', True]
---
a[1:4:2] # 0번째부터 4번째까지 2 칸씩 건너뛰어서 불러오기

out:
[2, 5]

존재하지 않는 인덱스를 조회할 경우 에러가 발생한다. 그럴 경우, try구문으로 예외처리를 해주자.

a[9]

out:
IndexError: list index out of range
---
try: # try로 예외처리
    print(a[9])
except IndexError:
    print('존재하지 않는 인덱스')

out:
존재하지 않는 인덱스

리스트에서 요소를 삭제하는 방법은 크게 두가지로 나뉘며 인덱스로 삭제하거나 값으로 삭제할 수 있다.

# del : 해당 인덱스의 값 삭제
del a[1]
a

out:
[1, 3, 5, 4, '안녕', True]
---
# remove() : 값에 해당하는 요소 삭제
a.remove(3)

out:
[1, 5, 4, '안녕', True]
---
# pop() : 삭제될 값을 리턴하고 삭제. 스택의 pop연산 처럼 추출로 처리
a.pop(3)

out:
'안녕'

a

out:
[1, 5, 4, True]

리스트의 특징

앞선 포스팅에서 말한바와 같이, 파이썬의 모든 자료형은 정수형 또한 객체로 되어있음을 살펴보았다. 리스트는 이처럼 객체로 되어있는 모든 자료형을 포인터로 연결하여 참조한다. 사실상 연결 리스트에 대한 포인터 목록을 배열 형태로 관리하고 있으며, 그 덕분에 파이썬의 리스트는 배열과 연결 리스트를 합친 듯이 강력한 기능을 자랑한다. 이 때문에 정수, 문자, 불리언 등 제각기의 다양한 타입을 동시에 단일 리스트에서 관리하는 것이 가능하다. 그러나, 각 자료형의 크기는 저마다 서로 달라 연속된 메모리에 할당하는 것은 불가능이다. 결국 각 객체에 대한 참조로 구현할 수 밖에 없다. 이러하다 보니 인덱스로 조회할 때 모든 포인터의 위치를 찾아가서 타입 코드를 확인하는 추가작업이 들어가기 때문에 속도면에서는 불리함을 가지고 있다. 강력한 기능을 위해 속도를 희생한 측면이 있다.

딕셔너리

파이썬의 딕셔너리(Dictionary)는 키/값 구조로 이뤄진 딕셔너리를 말한다. 내부적으로는 해시 테이블(Hase Table)로 구현되어 있다. 파이썬은 불변 객체를 모두 키로 사용할 수 있다. 이 과정을 해싱이라고 하며, 해시 테이블을 이용해 자료를 저장한다.

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

딕셔너리 대부분의 연산이 O(1)에 처리가 가능한 우수형 자료형이며, 키/값 구조의 데이터를 저장하는 유용한 자료형으로서 코딩테스트에서 리스트만큼이나 매우 빈번하게 활용된다.

파이썬 3.6 이하에서는 입력 순서가 유지되지 않아 collections.OrderedDict()라는 별도 자료형을 사용해야 하므로, 버전을 알 수 없는 환경에서는 딕셔너리의 입력 순서가 유지될 것이라고 가정하고 진행하는 것은 매우 위험하며 일반적으로 권장하지 않는다.

딕셔너리 활용 방법

# 딕셔너리 선언
a = {}
---
# 딕셔너리 값 입력

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

out:
{'key1': 'value1', 'key2': 'value2'}
---
# 딕셔너리 값 추가
a['key3'] = 'value3'
a

out:
{'key1': 'value1', 'key2': 'value2', 'key3': 'value3'}
---
# 딕셔너리 값 호출
a['key1']

out:
'value1'
---
# 딕셔너리 에러 예외처리
a['key4']

out:
KeyError                                  Traceback (most recent call last)
Cell In [8], line 1
----> 1 a['key4']

try:
    print(a['key4'])
except:
    print('존재하지 않는 키')

out:
존재하지 않는 키

딕셔너리에 있는 키/값은 for 반복문으로 조회가 가능하다.

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

out:
key1 value1
key2 value2
key3 value3

딕셔너리의 키의 삭제는 del로 삭제한다.

del a['key1']
a

out:
{'key2': 'value2', 'key3': 'value3'}

딕셔너리 모듈

defaultdict 객체

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

import collections

a = collections.defaultdict(int)
a['A'] = 5
a['B'] = 4
a

out:
defaultdict(int, {'A': 5, 'B': 4})
---
a['C'] += 1
a

out:
defaultdict(int, {'A': 5, 'B': 4, 'C': 1})

원래의 딕셔너리라면 KeyError가 발생하겠지만, defaultdict 객체는 에러 없이 바로 +1 연산이 가능하고 이 경우 디폴트인 0을 기준으로 자동으로 생성 후 1을 더해 최종적으로 1이 만들어졌다.

Counter 객체

Counter 객체는 아이템에 대한 개수를 계산해 딕셔너리로 리턴해준다.

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

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

type(b)

out:
collections.Counter # 딕셔너리를 한번 더 래핑한 collections.Counter 클래스

개수를 자동으로 계산해주기 때문에 매우 편리하며 여러 분야에서 활용된다. Counter객체에서 가장 빈도수가 높은 요소 추출은 most_common()을 사용하면 된다.

b.most_common(2)

out:
[(5, 3), (6, 2)]

가장 빈도가 높은 2개의 요소를 추출한 결과가 나왔다.

OrderedDict 객체

앞서 언급한 내용에 파이썬 3.6 이하는 딕셔너리의 순서가 유지되지 않는다고 했었다. 대부분의 인터프리터는 3.7 이상의 버전을 사용하지만 혹시나 그 이하의 버전을 사용하게 될 경우 collections.OrderedDict()을 사용하여 순서를 유지시킬 수 있다.

collections.OrderedDict({'banana' : 3, 'apple' : 4, 'pear' : 1, 'orange' : 2})

out:
OrderedDict([('banana', 3), ('apple', 4), ('pear', 1), ('orange', 2)])

You may also enjoy