[항해99 취업 리부트 코스 학습일지] 16일차

(인강) Heap, Hash Table #

힙 Heap, 우선순위 큐(Priority Queue) #

• Heap

  • 우선순위에 따라 정렬된 완전 이진트리 -> 하위 노드로 갈 수록 큰(또는 작은) 우선순위
  • 우선순위 큐를 구현하기 위해 사용
  • 최대 힙(Max Heap) 에서는 부모 노드가 자식 노드보다 항상 크다.
  • 최소 힙(Min Heap) 에서는 부모 노드가 자식 노드보다 항상 작다.

• 우선순위 큐

  • 삽입 순서와 상관없이 우선순위가 높은 데이터가 먼저 나가는 형태

  PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 최소 힙  
  minHeap.offer(5);  
  minHeap.offer(1);  
  minHeap.offer(3);  
  System.out.println(minHeap.poll()); // 1  
  
  PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // 최대 힙  
  maxHeap.offer(5);  
  maxHeap.offer(1);  
  minHeap.offer(3);  
  System.out.println(maxHeap.poll()); // 5
  

Hash Table #

• 키를 값에 매핑할 수 있는 구조
• 데이터를 빠르게 검색, 추가, 삭제 가능
• 조회 시 평균 O(1)의 시간복잡도를 가짐

연습 문제 #

K번째 최소/최대 원소 찾기 11286번: 절댓값 힙 중복 문자 없는 가장 긴 부분 문자열

오늘의 과제 #

1. 9375번: 패션왕 신해빈
2. 2075번: N번째 큰 수
3. 2002번: 추월
4. 15903번: 카드 합체놀이
5. 11286번: 절댓값 힙
6. 2295번: 세 수의 합
7. 1715번: 카드 정렬하기
8. 7662번: 이중 우선순위 큐

마지막 정리 #

Q. 오늘 진행된 강의에서 학습한 내용은 무엇인가요? #

• Heap, Hash Table

Q. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요? #

• 우선순위 큐
  • 삽입 log(N) | 탐색 O(n)
• HashTable
  • Java에서 어떤 Hash 함수를 사용 하는가?
  • Hash 충돌을 어떻게 완화하는가?
• Comparator, comparing

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

https://hanghae99.spartacodingclub.kr/reboot

#개발자포트폴리오 #개발자이력서 #개발자취업 #개발자취준 #코딩테스트 #항해99 #취리코 #취업리부트코스 #재취업