Algorithm/Data Structure

[Java] 백준 #1158 요세푸스 문제

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 1번부터 N번까지 N명의 사람이 원을 이루며 앉아있음 양의정수 K → 순서대로 K번째 사람 제거 → N명이 제거될 때까지 (N, K) 요세푸스 순열 구하기 💡 알고리즘 자료구조, 큐 💡 접근 처음에 중간에 원소가 나가면 인덱스도 하나씩 줄어들어야 하겠구나 라는 잘못된 생각을 해서 큐를 생각해내지 못했다. (규칙만 추가하며 산으로 가던 코드) int idx = K - 1; LinkedList res = new LinkedList(); while(list.size() > 0){ res.add..

[Python] 백준 #11866 요세푸스 문제 0

11866번: 요세푸스 문제 0 (acmicpc.net) 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net N명의 사람이 원을 이루며 앉아있음 K번째 사람을 제거 → N명의 사람이 모두 제거될 때까지 계속 제거 원에서 사람들이 제거되는 순서 ↔ (N,K)-요세푸스 순열 💡 알고리즘 구현, 자료구조, 큐 💡 접근 [Python] 백준 #1966 프린터 큐 (tistory.com) 풀다가 이 문제가 생각나서 deque으로 수월하게 해결하였다. → while문으로 카운트를 세면서 조건을 확인하고, 맞다면 result에 저장하고 pop 아니라면 맨 뒤로 보내고 pop 💡 코드 from collection..

[Python] 백준 #1966 프린터 큐

1966번: 프린터 큐 (acmicpc.net) 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 💡 알고리즘 자료구조, 큐 💡 접근방법 원소들을 Queue의 가장 뒤에 재배치하고, 가장 앞에 있는 원소는 pop해야한다. → 앞뒤로 pop, append가 자유로운 deque 사용 주어진 예시를 직접 그려보면, 두가지를 신경써서 구현해야 함을 알 수 있다. M번째 수가 몇 번째로 큰 중요도를 갖는가 → deque의 0번째 원소가 max인지 확인 M의 중요도와 같은 중요도가 있는가 → count변수로 해결 💡 코드 f..