[2023.07.28] 요세푸스 순열 / PriorityQueue / Heap

https://teresa88.tistory.com/56

[자바] 4949번 균형잡힌 세상

 

https://teresa88.tistory.com/57

[자바] 11279번 최대 힙

 

https://teresa88.tistory.com/58

[자바] 11866번 요세푸스 문제 0

 

1. 요세푸스 순열

https://velog.velcdn.com/images/zabaniya09/post/36ffd1c4-c683-4292-a707-46709ad94bd8/image.jpg

 

유래

• 유대인 역사가 플라비우스 요세푸스가 겪은 경험을 바탕으로 만들어진 문제라고 한다.전쟁 중 자신을 포함한 41명이 로마군에 포위 되었고 로마군의 손에 죽느니 집단자살하기로 하지만 요세푸스는 그 뜻에 반대하여 수학적 논리를 발휘 하여 끝까지 살기 위한 자리를 찾아 결국 살아남고 항복하였다.

 

풀이

풀이는 2가지 경우가 있다.

• 제거되는 순서와 마지막 남은 수를 모두 구하는 풀이
  • 배열
  • 연결리스트
  • 큐
  • 이진 탐색 트리
• 마지막 남은 수만 구하는 풀이

다음번에도 이와 같은 문제가 나오면 위와 같은 자료구조를 참고하여 풀어야겠다.

 

참고한 사이트

https://namu.wiki/w/%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4%20%EB%AC%B8%EC%A0%9C

https://namu.wiki/w/%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4%20%EB%AC%B8%EC%A0%9C

 

2. PriorityQueue

https://www.dotnetlovers.com/Images/InsertioninMaxHeap114201985400AM.png

• 우선 순위 큐라고 하며 Queue와 구조가 비슷하다.
• 우선순위를 정해 그 순위가 높은 순서대로 Out된다.
• 값을 비교해야하므로 null을 허용하지 않는다.
• 내부 요소는 힙으로 구성 되어 이진 트리 구조로 이루어져 있다.
• Heap을 이용하여 구현하는 것이 일반적이다. = 최대 값이 우선 순위인 큐 → 최대 힙 / 최소 값이 우선 순위인 큐 → 최소 힙
• import java.util.PriorityQueue로 사용할 수 있다.

import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
         // 우선 순위 낮은 숫자
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        // 우선 순위 높은 숫자
        PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(Collections.reverseOrder());

        // 삽입
        priorityQueue.add(1); // 삽입 성공 시 true 반환 -> 실패 하면 예외 발생
        priorityQueue2.offer(1);

        // 삭제 -> 우선 순위가 높은 값이 제거
        priorityQueue.poll(); // Queue의 머리 부분의 원소를 제거한 후 반환하고 비어 있으면 null 반환
        priorityQueue2.remove(1); // 값을 비교하여 같은 원소 제거
        priorityQueue2.clear(); // Queue의 모든 요소 제거 -> 초기화

        // 출력
        priorityQueue.offer(1);
        priorityQueue2.peek(); // 원소를 제거하기 않고 출력하고 비어 있으면 null을 반환한다.
        
        // 존재 여부 확인
        priorityQueue.isEmpty(); // Queue에 원소가 존재하면 false, 존재하지 않으면 true를 반환한다.
        
    }
}

 

예시

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.offer(1);
pq.offer(2);
pq.offer(3);
pq.offer(4);
pq.offer(5);
pq.offer(6);
pq.offer(7);

https://haservi.github.io/posts/algorithms/priority-queue/images/image002.png#center

https://haservi.github.io/posts/algorithms/priority-queue/images/image003.png#center

 

 

참고한 사이트

https://coding-factory.tistory.com/603

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리

https://haenny.tistory.com/358

[자료구조] 자바 우선순위 큐(Priority Queue)의 클래스 사용하기

https://haservi.github.io/posts/algorithms/priority-queue/

Java Priority Queue(우선순위 큐) 원리 및 사용 방법

 

 

3. Heap

• Binary Heap(이진 힙)이라고 부르기도 한다.
• 중복값을 허용한다.
• 트리 형태의 자료 구조 이며 완전 이진 트리(항상 왼쪽부터 값이 채워진다.)이고 중간에 빈 데이터가 없다. 
  • 이진 트리는 배열 또는 연결리스트로 표현이 가능하다.

https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FblbjFV%2Fbtq1K3P9Y8v%2FH393OwoRI9lX8N3wrz9OO1%2Fimg.png

https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FIhRCJ%2Fbtq1KBzynQT%2FPeGuw08s4e4c8Obna4zaYK%2Fimg.png

• 상 하의 관계가 중요하고 좌 우는 중요하지 않다. → 형제 노드 간의 우선 순위가 없다.
• 최대, 최소 기준으로 데이터를 찾는 연산이 빠르다.
• Max Heap
  • 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같다.
  • 루트노드 = 트리의 최대값
• Min Heap
  • 부모 노드의 값은 항상 자식 노드의 값보다 작거나 같다.
  • 루트노드 = 트리의 최소값
• 예제는 참고한 사이트 맨 마지막 사이트 내용이 이해하기 쉬웠다.

 

참고한 사이트

https://yoongrammer.tistory.com/69

[자료구조] 이진 트리 (Binary tree) 알아보기

https://ish0301.tistory.com/entry/%ED%9E%99-heap-%EA%B0%9C%EC%9A%94-%EC%9E%90%EB%B0%94%EB%A1%9C-%EA%B5%AC%ED%98%84

힙 (heap) 개요, 자바로 구현

https://velog.io/@suk13574/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0Java-%ED%9E%99heap

[자료구조/Java] 힙(heap)

https://kim6394.tistory.com/222

[자료구조/Java] 힙(Heap) 구현