섹션5: 자료구조 활용_해쉬, 힙

딕셔너리 해쉬: 정수만 인덱스 번호로 쓸 수 있는 리스트와 다르게 문자, 숫자 등을 인덱스 값으로 쓸수 있다.

sH = dict()

for key, value in sH() # key와 value값 확인

for key in sH() # key값만 확인

sH(특정 키 값) # value만 확인

 

힙:이진 트리를 바탕으로 만들어짐.노드의 왼쪽이 2k-1, 오른쪽이 2k+1 (k: level)

root 노드 기준 왼쪽: 왼쪽 sub tree

root 노드 기준 오른쪽: 오른쪽 sub tree

- 최소 힙: 부모 노드의 값이 자식의 노드 값보다 항상 작다.

import heapq

a =[]

heapq.heapop(a) # 힙인 a에서 root 노드 값을 pop한다.

heapq.heappush(a, n) # 힙인 a에 n값을 넣는다.

- 최대 힙: 부모 노드의 값이 자식의 노드 값보다 항상 크다.

import heapq # 최소 힙으로 작동.

a =[]

heapq.heapop(a) # 힙인 a에서 root 노드 값을 pop한다.

heapq.heappush(a, -n) # 힙인 a에 반대 부호인 -n값을 넣는다. 대신 출력할 때 부호값 다시 바꾸기.

 

8번: 단어찾기

단어들을 키값으로해서 공간의 value를 1로 체크한뒤,

0으로 바꾸면 1로 바꾼 값이 쓰이지 않는 단어.

 

9번: 아나그램

<딕셔너리 해쉬>

딕셔너리의 키 값: 알파벳

str1[A]의 value가 없는 경우, str1[A] = str1[A] + 1을 하면 오류가 발생한다.

str1.get(A, 0): A라는 키 값이 없으면 0값을 리턴하고 있으면 value값을 리턴한다.

str1[A] = str1.get(A, 0) + 1: 위 내용에 1을 더함.

 

<리스트 해쉬> *면접때 물어 볼 수 있어서.

대문자 26 + 소문자 26 -> 리스트의 인덱스 번호 총 52개 필요

문자(x)를 아스키 넘버로 변환: ord(x)

대문자 아스키 넘버: 65~90 --> x가 대문자의 경우 65를 빼야지 0번 인덱스부터 해싱된다. (대문자는 0~25까지 해싱된다)

소문자 아스키 넘버: 97~122 --> x가 소문자인 경우 71을 빼야지 26번 인덱스부터 해싱된다. (소문자는 26~52까지 해싱된다)

 

10번: 최소힙

heappush: 처음에는 자식 노드로 오다가 부모가 더 작으면 swap하기 -> 올라가면서 비교하기: upheap

heappop: root 노드 값이 나온다.

  가장 밑 level의 오른쪽 노드 값(7)을 빈 root 노드 값으로 옮긴다.

  root 노드의 자식들 (2, 3)과 비교해서 더 작은 값 선정 (2) -> 2와 7 swap -> 2가 root노드가 됨

  7의 자식들(4, 5)와 비교... -> 내려가면서 비교하기: downheap

 

11번: 최대힙

최대 힙은 최소 힙을 살짝 변형.

파이썬의 heapq는 기본적으로 최소 힙 기준으로 작동한다.

3, 4를 넣는다면 3이 부모가 4가 자식이다.

하지만 - 부호를 앞에 넣으면 -4, -3이 되어서 -4가 부모가 -3이 자식이 된다.

출력할때 부호를 바꾸면 된다.