Cute Hello Kitty Kaoani

Algorithm/Problem Solving

Algorithm/Problem Solving

[BOJ] 2468. 안전영역 - JAVA 자바

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 💡 DFS 비 내리는 양에 따라 나뉜 영역 개수를 찾고 그 중 가장 많은 영역을 가질 수 있는 경우를 구하면 되는 문제이다. (0,0)부터 상하좌우로 탐색하며 방문 체크하는 구조로 DFS를 이용했다. max_rain : 비가 올 수 있는 최대 ( 지역의 높이 중 가장 큰 높이 ) 비 내리는 양을 하나씩 증가시키며 나뉜 영역 중 최대 구하기 비 양에 따른 물에 잠긴 구역 체크 full() 이중 for문을 돌며 물에 잠기지 않은 구역 탐색 safe_area() 물에 잠기지..

Algorithm/Problem Solving

[BOJ] 2075번 N번째 큰 수 - JAVA(자바)

💡 PriorityQueue 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 우선순위 큐를 구현하는 방식인 힙(Heap)에서 데이터를 넣었다가 꺼내는 작업은 정렬하는 작업과 동일하다. 이 경우 시간복잡도는 O(NlogN)이 된다. 따라서 순서 상관없이 주어진 데이터를 우선순위 큐에 넣기만 하면 루트노드는 가장 우선순위가 큰 값을 가지고 먼저 제거된다. 문제에서는 N번째로 큰 수를 찾는 문제로 Collections.reverseOrder()메서드를 활용하여 높은 숫자가 우선순위가 될 수 있도록 한다. import ja..

Algorithm/Problem Solving

[BOJ] 2110번 공유기 설치 - JAVA(자바)

2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 💡 이진탐색(Binary Search) 문제 구하고자 하는 것 : 두 공유기 사이의 최대거리 lt = 1 rt = arr[n-1] ➜ 너무 세세하게 생각X. 그냥 가장 멀리있는 좌표 선택 ➜ 답(두 공유기의 최대거리)은 lt~rt 사이에 확실하게 있다. mid = (lt + rt ) / 2 가장 인접한 두 공유기의 거리를 mid라고 했을 때, 답이 가능한지 검증 ➜ 공유기의 배치 수를 count하는 함수 생성 ..

Algorithm/Problem Solving

[BOJ] 1654번 랜선 자르기 - JAVA(자바)

💡 이분탐색(Binary Search) 문제 ✅ 구하고자 하는 것 : N개를 만들 수 있는 랜선 최대 길이lt = 1rt = 랜선 길이 중 가장 긴 값  ➜ lt ~ rt 사이의 구하고자 하는 값이 확실하게 있다.자를 랜선의 길이가 mid이면 답으로써 가능한 숫자인가 검증 ➜ 얻을 수 있는 랜선의 개수를 구하는 함수 생성얻을 수 있는 랜선의 개수가 N개 보다 크거나 같으면 자를 랜선의 길이를 늘려도 됨 lt=mid+1반대면 랜선의 길이 줄이기 rt=mid-1👨🏻‍💻 실행코드import java.util.*;import java.io.*;public class Main { private static BufferedReader br = new BufferedReader(new InputStrea..

Algorithm/Problem Solving

[BOJ] 2805번 나무 자르기 - JAVA(자바)

2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 💡 이진탐색(Binary Search) 이진탐색으로 해결할 수 있는 문제들의 유형은 비슷하다. lt와 rt를 정하고 lt ~ rt 사이에 찾고싶은 답이 분명히 있다라는 확신이 있는 문제에 적용한다 + 최대/최소 구하고자 하는 것 : 절단기를 설정할 수 있는 높이의 최대값 lt = 0 : 절단기에 설정할 수 있는 가장 작은 값 rt : 나무의 길이 중 가장 긴 값 ➜ lt ~ rt 사이의 구하고자 하는 값이 확실하게 있다. ..

Algorithm/Problem Solving

[BOJ] 10825번 국영수 - JAVA(자바)

10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 단순히 이중 for문으로 해결하면 시간초과 뜨는 문제다. 그리디 알고리즘 할 때 배웠던 Comparable 인터페이스를 이용해 해결하였다. Comparable에서 compareTo는 정렬하는 기준을 잡아주는 메서드이다. public int compareTo(Grade o) { /* 국어 점수기준으로 내림차순 정렬. 값이 같다면 영어점수 기준으로 * 오름차순 같다면 수학점수 기준으로 내림차순. 마지막 이름 사전식 정렬 */ if (this.ko..

Algorithm/Problem Solving

[BOJ] 1002번 터렛 - JAVA(자바)

1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 $-1$ 출력한다. www.acmicpc.net 문제에서 두 좌표와 각각의 거리가 주어져 원을 그릴 수 있다. 그 원이 바로 문제에서 말하는 사람이 있을 수 있는 위치이다. 사람이 있을 수 있는 위치가 무한대인 경우는 두 좌표가 일치하고, 원의 크기가 같을 때 사람이 있을 수 있는 위치가 한 곳인 경우는 두 원이 내접, 외접하는 경우이다. 두 원의 반지름 차 == 두 좌표의 거리 or 두 원의 반지름 합 == 두 좌표의 거리 사람이 있을 수 있는 위치가 두 곳인 경우는 두 원이 두 점에서 만나는 경우이다. 두 원의 반지름 차 < 두 좌표의 거리 < 두 원의 반..

Algorithm/Problem Solving

[BOJ] 2960번 에라토스테네스의 체 - JAVA(자바)

2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 이젠 자신있는 소수 문제 💪💪 에라토스테네스의 체는 소수를 빠르게 판별할 수 있는 알고리즘으로 원래의 에라토스테네스의 체는 소수의 배수만 지우는 구조로 구현되는데 이 문제는 소수까지 지우는 것으로 해결해야된다. 지워진 숫자는 continue 를 통해 넘어갈 수 있어 소수를 구하는데 있어 효율적인 방식이다. import java.util.*; class Main { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int k =..