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

이번 주 목표

📢 이번주 목표는 백준 실버1까지 승급하는 것이다. 현재 실버2이다.

오늘 스케줄

09:00~09:20 팀 모닝 스크럼
09:20~12:00 데일리 과제 문제 풀이
12:00~13:00 점심 식사
13:00~17:00 데일리 과제 문제 풀이
17:00~17:20 팀 코드 선정 회의
17:20~18:00 휴식
18:00~18:20 기술 매니저님과 팀 코드 리뷰
18:20~19:20 저녁 식사
19:30~20:00 산책
20:00~21:00 장보기
21:30~00:30 프로그래머스 문제 풀이(5문제)
01:00~01:10 TIL 작성

오늘 목표

👉 데일리 과제 모두 풀기

👉 TIL 빠지지 않고 작성하기

👉 북스터디 참여

👉 마이크로서비스 강의 수강

👉 프로그래머스 5문제 풀기

 

오늘 한 것

• 데일리 과제 모두 풀기
• TIL 빠지지 않고 작성하기
• 프로그래머스 5문제 풀기

오늘 못한 것

• 북스터디 참여
• 마이크로서비스 강의 수강

알게된 것

⭐우선순위 큐(Priority Queue)

우선순위 큐의 이해를 돕기 위한 max, min heap 자료구조

✅설명

PriorityQueue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다.

Comparable Interface를 구현하면 compareTo method를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue 가 알아서 우선순위가 높은 객체를 추출 해준다.

PriorityQueue는 Heap을 이용하여 구현하는 것이 일반적이다.

데이터를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아 옮기는 방식으로 진행된다.
최대 값이 우선순위인 큐 = 최대 힙, 최소 값이 우선순위인 큐 = 최소 힙

출처: https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

 

✅ 특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다.
   우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야한다.
2. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다.
3. 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)이다.
4. 우선순위를 중요시해야 하는 상황에서 주로 쓰인다.

 

✅ 코드 예시

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // 우선순위 큐 선언
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        // 내림차순 우선순위 큐 선언
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        // 삽입 (offer)
        pq.offer(10);
        pq.offer(30);
        pq.offer(20);

        // 조회 (peek)
        System.out.println("큐의 맨 앞 요소: " + pq.peek());

        // 삭제 (poll)
        while (!pq.isEmpty()) {
            System.out.println("큐에서 삭제: " + pq.poll());
        }
    }
}

 

✅ 시간 복잡도

최고(최소) 우선순위 확인	O(1)
요소 검색	O(n)
크기(요소 수)	O(1)
배열/목록으로 변환	O(n)

 

🤔오늘의 반성

- 마이크로서비스 강의를 못 들었다 ㅠㅠ
- 내일은 꼭 책 읽자..

 

👍 오늘의 칭찬

1. 지각하지 않았다.
2. 깃헙 1일 1커밋 달성
3. TIL을 빠지지 않고 작성했다.
4. 오늘의 데일리 과제 모두 풀었다.

❗ 항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.
https://hanghae99.spartacodingclub.kr/reboot