2023.05.25 목 워밍업 4일차

• 학습목표

1. 알고리즘 페어 프로그래밍 문제 4일차

• 학습 스케쥴

3:00 ~ 4:00 PM - 알고리즘 페어 프로그래밍 3일차 학습 공유

4:00 ~ 6:00 PM - 알고리즘 페어 프로그래밍 학습

7:00 ~ 9:00 PM - 토의 및 마무리

---

Queue의 LinkedList와 ArrayList

데이터를 저장하는 방식이 다름.

LinkedList - 노드로 연결된 구조로 데이터를 저장. 각 노드는 데이터와 다음 노드에 대한 포인터를 가지고 있음.

ArrayList - 배열로 데이터를 저장. 배열은 연속적인 메모리 공간에 데이터를 저장한다.

• LinkedList는 ArrayList에 비해 삽입과 삭제가 빠르다. LinkedList는 노드의 연결만 변경하면 되지만, ArrayList는 데이터 변경 시 전체를 이동해야 하기 때문에 삽입과 삭제가 느림.
• LinkedList는 ArrayList에 비해 검색이 느리다. LinkedList는 처음부터 노드를 순회해야 하고, ArrayList는 인덱스를 사용하여 빠르게 검색할 수 있음.
• LinkedList는 ArrayList에 비해 메모리 사용량이 적다. LinkedList는 노드만 사용하지만, ArrayList는 지정된 크기의 배열을 사용하기 때문.

*삽입과 삭제가 자주 발생하는 경우 LinkedList를 사용.

검색이 자주 발생하는 경우 ArrayList를 사용.

 

PriorityQueue

Java에서 제공하는 우선순위 큐 자료구조. 내부적으로 heap 자료구조를 사용하여 구현되며, 각 원소는 우선순위를 가지고 있다.

원소의 순서는 항상 오름차순.

원소를 삽입하거나 삭제하는 연산은 O(log n)의 시간복잡도를 가지며, n은 PriorityQueue의 크기.

PriorityQueue는 동기화되지 않으므로, 여러 스레드에서 동시에 접근할 경우 문제가 발생할 수 있다.

 

PriorityQueue의 메서드

• add(element): element를 PriorityQueue에 추가합니다. 큐가 가득 차 있으면 예외발생(IllegalStateException)
• offer(element): element를 PriorityQueue에 추가합니다. 만약 큐가 가득 차 있으면, IllegalStateException 대신 false를 반환.
• peek(): PriorityQueue의 가장 앞에 있는 원소를 반환. 제거는 하지 않음.
• poll(): PriorityQueue의 가장 앞에 있는 원소를 반환 후, 제거.
• remove(element): PriorityQueue에서 element를 제거.
• contains(element): PriorityQueue에 element가 있는지 확인.
• size(): PriorityQueue의 크기 반환.

 

활용

• 최소값 알고리즘: PriorityQueue에 원소들을 삽입하고, poll()을 사용하여 가장 앞에 있는 원소를 반환.
• 최대값 알고리즘: PriorityQueue에 원소들을 역순으로 삽입하고, poll()을 사용하여 가장 앞에 있는 원소를 반환.
• 우선순위가 있는 작업을 처리하는 알고리즘: PriorityQueue에 작업들을 삽입하고, poll()을 사용하여 가장 앞에 있는 작업을 처리합니다.
• 정렬 알고리즘: PriorityQueue에 원소들을 삽입하고, poll()을 사용하여 원소들을 순서대로 꺼냅니다.