Algorithm
[백준] 13702 이상한 술집 - Java
[백준] 13702 이상한 술집 - Java
2022.05.06매개 변수 탐색을 활용해 풀 수 있는 문제이다. 0으로 나눠지는 경우 / int가 아니라 long으로 설정해야 함 위 두 가지만 신경쓰면 쉽게 해결할 수 있다. import java.util.*; import java.io.*; public class Main { static int N; static int K; static int max = Integer.MIN_VALUE; static int[] liter; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringT..
[백준] 2343 기타 레슨- Java
[백준] 2343 기타 레슨- Java
2022.05.05매개변수 탐색을 통해 풀 수 있는 문제이다. 이분탐색을 수행할 때 최솟값을 구하는 경우이므로 최댓값을 구하는 경우와 헷갈리지 말자. import java.util.*; import java.io.*; public class Main { static int N; static int M; static int[] lecture; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.n..
[백준] 2512 예산 - Java
[백준] 2512 예산 - Java
2022.05.05매개 변수 탐색을 활용해 풀 수 있는 문제이다. 입력으로 들어온 예산들 사이에서 답을 구할 수 있으니, 0 ~ 최대 예산에 대해서 이분 탐색을 수행해 빠르게 답을 구하자. import java.util.*; import java.io.*; public class Main { static int N; static int M; static int[] money; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); money = new int[N+1]; Str..
[백준] 1654 랜선 자르기 - Java
[백준] 1654 랜선 자르기 - Java
2022.05.05매개 변수 탐색을 활용해 풀 수 있는 문제이다. 만들 수 있는 최대 랜선의 길이를 구하시오. => 특정 길이로 잘랐을 때 N개보다 많은 랜선을 얻을 수 있는가? 각 랜선의 길이는 정수 범위 안에서 결정된다. 랜선을 자르고 답을 갱신하다 보면 정수 범위를 초과할 수도 있을 것 같다. long타입으로 설정하고 풀자. import java.util.*; import java.io.*; public class Main { static int N; static int K; static int LAN[]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRead..
[백준] 3273 두 수의 합 - Java
[백준] 3273 두 수의 합 - Java
2022.05.05이분 탐색을 활용해 빠르게 찾자 import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] arr = new int[N+1]; StringTokenizer st = new StringTokenizer(br.readLine()); for(int i=1; i
[백준] 2110 공유기 설치 - Java
[백준] 2110 공유기 설치 - Java
2022.05.04매개 변수 탐색을 활용해서 풀 수 있는 문제이다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 최대 거리를 구하시오. => 두 공유기 사이의 최대 거리를 적당히 설정했을 때 C개의 공유기를 설치할 수 있는지 구하시오. 공유기 C개를 설치할 수 있는지에 대한 확인은 그리디 느낌으로 일단 싹다 설치해놓고 C이상이면 true, 아니면 false를 반환하도록 작성했다. 매개 변수 탐색은 이분 탐색을 기반으로 함을 잊지 말자. import java.util.*; import java.io.*; public class Main{ static int N; static int C; static int[] Home; public static void main(String[] args) t..
매개 변수 탐색
매개 변수 탐색
2022.05.04이분 탐색을 응용한 알고리즘이다. 어떤 배열이 0과 1로만 구성되어있고, 이 배열이 정렬된 상태라고 생각해 보자. 0과 1의 경계를 찾으려면 어떻게 해야 할까? 인덱스 0부터 시작해서 순차적으로 탐색해 경계를 찾는 방법도 있지만, 딱 봐도 효율적이지 않다. 지난번에 배웠던 이분 탐색을 이 문제에 적용해보자. L = 배열의 시작, R = 배열의 끝 으로 설정하고 이분 탐색을 수행하면 순차 탐색보다 훨씬 효율적으로 탐색할 수 있다. 이를 매개 변수 탐색이라고 하는데, 특정 문제에서 유용하게 사용될 수 있다. 1. 정답을 매개 변수로 만들고, 주어진 문제를 예 / 아니오 로 결정할 수 있는 문제로 바꿔 보자. 2. 배열이 정렬된 상태인가? 두 가지 조건이 성립한다면 매개 변수 탐색으로 해결할 수 있는 문제이다..
[백준] 2805 나무 자르기 - Java
[백준] 2805 나무 자르기 - Java
2022.05.04매개 변수 탐색을 활용해 풀 수 있는 문제이다. 알고리즘 분류에 매개 변수 탐색이라고 나와있어서 쉽게 찾을 수 있지만.. 어떤 문제를 매개 변수 탐색으로 풀 수 있는지, 어떤 경우에 매개 변수 탐색이 효율적인지 알아두자. 매개 변수 탐색을 활용하기 위해 문제를 적절하게 변형하자. 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구해라. => 절단기에 특정 높이를 설정했을 때 적어도 M미터의 나무를 집에 가져갈 수 있는가? import java.util.*; import java.io.*; public class Main{ static int N; static int M; static int[] tree; public static void main(String[] ar..
[백준] 2470 두 용액 - Java
[백준] 2470 두 용액 - Java
2022.05.04해당하는 용액을 빠르게 찾아야 한다. 먼저 이분 탐색을 활용해 풀어보자. 용액의 특성값 합이 0에 가장 가까워야 한다. 용액에 대해 오름차순으로 정렬을 수행한 후, target을 -arr[i]로 설정하고 이분 탐색을 진행하자. 1. target이 특성값 배열의 최댓값보다 크면 R + 1을 반환한다. 2. 1의 경우가 아니면 target과 가장 근접한 요소의 인덱스를 반환한다. 이진 탐색 코드는 자주 사용되니, 정형화된 스타일을 익혀 두자. import java.util.*; import java.io.*; public class Mabn{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedRe..
[백준] 7795 먹을 것인가 먹힐 것인가 - Java
[백준] 7795 먹을 것인가 먹힐 것인가 - Java
2022.05.04원소를 하나하나 비교하고 있으면 시간 초과가 날 게 뻔하다. 이분 탐색을 통해 빠르게 비교하자. 이분 탐색을 할 때 배열의 인덱스에 주의하자. 0부터 시작하는 것 보다 1부터 시작하도록 조작한 후 이분 탐색을 수행했을 때 실수를 줄일 수 있더라... import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); StringTokenizer st; for(int..
정렬 기본 - Java
정렬 기본 - Java
2022.05.03자바에서 정렬을 수행할 때는 Integer, char과 같은 Primitive 원소에 대해서는 Dual-Pivot Quick Sort를 사용하고, 객체를 정렬할 때는 Tim Sort를 사용한다. (내부 함수 사용 시) 왜 객체와 객체가 아닌 것에 대해 따로 정렬을 수행할까? 한 가지 방법으로 통일하면 일관성을 유지할 수 있어 이해하기 쉽지 않을까? 이 질문에 대해 답하기 위해서는 In-place와 Stable여부를 알아야 한다. 정렬 알고리즘이 In-place하다면, 정렬 과정에서 정렬을 수행하는 N에 비해 무시할 만한 개수의 메모리만 사용함을 의미한다. 정렬할 요소의 수가 10만개이고, 10만개의 요소를 정렬할 때 추가로 사용해야하는 메모리가 10이라면 무시할 만 하다고 할 수 있다. 다음으로, 정렬 ..
[백준] 1182 부분수열의 합 - Java
[백준] 1182 부분수열의 합 - Java
2022.05.02재귀함수를 사용해 백트래킹을 구현해서 풀 수 있는 문제이다. 백트래킹 알고리즘에서 가장 중요한 부분은 재귀함수의 올바른 정의이다. 재귀함수와 반복문잉 본직적인 차이가 없음을 이해하고 재귀함수를 정의하자.. 재귀적 스타일에 익숙해 지는 게 중요하다. 종료 조건 명시해두고, 인덱스를 하나씩 늘려 가며 "이렇게 작성하면 모든 경우를 셀 수 있겠다." 라는 믿음을 가지자. import java.util.*; import java.io.*; public class Main { static int N; static int S; static int ans; static int arr[]; public static void main(String[] args) throws IOException { BufferedRead..