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', '?'))   # '?'