😆 동빈나 님의 이코테 2021 강의 몰아보기를 보면서 공부한 내용을 정리하고 있습니다. 책은 이것이 취업을 위한 코딩 테스트다 with 파이썬을 참고하여 학습했습니다.😊
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조!
우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용!
→ 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우
- 스택은 LIFO 선입선출 구조
- 큐는 가장 먼저 삽입된 데이터. 순차적!
- 우선순위 큐는 가장 우선순위가 높은 데이터를 추출
우선순위 큐 구현 방법
힙은 완전이진트리 형식을 따른다! 루트노드부터 왼쪽 자식노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리야!
일반적으로 힙을 구성하기 위한 함수 이름을 Heapify()라고 한다!
파이썬의 기준으로 기본적으로 제공하는 힙 라이브러리가 minHeap이야!
maxHeap이 필요하다면 ! 코드 수정하면 돼
스택
스택은 LIFO 구조로 나중에 들어간 것이 가장 먼저 나오는 형태의 자료구조이다.
파이썬에서는 그냥 리스트를 가지고 append() → 가장 마지막에 자료 저장, pop() → 가장 마지막 자료 삭제. 리스트를 통해 스택을 쓰면 돼!
큐
큐는 FIFO 구조로 먼저 들어간 것이 먼저 나오는 형태의 자료구조.
파이썬에서는 deque를 활용해서 앞 뒤에서 삽입 삭제가 모두 가능하다.
(앞에서 삽입, 삭제 : appendLeft(), popLeft())
(뒤에서 삽입, 삭제 : append(), pop())
딕셔너리
딕셔너리는 리스트와 다르게 인덱스에 문자, 단어를 키 값으로 (인덱스 값으로) 설정할 수 있다. 단어들을 키 값으로 해서 해당 단어가 들어오면 +=1 해주는 식으로 원활하게 활용 가능하다.
딕셔너리에서 삭제할 때는 del dic["DB"] 이런 식으로 하면 됨.
딕셔너리에서 정렬
key, value를 이용한 정렬 따로 적용
-
key를 이용한 오름차순 정렬
dic = sorted(dic.items()) -
value를 이용한 오름차순 정렬
dic = sorted(dic.items(), key = lambda x : x[1]) -
key를 이용한 내림차순 정렬
dic = sorted(dic.items(), reverse = True) -
value를 이용한 내림차순 정렬
dic = sorted(dic.items(), key = lambda x : x[1], reverse = True)
트리
코테에서 배울 트리는 완전이진트리로 왼쪽 자식과 오른쪽 자식으로 구성.
트리를 통해 만드는 최소힙
최소힙은 부모노드의 값이 자식의 노드 값보다 항상 작아야 한다.
데이터가 들어올 때 어떻게 작동하는지 생각하자.
- 파이썬에서는 힙큐를 통해 이진트리를 구성할 수 있다.
