파이썬 알고리즘 인터뷰 - 리스트, 딕셔너리

리스트

언어	동적배열
파이썬	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부터 딕셔너리는 내부적으로 인덱스를 이용하며 입력 순서가 유지되도록 개선됐다.