알고리즘/그리디12 [백준 13334] 철로 / 자바 / 라인스위핑 ** #문제 레벨: G2알고리즘: 라인 스위핑 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/13334#문제 풀이 라인 스위핑 을 직역하면 싹스리 하는 이라는 뜻이다. 한 마디로 한 쪽 방향으로 정렬된 직선을 스캔하며 정해진 기준에 따라 답을 업데이트 하는 것이다. 그리드 알고리즘의 종류라고 생각하면 된다.이 문제는 끝점을 기준으로 오름차순 정렬한다. 놓아야 하는 직선 L을 정렬된 끝점에 맞추어 계속해서 대보는 것이다. 기준에 부합하면 시작점을 큐에 넣고 L보다 튀어나온 큐에 있는 시작점들은 Poll 해준다. 간단하지 않은가? +라인스위핑 문제느 변수를 사용해서 답을 관리하는 것보다 우선순위 큐의 사이즈로 관리하는 것이 용이하다.!!!!.. 2024. 8. 28. [백준 1700] 멀티탭 스케줄링 / 자바 / 그리드 #문제 레벨: G1알고리즘: 그리드 풀이시간: 30분힌트 참조 유무:https://www.acmicpc.net/problem/1700#문제 풀이 이 문제는 순서대로 조건에 맞게 하나 씩 콘센트를 빼고 꽂는다 하여 그리드 문제이다. 그리드는 지금까지 탐색한 것들을 토대로 풀어나간다 라는 생각이 있어서 이 방식도 그리드인줄 몰랐다. 그래서 이 방식이 뭐냐? 꽂을려는 콘센트가 이미 꽂혀있는 경우는 skip하고 구멍이 넉넉한 경우에도 꽂아주고 skip한다. 신경써줘야 할 부분은 구멍이 다 꽂혀있을 경우인데 콘센트를 뽑을지는 가장 뒤늦게 다시 나오는 콘센트를 뽑는 거다. 그러기 위해서는 앞이 아닌 뒤를 탐색해야 한다. 이번 문제를 통해서 그리드 개념을 다시 세웠다. 현재까지 탐색한 것을 .. 2024. 8. 10. [백준 12904] A와 B / 자바 / 그리드 문제 레벨: G4알고리즘: 그리드 풀이시간: 30분힌트 참조 유무: 무https://www.acmicpc.net/problem/129041 번째 시도 [로직 설명]T에 룰을 거꾸로 적용해서 하나씩 빼주고 마지막에 비교한다.[배운점]String 함수 되짚기import org.w3c.dom.Node;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;public class Main { public static void main(String[] args) throws IOException .. 2024. 6. 23. [백준 1744] 수 묶기 / 자바 / 그리디 문제 레벨: G4알고리즘: 그리디 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/17441 번째 시도 [아이디어]정렬된 마이너스 배열정렬된 플러스 배열마이너스 x 마이너스 후 정답에 더하기플러스 x 플러스 후 정답에 더하기+ 예외생각) 1x1보다는 +1+1이 더 높으니 현재 숫자가 1일때는 다음 숫자가 1인지 검사하기import java.io.*;import java.util.*;public class Main { static int N; //양수 관련 값 저장, 내림차순 정렬 static PriorityQueue plus = new PriorityQueue(Comparator.reverseOrder()); //음수 관.. 2024. 6. 22. [백준 1339번] 단어 수학 / 자바 / 그리디 ** 문제 레벨: G4알고리즘: 그리디풀이시간: 50분힌트 참조 유무: 유(아이디어 참조)https://www.acmicpc.net/problem/1339 1 번째 시도 [알고리즘 선택 과정]입력 제한을 보니 DFS도 가능하다.그러나 Greedy문제이기 때문에 Greedy로 풀어보겠다. [Greedy란?]탐욕적 알고리즘이라고도 불린다.현재의 단계에서 최적을 선택해 마지막의 최적의 정답을 도출한다는 아이디어이다.근시안적으로 현재만 보고 선택하는 것이 탐욕적 알고리즘이라고 불리는 게 어울린다. [Greedy 과정]알파벳이 주어진 순대로 탐색할 것이다. 납득이 가는 과정일 것이다. 그렇다면 어떨 때 알파벳의 숫자를 바꿔줘야 할까?새로운 알파벳이 해당 숫자의 알파벳보다 자릿수가 높을 때 숫자를 바.. 2024. 6. 3. 항해99 32일차 TIL(강의실 배정 / 백준) 문제 레벨: G5알고리즘: 그리디풀이시간: 1시간힌트 참조 유무: 무https://www.acmicpc.net/problem/110001 번째 시도 끝나는 시간으로 정렬 현재 인덱스 끝나는 시간이 다음 인덱스 시작 시간보다 크다면 answer++ 방의 개수를 새는 자료구조 고민 min변수에 방 최소 개수 담고 우선순위에큐에 끝나는 시간 담기 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 5. 1. 항해99 31일차 TIL( 저울 /백준) 문제 레벨: G2알고리즘: 그리디 풀이시간: 1시간힌트 참조 유무: 유<a href="https://www.acmicpc.net/problem/2437" target="_blank" rel="noopener norefer.. 2024. 4. 30. [백준] 보석 도둑 /자바 문제 https://www.acmicpc.net/problem/1202레벨: G2알고리즘: 그리드 풀이시간: 40분힌트 참조 유무: 무1 번째 시도 보석의 가격으로 정렬해야 하나? 보석의 무게로 정렬해야 하나?가격으로 정렬 후 가방 순회하며 담을 수 있는 지 판단자료구조 고민 현재 가방에서 선택할 수 있는 보석을 우선순위큐에 넣기 우선순위 큐를 보석의 값으로 내림차순 정렬가장 보석의 값이 큰 거 하나 선택이 과정을 가방의 개수 만큼 반복import java.util.*; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); .. 2024. 4. 29. [백준] 카드 정렬하기 / 자바 문제 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 2 다음
