스위핑5 [자바] 백준 2836 - 수상 택시 (java) 목차문제 : boj2836 필요 알고리즘정렬, 스위핑사실 그냥 정렬 + 반복문 + 조건문만 알면 풀 수 있다. 아이디어가 더 중요한 문제다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아이디어만 잘 떠올리면 풀 수 있는 문제이다. 내 경우 이하와 같이 진행했다. 어차피 0부터 M까진 무조건 가야 한다. 따라서 입력값에서 타는 위치가 목적지보다 이전이라면, 사실 신경을 안써도 .. 2024. 4. 24. [자바] 백준 23740 - 버스 노선 개편하기 (java) 목차 문제 : boj23740 필요 알고리즘 정렬, 스위핑 스위핑을 통해 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 겹친다는 부분을 어떻게 알 수 있을까? 노선A의 e가 노선 B의 s 이상이고, 노선 B의 e가 노선 A의 s 이상이라면 겹친다고 볼 수 있을 것이다. 이 때, 무조건 s가 증가하는 순서대로 정렬해두고 확인해본다고 해보자. s가 더 작은 쪽이 노선 A라고 한다면 이후 겹친다는 판단.. 2023. 4. 8. [자바] 백준 18251 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) (java) 문제 : boj18251 필요 알고리즘 개념 스위핑 문제를 단순화 시키면 사실 여러번의 스위핑을 통해 풀 수 있는 문제이다. 다만 이건 내 경우이고, 이 문제는 DP 등 다른 풀이들도 있다. 내가 푼 방식은 스위핑을 이용한 풀이이므로 그걸로 해설을 진행한다. bfs (너비 우선 탐색) 내 경우 트리의 루트부터 주어진 가중치들을 스위핑을 하기 위해 위치 순서대로 정렬하려고 bfs를 사용했다. 꼭 필요한 방식은 아니고, 이 역시 다양한 방식으로 가능하다. 혹시 bfs를 모른다면 이 글을 참고하자. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백.. 2022. 9. 6. 백준 5419 자바 - 북서풍 (boj 5419 java) 문제 : boj5419 1. 일단 모든 쌍을 직접 확인해보자! (brute force) n개의 정점 모두에 대해 모든 쌍을 확인하면서 조건을 만족하는지 확인해보면 된다. 이 경우 코드는 아래와 같이 될 것이다. 물론 이대론 O(N^2)이 되므로 시간 내에 통과할 수 없다! 어쨌든 어떠한 점이 자신보다 x가 작거나 같고, y가 크거나 같은지 확인하면 될 것임을 알 수 있다. ArrayList arr = new ArrayList(); void add(Island island) { arr.add(island); } long getAnswer() { long cnt = 0; for (int i = 0; i < arr.size(); i++) { for (int j = i+1; j < arr.size(); j++).. 2022. 3. 31. 백준 2170 자바 - 선 긋기 (boj 2170 java) 문제 : boj2170 당연히 전체 위치를 보게되면 -10억부터 +10억까지 봐야하므로 시간초과가 뜬다. 최대 100만개인 N을 기준으로 동작할 방법을 찾아야 한다. 문제에서 제시된 '예제 입력 1'은 이미 그렇게 정렬된 데이터긴 하지만, N개를 전부 x를 기준으로 오름차순으로 정렬했다고 생각하고 어떻게 풀지 한번 생각해보자. 4 1 3 2 5 3 5 6 7 그렇다면 위와 같이 x값 기준 오름차순으로 차례대로 확인할 경우(x값이 동일할 경우 y값 순서는 상관 없음. 그나마 내림차순으로 하면 아주 약간의 대입연산 정도는 줄여볼 수 있는데 의미 없음), 이전 y 값보다 현재의 x값이 작거나 같다면 이어진 항목으로 생각해볼 수 있다. 1-3을 본 후, 2-5를 보자. 현재 보고 있는 x인 2는 이전의 y값인 .. 2022. 3. 30. 이전 1 다음
