크래프톤정글 3주차; TIL 4 - 파이썬 type error, BFS, topological sort, 문자열 검색 알고리즘

• 개인적으로 공부하면서 지속적으로 정보를 추가, 수정, 삭제합니다.
• 정확하지 않은 부분은 피드백 주시면 감사합니다.

2022-11-14

파이썬 TypeError: unhashable type

참고: https://daewonyoon.tistory.com/363

무엇?

list1 = [1, 2, 3]
set1 = set([1, 2, 3])
d = {}
d[list1] = "리스트를 딕셔너리 키로 지정 불가능"
d[set1] = "집합을 딕셔너리 키로 지정 불가능"

>>> TypeError: unhashable type

파이썬에서 딕셔너리의 키를 지정할 때 리스트 자료형을 지정할 때 발생하는 에러

왜?

unhashable이란 해쉬화를 할 수 없다는 뜻으로,
해쉬화란 value에 고유한 라벨을 붙여 주는 것과 비슷한데, 이때 붙이는 라벨은 쉽게 변형되면 안되므로(immutable) 리스트, 집합처럼 값을 바꿀 수 있는 자료형은 쓸 수 없음.

어떻게?

tuple1 = (1, 2, 3)
d = {}
d[tuple1] = "튜플을 딕셔너리 키로 지정하기 가능"

값을 변경할 수 없는 튜플로 키를 지정해주기!

2022-11-15

BFS는 항상 최단 거리를 보장하나? (feat. 특정 거리의 도시 찾기)

참고: https://nulls.co.kr/graph/141

무엇?

BFS는 항상 최단 거리를 보장한다.

왜?

백준의 특정 거리의 도시 찾기 반례를 찾아보다가, 더 적은 최단 거리가 들어올 수 있는 경우를 가정하여 조건 처리를 하라는 누군가의 코멘트를 보았다. (결론: 이 말은 틀렸다.)
음?
그래서 BFS가 항상 최단 거리를 보장하는 것이 맞는지 궁금해졌다.

어떻게?

파이썬 KeyError를 안 보고 싶다면…

참고:

무엇?

KeyError란 딕셔너리와 관련된 에러이다.
딕셔너리에 없는 key를 넣어 값을 찾으려고 할 때 발생한다.

왜?

백준 3055번 탈출 문제… 뿐만 아니라 BFS, DFS 문제에서 딕셔너리를
많이 사용했는데 키 에러로 애먹음.

어떻게?

# 방법1 : 조건문 한 줄 추가하기 
if dict[key] > 1:   # 이런 식으로 바로 쓰지 말고, 
	print(dict[key])

if key in dict.keys:  # 이 라인을 추가해주기
	if dict[key] > 1:   
		print(dict[key])

# 방법2 : fromkeys 메소드를 이용해서 미리 딕셔너리를 초기화 해놓기!!
# dict.fromkeys(key목록, 디폴트값)
tup = (1, 2, 3)
d = dict.fromkeys(tup, 0)

2022-11-16

위상정렬 topological sort

참고: 책 Introduction to Algorithms Third Edition
[이것이 코딩 테스트다 with Python] 36강 위상 정렬 - YouTube

무엇?

자료구조 & 알고리즘 노트에 추가!

왜?

어떻게?

문자열 검색 알고리즘

참고: 책 Do it 자료구조와 함께 배우는 알고리즘 입문 파이썬 편

무엇?

문자열 검색 알고리즘

• 브루트포스,
• KMP법,
• 보이어무어

왜?

코치님의 미션
기술 면접 등으로 잘 등장한다고 함 !

어떻게?