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

 

 

파이썬에서 가장 빈번하게 사용되는 자료형

1. 리스트

2. 딕셔너리

이 두 가지 자료형은 모든 문제에 빠짐없이 쓰이는 자료형이므로 확실히 이해 하기! 

 

 

 

 

1. 리스트

 

• 순서대로 저장하는 시퀀스(입력한 순서대로 유지된다)
• 숫자 외에도 다양한 자료형과 함께 저장 가능 (ex. [1, 2, 3, 5, 4, '안녕', True] )
• 변경 가능한 (Mutable List) 
• 동적 배열로 구현된

 

 

 

장점

스택을 사용할 지, 큐를 사용할 지 고민하지 않아도 됨.
이말은 즉, 리스트가 스택과 큐에서 사용 가능한 모든 연산을 함께 제공한다는 뜻. 

 

 

 

 

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

연산	시간 복잡도	설명
len(a)	O(1)	전체 요소의 개수를 리턴
a[i]	O(1)	인덱스의 i 요소를 가져옴
a[i : j]	O(k)	i 부터 j-1 까지 슬라이스.  k개의 요소가 있다고 하면 각 객체 k개에 대한 조회가 필요하므로 O(k)
elem in a	O(n)	elem 요소가 a 안에 있는 지 확인. 처음부터 순차탐색 하므로 n 만큼 시간 소요.
a.count(elem)	O(n)	elem의 요소 개수를 리턴
a.index(elem)	O(1)	elem 요소의 인덱스 리턴
a.append(elem)	O(1)	리스트의 마지막에 elem 요소 추가
a.pop()	O(1)	리스트의 마지막 요소 추출. 스택 연산
a.pop(0)	O(n)	리스트 첫번째 요소 추출. 큐 연산 전채 복사가 필요하므로 O(n)  ➡️ 이 경우 데크 사용 권장( 덱은 O(1) )
idel a[i]	O(n)	i에 따라 다르며 최악의 경우 O(n)
a.sort()	O(nlogn)	정렬. 팀소트 사용.  최선의 경우 O(n)에도 실행될 수 있음
min(a), max(a)	O(n)	최솟값, 최댓값을 계산하기 위햐서는 전체 선형 탐색해야 하므로 O(n)
a.reverse	O(n)	뒤집는다. 리스트 입력 순서가 유지되므로  뒤집으면 반대로 됨.

 

 

 

 

---

 

 

 

 

리스트 특징 

 

 

1) 슬라이싱 

 

특정 범위 내의 값을 매우 편리하게 가져올 수 있음. 

a[i : j] 일 때, i 부터 j-1 까지 값을 리턴함. 

 

# 리스트
[1, 2, 3, 4, 5, '안녕', True]

a[1:3]
>> [2, 3]

 

 

# 시작 인덱스 생략 가능
# 맨 처음부터 2번째 인덱스까지 반환
a[:3] 
>> [1 ,2, 3]

 

 

# 종료 인덱스도 생략 가능 
# 4부터 맨 마지막까지 반환

a[4:]
>> [4, '안녕', True]

 

 

 

# 세번째 파라미터 : 단계(step)의 의미. 

# 맨 마지막 파라미터는 스텝의 의미
# 2씩 건너 뜀
# '1'  2  '3'

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

 

 

---

 

2) 삭제 

1. 인덱스를 사용하여 삭제 - del , pop

 

[1, 2, 3, 4, 5, '안녕', True]

del a[1]     # 1번 인덱스 삭제 
>> [1, 3, 4, 5, '안녕', True]

 

 

[1, 2, 3, 4, 5, '안녕', True]

a.pop(5)    # 다섯번째 인덱스 삭제 
>> [1, 2, 3, 4, 5, True]

 

 

2. 값을 통한 삭제 - remove

[1, 2, 3, 4, 5, '안녕', True]

a.remove(3)    # 값이 3인 것을 삭제 
>> [1, 2, 4, 5, '안녕', True]

 

 

 

 

* 리스트의 형태 
리스트는 객체에 대한 포인터 목록으로 구현되어 있다. 

 

 

일반적 정수형 배열 : 정수로만 이루어진 값을 연속된 메모리 공간에 저장
파이썬 리스트 : 연결 리스트에 대한 포인터 목록을 관리하고 있음 

 

 

 

아래 배열을 보자. 

[1, '안녕', True]

 

 

파이썬 리스트는 포인터 목록을 관리하고 있다고 했다. 이는 각각의 객체에 대한 참조를 갖고 있다는 것으로 
만약 2번 인덱스 값에 대해 접근하려고 하면 포인터의 위치를 찾아가서 타입 코드를 확인하고 값을 일일이 살펴봐야 한다. 

 

모두 제각각인 자료형을 단일 리스트에 모두 통합하여 저장할 수는 있지만, (강력한 장점) 

값에 접근하기 위해서는 모든 포인터 위치를 보고 값을 확인해야 하기에 속도를 희생한 측면이 있는 언어이다. (성능상 무의미하긴 하지만..)

 

 

 

 

 

 

2. 딕셔너리 

 

 

• 키, 값 구조로 이루어짐
• (*파이썬 3.7 + 기준) 입력 순서가 유지된다.
• 해시 테이블로 구현되어 있음. 
  
  
  

 

장점

 

(인덱스를 숫자로만 지정할 수 있는 리스트와 달리) 문자를 포함해 다양한 타입을 키로 사용 가능.
숫자, 문자, 집합까지 불변 객체를 모두 키로 사용 가능 ➡️ 해싱. 
입력과 조회 모두 O(1).

 

 

 

 

딕셔너리의 주요 연산 시간 복잡도

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

 

 

 

3.7 이상부터 내부적 인덱스를 이용해 입력 순서를 유지하도록 개선되었지만,
여전히 3.6 이하를 사용하는 곳이 많으므로 입력 순서가 유지될 것이라 가정하는 것은 매우 위험! (버전 잘 확인하기) 

 

 

 

유용한 collections

import collections

collections.OderedDict()        # 입력 순서 유지 
collections.defaultdict()       # 조회 시 항상 디폴트 값 생성 -> 키 오류 방지
collections.Counter()           # 요소의 값을 키로 하고 개수를 값 형태로 만들어 카운팅

 

 

 

---

 

 

딕셔너리 활용 방법

 

 

1) 값 추가 

 

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

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

 

 

 

2) 키 존재하는 지 확인

 

if 'key4' in a:
	print('존재하는 키')
else :
	print('존재하지 않는 키')

 

 

 

3) 키, 값 조회 

 

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

 

 

 

4) 키 삭제 

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

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

 

 

 

---

 

 

딕셔너리 모듈

 

 

1) defaultdict 객체

 

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

a = collections.defaultdic(int)
a['A'] = 5
a['B'] = 4
a 
>> defaultdict(<class 'int'>, {'A':5 , 'B' : 4}) 


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

 

 

'C' 는 없는 키 값이지만,
디폴트인 0을 기준으로 자동으로 생성 후 여기 1을 더해 최종적으로 1인 값과 그의 키인 'C' 를 딕셔너리에 추가한다. 

 

 

 

---

 

2) 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})

 

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

 

 

 

가장 빈도 수 높은 요소 추출

b.most_common(2)

>> [(5, 3), (6, 2)]

 

 

 

---

 

 

3) OrderedDict 객체 (파이썬 3.7 미만 버전) 

 

 

# 대부분 언어에서 해시 테이블을 이용한 자료형은 입력 순서 유지 X
# 입력 값을 부여할 경우 OrderedDict는 입력 그대로 순서가 유지됨.

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