210421 TIL
오늘 한 일
- KDT 인공지능 데브코스 Day 2 듣기 + Day 3 일부
밀린 진도 열심히 따라잡는중...😵
Remind
트리의 순회 방식
-
DFT(Depth-First-Traversal) 깊이 우선 순회
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
- 전위순회(VLR), 중위순회(LVR), 후위순회(LRV)가 있음
- 재귀로 구현
- DFS
-
BFT(Breadth-First-Traversal) 너비 우선 순회
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방식
- Queue로 구현
- BFS
str.join(iterable)
- str의 내장 함수
- iterable이 str타입 iterable이여야 한다(안그러면 TypeError 발생)
- 사용 예
strlist = ['안', '녕', '하', '세', '요']
str1 = ''.join(strlist)
str2 = '!'.join(strlist)
print(str1) # '안녕하세요'
print(str2) # '안!녕!하!세!요'
새로 배운 것
힙(Heap) 자료구조와 python에서 custom comparator를 만들어 정렬하는 법을 알게 되었다!
또, 파이썬 dictionary에서 get(key)
사용시, key 값이 dictionary 내에 없을 때 default값을 받아오게 하는 법도 알게되었다~~!
힙(Heap) 자료구조
-
최대 세 가지 성질을 만족하고 있는 완전 이진 트리로 최소힙과 최대힙이 있음
-
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
-
반정렬 상태(느슨한 정렬 상태) 를 유지
-
최대 힙의 성질
- 루트 노드가 항상 최댓값을 가진다. (최소 힙은 루트가 항상 최소)
- 완전 이진 트리이다.
- 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다.
-
이진 탐색 트리와의 비교
- 원소들은 완전히 크기 순으로 정렬되어 있는가?
-> 이진탐색트리는 크기순으로 정렬이 가능하지만, 힙은 그렇지 않음 - 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가?
-> 이진탐색트리는 가능하지만, 힙은 불가능 - 부가의 제약 조건은 어떤 것인가?
-> 이진 힙은 이진탐색트리에 비해 완전 이진 트리여야함
- 원소들은 완전히 크기 순으로 정렬되어 있는가?
-
장점
- 완전 이진 트리이기 떄문에
n
개의 원소로 이루어진 최대 힙의 깊이는 항상log(n) + 1
- 따라서, 데이터 원소의 삽입/삭제 연산의 실행 시간은 언제나 log(n) 에 비례
- 완전 이진 트리이기 떄문에
-
구현
- 보통 배열로 구현
- 구현상의 편리함을 위해 0번째 인덱스는 사용하지 않음 (루트의 인덱스 번호는 1)
- 인덱스 사이의 관계
- 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
- 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
- 부모의 인덱스 = (자식의 인덱스) // 2
-
삽입 연산
- 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입
- 새로운 노드를 부모 노드들과 교환해서(위쪽 방향으로 swap) 힙의 성질을 만족시킴
-
삭제 연산
- 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제됨
- 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
- 새로운 루트 노드를 자식 노드들 중 최대값과 교환해서(아래 방향으로 swap) 힙의 성질을 만족시킴
Custom Comparator를 활용한 정렬
-
lambda 함수를 이용하는 것 외에도
functools.cmp_to_key()
를 활용하여
sort()
또는sorted()
사용 시 custom comparator를 key로 지정할 수 있음 -
사용 예
from functools import cmp_to_key
def myComparator(a, b): # custom 정렬 기준 구현, 여기서는 내림차순 정렬을 구현함
if a > b:
return -1 # a가 앞에 와야함
elif a < b:
return 1 # b가 앞에 와야함
else:
return 0 # 우선순위 동일
mylist = [1, 3, 2, 6, 4]
newlist = sorted(mylist, key=cmp_to_key(myComparator))
mylist.sort(key=cmp_to_key(myComparator))
### 결과 : [6, 4, 3, 2, 1]
Dictionary에서 key로 value 얻기 get(key)
- Dictionary에서
get(k)
는 k에 해당하는 key 값의 value를 리턴 - 존재하지 않는 key값인 경우
None
을 리턴 - 존재하지 않는 key값일 때 미리 정해놓은 default값을 리턴받고 싶을 때는
get(key, default값)
를 사용하면 됨! - 사용 예
d = { 'a':2, 'c':3, 'd':1 }
print(d['b']) # KeyError 발생
print(d.get('b')) # 'None'
print(d.get('b', '?')) # '?'
Author And Source
이 문제에 관하여(210421 TIL), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pengu/210421-TIL저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)