🧩 코딩 테스트 정복기 @21#B*05

파이썬 알고리즘 인터뷰

📚📚📚👈🏻 책 구매 링크

🤴🏻👸🏻👵🏻👴🏻 👈🏻 소스코드 깃허브

😥😱🤪👈🏻   책 정오표   

🏓📡📺  👈🏻   유투브 채널

---

리스트

List

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

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

파이썬의 리스트는 큐와 스택에서 사용가능한 모든 연산을 제공하고 있다. 

 

엄청나게 편한 것이다. 

연산	시간 복잡도	설명
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)의 시간복잡도가 반영된다. 가능한 deque를 사용권장
del a[i]	O(n)	i 에따라 다르지만, 최악의 경우는 O(n)이다. a[i]를 지운다.
a.sort()	O(n log n)	정렬, 최선의 경우 O(n) 에도 실행된다.
min(a), max(a)	O(n)	최소/최대값, 선형탐색,
a.reverse()	O(n)	뒤집는다.

 

파이썬에서 리스트는 숫자 외에도 다양한 자료형을 단일 리스트에 관리할 수 있다. 

for i in range(4):
	a.append(i)
a.insert(3,9)
print(a) # [0,1,2,3]>> [0,1,2,9]
a.append('안녕')
a.append(True)
print(a) # [0,1,2,9,'안녕', True]
a[:2] # [0,1]
a[4:] # ['안녕', True]
a[0:4:2] # [0,2] 인덱스 0부터 3까지 2의 간격의 값

삭제

a = [1,2,3,4,5]
# 인덱스로 지우기
del a[2]
print(a) # [1,2,4,5]
# 값으로 지우기
a.remove(2)
print(a) # [1,4,5]
# pop으로 지우기
a.pop()
print(a) # [1,4]

파이썬의 리스트는 원시타입을 지원하지 않는다. 모두 객체이다.

리스트는 객체로 되어있는 모든 자료형을 포인터로 연결한 상태이다. 

사실상 연결 리스트에 대한 포인터 목록을 배열 형태로 관리하고 있어서, 배열과 연결 리스트를 합친 듯한

느낌을 주는 것이다. 

이렇기 때문에 여러 타입의 변수들을 리스트에 담을 수 있게 되는 것이다. 

당연히, 인덱스를 조회하는 데에도 모든 포인터의 위치를 찾아가서 타입 코드를 확인하고 값을 일일히 살펴봐야

하는 등 추가적인 작업이 필요하기 때문에, 속도 면에서도 훨씬 더 불리하다. 

---

 딕셔너리 

키/값 구조로 이뤄진 타입이며, 입력 순서가 유지된다. 

내부적으로는 해시 테이블로 구현되어있다. 

C++에선 std::unordered_map 으로 생각하면 되고, java 에선 HashMap이다. 

 

인덱스를 숫자로만 지정하지 않고, 문자를 포함한 다양한 타입으로 키로 사용할 수 있다. (리스트는 숫자만) 

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

최악의 경우 O(n)이 될 수 있으나 대부분의 경우 훨씬 더 빨리 실행된다. 

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

대부분의 연산이 O(1) 에 처리 가능한 매우 우수한 자료형이다. 

원래 파이썬에서 딕셔너리는 입력 순서가 유지되지 않았다. 

3.7 버전 부터는 내부적으로 인겟르를 이용해 입력 순서를 유지하도록 개선됐다. 

그러나, 순서가 유지 안된다고 가정하는 것이 좋다.

 

예외처리 방법.

# 예외처리
try:
	print(a['key4']
except KeyError:
	print('존재하지 않는 키')

예외처리 하지않고 미리 키가 존재하는지 확인하여 진행하는 방법. 

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

items()

for k, v in a.items():
	print(k, v)
# key1 value1
# key2 value2...

삭제

del a['key1']
# 해당 키와 값이 삭제된다.

---

DefaultDict 객체

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

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

collections 라이브러리 안에 있다. 따로 import해줘야 한다. 

from collections import defaultdict
a = defaultdict(int)
a['A'] = 5
a['B'] = 4
print(a) # {'A' : 5, 'B': 4}

a['C'] += 1
print(a) # {'A' : 5, 'B': 4, 'C':1}

'C' 키는 존재하지 않아 원래  딕셔너리라면 keyerror가 발생하지만,  

defaultdict의 경우에는 그렇지 않다.

+1 연산이 가능하여 디폴트인 0을 기준으로 자동으로 생성한 후 여기에 1을 더해 최종적으로 1이 만들어진다. 

 

Counter 객체 

아이템에 대한 갯수를 계산해 딕셔너리로 리턴한다. collections라이브러리에 속한다.

from collections import Counter
a = [1,2,3,4,5,5,5,6,6]
b = Counter(a)
print(b) # Counter({5:3, 6:2, 1:1, 2:1, 3:1, 4:1})

키에는 아이템의 값, 값에는 해당 아이템의 갯수가 들어간다.

type(b)를 하면 Counter로 되니, 유의하여 형을 바꿔줘야 한다. 

 

most_common()

가장 빈도 수가 높은 요소를 추출하는 메서드 이다. 

print(b.most_common(2))
# [(5,3), (6,2)]

가장 빈도가 높은 2개의 요소를 추출하는 코드이다. 

 

OrderedDict 객체

3.7버전 이전에, 순서가 유지 안된 자료형에 순서가 반영되게 해주었던 딕셔너리 객체이다. 

그러므로, 현재는 기본 딕셔너리를 사용하면 된다. 

그러나, 순서를 기대하는 것 자체가 위험하니, 알아두는 것이 좋다. 

 

type()선언에서 set , dict의 혼동을 주의 하자

type()

type([]) # <class 'list'>
type({}) # <class 'tuple'>
type({1}) # <class 'set'>