파이썬알고리즘인터뷰. 5장요약

5장. 리스트, 딕셔너리

리스트

파이썬의 리스트는 말 그대로 순서대로 저장하는 시퀀스이자 변경 가능한 목록을 말한다. 입력 순서가 유지되며, 내부적으로는 동적 배열로 구현되어 있다. 파이썬에서는 list()로 표현된다.

파이썬 리스트의 가장 좋은 점은 매우 다양한 기능을 제공한다는 점이다. 리스트를 사용하면 사실상 스택을 사용할지, 큐를 사용할지를 고민하지 않아도 되며, 스택과 큐에서 사용 가능한 모든 연산을 함께 제공한다. 이는 코딩테스트 시 다른 언어에 비해 매우 유리한 조건을 갖게 되는 셈이며, 코딩 테스트 언어로 파이썬을 택해야 하는 매우 중요한 이유 중 하나이다.

리스트는 다양한 기능을 제공하면서도 $O(1)$에 실행 가능한 연산들도 몇가지 있다. 리스트 마지막에 요소를 .append()로 추가하거나, 리스트 마지막 요소를 pop()으로 추출하거나, 원하는 인덱스의 요소를 조회하는 연산은 모두 $O(1)$이다. 반면에 요소를 삭제하거나 큐의 연산이기도 한 첫 번째 요소를 추출하는 pop(0)는 $O(n)$이다. 따라서 리스트에 주로 큐의 연산을 사용할 때는 주의가 필요하다.

### 리스트의 활용 방법

#### 선언

a = list()
대괄호 선언 : a = []
초기값 지정해 선언 : a = [1,2,3]
append로 추가 : a.append(4)
insert()함수로 특정 위치 인덱스 지정해 요소 추가 : a.insert(3,5) = 3 index에 5삽입

삭제

인덱스로 삭제하기 :
```
a = [1,2,3,5,4]
del a[1]
```
결과 : a = [1,3,5,4]
값에 해당하는 요소 삭제하기 :
```
a.remove(3)
```
결과 : a = [1,5,4]
스택의 팝 연산
```
a.pop(2)
```
결과 : 4

딕셔너리

파이썬의 딕셔너리는 키/값 구조로 이뤄진 딕셔너리를 말한다. 내부적으로는 해시 테이블로 구현되어 있다. 구현은 dict()로 이루어진다.

이처럼 딕셔너리를 대부분의 연산이 O(1)에 가능한 매우 우수한 자료형이다. 키/값 구조의 데이터를 저장하는 유용한 자료형으로서, 코딩테스트에서도 리스트만큼이나 매우 빈번하게 활용된다. 원래 파이썬에서 딕셔너리는 입력순서가 유지되지 않았다. 마찬가지로 대부분의 언어에서 해시테이블을 이용한 자료형은 입력순서가 유지되지 않는다. 그러나 파이썬 3.7부터는 내부적으로 인덱스를 이용해 입력 순서를 유지하도록 개선됐다. 코딩 테스트시에 인터프리터의 버전을 정확히 확인할 수 없는 상황에서는 입력순서가 유지되지 않을 수 있으므로 딕셔너리의 입력순서가 유지될 것이라고 가정하고 진행하는 것은 매우 위험하며 일반적으로 권장하지 않는다.

딕셔너리 활용 방법

선언

a = dict()

a = {}

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

a['key3'] = 'value3'

조회

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

결과 :
key1 value1
key2 value2
key3 value3

삭제

del a['key1']

결과 : {‘key2’:’value2’, ‘key3’:’value3’}

딕셔너리 모듈

defaultdict 객체

defaultdict 객체는 존재하지 않는 키를 조회할 경우, 에러 메시지를 출력하는 대신 디폴트 값으로 해당 키에 대한 아이템을 생성해준다. 마찬가지로 실제로 collections.defaultdict 클래스를 갖는다

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

결과 : defaultdict(<class ‘int’>, {‘A’:5,’B’:4})

여기서 A와 B에 5와 4를 할당했다.

a['C']+=1 

결과 : defaultdict(<class ‘int’>, {‘A’:5,’B’:4,’C’:1})

이제 C는 존재하지 않는 키다. 원래의 딕셔너리라면 keyerror가 발생하겠지만 defaultdict객체는 에러 없이 바로 +1 연산이 가능하고 이 경우 디폴트인 0을 기준으로 생성한 후 여기에 1을 더해 최종적으로 1이 만들어진다.

Counter 객체

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

Counter객체는 이처럼 키에는 아이템의 값이, 값에는 해당 아이템의 개수가 들어간 딕셔너리를 생성한다. 개수를 자동으로 계산해주기 때문에 매우 편리하며, 여러 분야에서 다양하게 활용된다.

그렇다면 Counter객체에서 가장 빈도수가 높은 요소는 어떻게 추출할 수 있을까?
most_common() 을 사용하면 된다

b.most_common(2)

결과 : [(5 , 3) , (6 , 2)]
이처럼 가장 빈도가 높은 2개의 요소를 추출 할 수 있다.

OrderedDict 객체

대부분의 언어에서 해시 테이블을 이용한 자료형은 입력 순서가 유지되지 않는다. 파이썬 3.6이하도 마찬가지였기에 입력순서가 유지되는 OrderedDict라는 별도의 객체를 제공했다. 다음과 같이 입력값을 부여할 경우 OrderedDict는 입력 그대로 순서가 유지된다.

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

결과 : OrderedDict([( ’banana ’, 3) , ( 0 apple 0, 4) , (’ pear 0, 1), ( 0 orange 0, 2) 1 )

타입선언

각각 리스트, 튜플, 딕셔너리, 집합을 기호로 선언한 경우다. 이 중에서 딕셔너리와 집합은 같은 중괄호 {}를 사용하지만 키의 존재 유무로 서로 다른 자료형으로 선언된다.

PREVIOUS파이썬알고리즘인터뷰. 4장요약

NEXTLeetCode 125번 <유효한 팰린드롬>