우선순위 큐4 [백준 13334] 철로 / 자바 / 라인스위핑 ** #문제 레벨: G2알고리즘: 라인 스위핑 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/13334#문제 풀이 라인 스위핑 을 직역하면 싹스리 하는 이라는 뜻이다. 한 마디로 한 쪽 방향으로 정렬된 직선을 스캔하며 정해진 기준에 따라 답을 업데이트 하는 것이다. 그리드 알고리즘의 종류라고 생각하면 된다.이 문제는 끝점을 기준으로 오름차순 정렬한다. 놓아야 하는 직선 L을 정렬된 끝점에 맞추어 계속해서 대보는 것이다. 기준에 부합하면 시작점을 큐에 넣고 L보다 튀어나온 큐에 있는 시작점들은 Poll 해준다. 간단하지 않은가? +라인스위핑 문제느 변수를 사용해서 답을 관리하는 것보다 우선순위 큐의 사이즈로 관리하는 것이 용이하다.!!!!.. 2024. 8. 28. [백준 1655] 가운데를 말해요 / 자바 / 우선순위 큐 #문제 레벨: G2알고리즘: 자료구조 (우선순위 큐)풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/1655#문제 풀이 이 문제를 봤을 때 한 번에 떠올리는 아이디어로 한다면 시간초과가 날 것이다. 입력을 받을 때마다 정렬을 하고 중간값을 찾는 다는 생각은 오답이다. 배열 정렬의 최선의 시간복잡도는 O(n)이고 최악은 O(n^2)이다. 그래서 우리는 더 나은 정렬된 자료구조를 사용해야 한다. 그건 정렬의 특화된 우선순위 큐이다. 우선순위 큐 정렬(Heap정렬 사용)의 시간복잡도는 O(logn)이다.아이디어는 이러하다. 중간값보다 낮은 숫자들을 담을 maxHeap과 중간값보다 높은 숫자들을 담을 minHeap을 생성한다. maxHeap은.. 2024. 7. 20. [백준] 아기상어 / 자바 문제 레벨: G3알고리즘: 풀이시간: 12:34힌트 참조 유무:https://www.acmicpc.net/problem/162361 번째 시도: 실패 [알고리즘 선택 사고 과정]먹을 수 있는 것들을 다 먹어야 함(배열 탐색)먹을 수 있는 것에서 갈 때에는 최소한의 거리로 가야 함 -> BFS 선택되게 간단히 알고리즘 선택했다 [풀이 과정]반복문상어가 먹을 수 있는 것을 찾을 때까지 탐색(BFS)한다.만약 먹을 것이 없다면 반복문을 종료하고 답을 반환한다.자세한 건 주석 참조 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;i.. 2024. 5. 25. [백준] 카드 정렬하기 / 자바 문제 https://www.acmicpc.net/problem/1715레벨: G4알고리즘: 그리드풀이시간: 1시간힌트 참조 유무: 무1 번째 시도 오름차순 정렬 필요두가지 생각이 들었습니다. 정렬 후1. 두 묶음씩 묶어서 계속 더해가며 줄일 것인가2. 1 번째와 2 번째만 계속 더해가며 줄일 것인가예시를 들어 비교1 3 5 10 4 + 15 + 4 + 15 = 38 4 + 4+5 + 9 +10 =32 결론: 2 번째 방법 선택 // 3, 5킬로그램 봉지가 있다.// 최대한 5킬로그램 봉지를 많이 들고가야 한다.// 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.import java.util.*;import java.io.*;class Main { public static v.. 2024. 4. 29. 이전 1 다음
