📙 Algorithm Solving/Java
📙[Algo] 24.02.07 알고리즘
혜덕hyeduck
2024. 2. 9. 20:51
알고리즘 문제) BOJ 1300. K번째 수
문제 요약
- N*N 배열 A
- A[i][j] = i*j
- 해당 수를 일차원 배열 B에 담고 오름차순 정렬했을 때 B[k]는?
- B의 크기 = N*N
- 인덱스는 A,B둘다 1부터 시작
시간 제한
- 2초
입력
- 배열의 크기 N
- N : 10만이하 자연수
- k
- min(10억, N*N)보다 작거나 같은 자연수
출력
- B[k]
접근법
- 완전 탐색으로 생각하기
- 직접 2차원 배열 A를 선언하고, ⇒ 10만*10만
- 해당 배열을 1차원 배열 B에 담고, 오름차순 정렬후 B[K]값 찾기
- 최적화하기
- N = 3, K = 7
1 2 3
2 4 6
3 6 9 - A[k] = x ⇒ x보다 작거나 같은 게 최소 K 개
- 만약, A[7] = x ⇒ x보다 작거나 같은 게 최소 7
- 1~9 의 중간값 5보다 작거나 같은거 개수 ⇒ 6개 ⇒ 개수가 적으므로 s=mid+1
6~9 의 중간값 7보다 작거나 같은거 개수 ⇒ 8개 ⇒ 개수가 크므로 e=mid-1
6~6의 중간값 6보다 작거나 같은거 개수 ⇒ 7개(최소 개수 기준) - 개수 구하는거에서 시간 초과뜨는걸 해결해야 하는데,,,,
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16- 10 보다 작거나 같은거 개수 구하기(13개….)
⇒ 1의배수:10개4개, 2의배수:5개4개, 3의배수 : 3개, 4의배수 : 2개 - ⇒ 가로 방향으로 봤을 때, 10 / i의 개수만큼 더하되, N값을 넘으면 안됨. 따라서 Math.min(mid/i, N)
- 10 보다 작거나 같은거 개수 구하기(13개….)
- N = 3, K = 7
코드
import java.io.*;
public class Main {
static int N, K;
static int binarySearch(int s, int e) {
int mid, cnt, answer = -1;
while (s <= e) {
mid = (s + e) / 2;
cnt = 0;
for (int i = 1; i <= N; i++) {
cnt += Math.min(mid / i, N);
}
// System.out.println(s + ", " + e + ", " + mid + ", " + cnt);
if (cnt < K) {
s = mid + 1;
} else if (cnt >= K) {
answer = mid;
e = mid - 1;
}
}
return answer;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
K = Integer.parseInt(br.readLine());
bw.write(String.valueOf( binarySearch(1, K)));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 20033. Square, Not Rectangle
문제 요약
- 히스토그램은 공통된 기준선을 공유하는 N개의 인접한 직사각형으로 구성된 도형
- 각 직각형의 너비는 1, 높이는 Hi
시간 제한
- 1.5초
입력
- 정수 N
- 1≤N≤300,000
- N개의 정수 H1… Hm
- 1≤Hi≤10억
출력
- 히스토그램 기준선에 평행한 한쪽 면을 가진 가장 큰 정사각형의 변의 길이 출력
접근법
- 완전탐색으로 접근하기
- 변의길이 1~ Hm최대값까지 정사각형을 만들 수 있는 경우를 모드 찾고 가장 큰 정사각형 변의 길이로 갱신하기
- 최적화하기
- 이분탐색으로 변의 길이를 고정시킨 상태에서(mid)
- 정사각형을 만들 수 있는지 체크해야하는데, 이것은 for문을 통해서 H1~Hn까지 변의 길이가 mid값인 정사각형이 가능한지 체크하기
- 만약 가능하면 변의 길이 최대값으로 갱신
- 변의 길이를 늘려야 하니까 s = mid +1;
- 불가능하면 변의 길이를 줄여야 하니까 e = mid-1;
- 이분탐색으로 변의 길이를 고정시킨 상태에서(mid)
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[] polls;
static long answer = 1;
static int maxH = 1;
static void binarySearch(long s, long e) {
long mid;
boolean isAble;
int cnt;
while (s <= e) {
mid = (s + e) / 2;
isAble = false;
cnt = 0;
for (int i = 0; i < N; i++) {
if(polls[i] >= mid){
cnt++;
if (cnt == mid) {
isAble = true;
break;
}
} else{ cnt = 0;}
}
if (isAble) {
s = mid + 1;
answer = Math.max(answer, mid);
} else {
e = mid - 1;
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
polls = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
polls[i] = Integer.parseInt(st.nextToken());
maxH = Math.max(maxH, polls[i]);
}
binarySearch(1, maxH);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 12991. 홍준이의 행렬
문제 요약
- 길이가 N인 수열 A, B
- N*N크기 행렬을 만들 때
- 행렬 (i,j) 원소는 수열 A의 i번째 원소와 B의 j번째 원소의 곱으로 정의
- 그리고 이 행렬 원소를 모두 정렬
- 정렬된 결과에서 k번째 위치한 값 구하기(1번부터 계싼)
시간 제한
- 2초
입력
- N 과 K
- 1≤N≤30000
- 1≤K≤N*N
- 수열 A의 원소
- 수열 B의 원소
- 각 원소는 1이상 10억 이하 자연수
출력
- N^2크기 행렬에서 K번째로 작은 값 출력
접근법
- 완전 탐색으로 접근하기
- 직접 NN행렬을 만들경우, 3000030000 ⇒ 9억연산 ⇒ 시간초과\
- 최적화
- N = 4 K=9
A : 1 5 8 9
B : 2 6 7 10 - N*N 행렬의 원소는 A와 B의 원소끼리 곱한 것들을 오름차순 정렬 한 것과 같다..
- [2, 6, 7, 10, 10, 16, 18, 30, 35, 48, 50, 54, 56, 63, 80, 90]
- K번째 수랑 문제가 비슷하다고 생각했는데,,,,
- arr[K]=x : x보다 작거나 같은 수가 K개
- 여기서는 개수를 어떻게 구해야 하지..ㅠㅠ
- 1 * min(2) : 2
1 * max(10) : 10
5 * min(2) : 10
5 * max(10) : 50
8 * min(2) : 16
8 * max(10) : 80
9 * min(2) : 18
9 * max(10) : 90 - 개수도 이분탐색으로 구할 수 있을까..?
- for문 i=1~N-1(A배열 기준)
- s=0, e=N-1, target = x(위에서 구한 mid값)
- upperbound(x)-1이용해서 개수 구하기
- s=0, e=N-1, target = x(위에서 구한 mid값)
- for문 i=1~N-1(A배열 기준)
- N = 4 K=9
코드
- 데이터 타입 크기 주의하기 ⇒ 중간에 더해지고 곱해지면서 int범위 벗어날 수 있음!!!
import java.io.*;
import java.util.StringTokenizer;
import java.util.Arrays;
public class Main {
static int N, K;
static int[] A;
static int[] B;
static long answer;
// 나보다 큰 값중 가장 왼쪽에 있는 것의 인덱스
static int upperbound(int s, int e, long target, int mul) {
int answer = N;
int mid;
while (s <= e) {
mid = (s + e) / 2;
if ((long)B[mid] * mul > target) {
answer = mid;
e = mid - 1;
} else {
s = mid + 1;
}
}
return answer;
}
static void binarySearch(long s, long e) {
long mid;
int cnt;
while (s <= e) {
mid = (s + e) / 2;
cnt = 0;
for (int i = 0; i < N; i++) {
cnt += upperbound(0, N - 1, mid, A[i]);
}
if (cnt < K) {
s = mid + 1;
} else {
e = mid - 1;
answer = mid;
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
A = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
B = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
B[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(A);
Arrays.sort(B);
binarySearch((long)A[0] * B[0], (long)A[N - 1] * B[N - 1]);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 8983. 사냥꾼
문제 요약
- N마리의 동물
- M개의 사대에서만 사격이 가능
- 각 동물의 위치
- (a1,b1) .. (aN,bN) 양의 정수
- 총의 사적 거리가 L이라고 할 때, L보다 작거나 같은 위치의 동물들만 잡음
- 사대위치 ~ 동물 거리 = abs(xi-aj) + bj
- 잡을 수 있는 동물의 수는?
시간 제한
- 1초
입력
- 사대의 수 M, 동물의 수 N, 사정거리 L
- 1≤M≤10만
- 1≤ N≤10만
- 1≤L≤10억
- 사대의 위치를 나타내는 M개의 x-좌표 값
- N개의 줄에 동물의 좌표값 x, y
- 모든 좌표값은 10억보다 작거나 같은 양수
출력
- 동물의 수
접근법
- 완전 탐색으로 생각하기
- 사대별로 모든 동물의 좌표와 비교하면서 잡을 수 있는 동물 수 카운트
- ⇒ M*N으로 시간초과
- 최적화 하기
- for문을 한 번만 사용 가능하다.
- 좌표를 중심으로 본다면..?
- 사대 위치 : 1 4 6 9
- 좌표 (7,2)
- s=0, e=3, mid=1 ⇒ arr[1] : 4
- 거리 = 3 + 2 = 5 > L(4)
- 사정 거리 밖이므로 좀 더 가까운 사대로 이동해야 한다.
- 현재 좌표 x > 사대 위치 arr[1] 이므로 s = mid +1
- s=2, e=3, mid=2 ⇒ arr[2] : 6
- 거리 = 1+2 < L(4)
- 사정거리 안이므로 가능! cnt = 1
- s = mid +1
- s=3, e=3, mid=3 ⇒ arr[3] : 9
- 거리 = 2+2 = L(4)
- 사정거리 안이므로 가능! 하지만 이미 카운트 했기 때문에 X
- s = mid +1 ⇒ s>e이므로 끝..
- s=0, e=3, mid=1 ⇒ arr[1] : 4
binarySearch 메소드 반환값으로 true,false를 하고 true일 경우 카운트 올리는 식으로 하자!
코드
import java.awt.image.BandedSampleModel;
import java.io.*;
import java.util.*;
public class Main {
static int M, N, L; // 사대의 수, 동물의 수, 사정거리
static int[] gun; // 사대 위치
static int[][] animals; // 동물 위치
static boolean binarySearch(int x, int y) {
int s = 0, e = M - 1, mid, dist;
while (s <= e) {
mid = (s + e) / 2;
dist = Math.abs(x - gun[mid]) + y;
if (dist > L) {
if (x > gun[mid]) s = mid + 1;
else e = mid - 1;
} else {
return true;
}
}
return false;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
gun = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
gun[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(gun);
animals = new int[N][2];
int cnt = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
animals[i][0] = Integer.parseInt(st.nextToken());
animals[i][1] = Integer.parseInt(st.nextToken());
if(binarySearch(animals[i][0], animals[i][1])) cnt++;
}
bw.write(String.valueOf(cnt));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 2512. 예산
문제 요약
- 정해진 총액 이하에서 가능한 한 최대의 총 예산 배정
- 모든 요청이 배정될 수 있다면 요청한 금액 그대로 배정
- 그럴 수 없다면, 특정 정수 상한액을 계산하여 그 이상인 요청에는 해당 상한액 만큼만 배정. 이하의 경우 요청 금액 배정
- 위의 조건을 모두 만족하도록 예산 배정하기(최댓값 출력)
시간 제한
- 1초
입력
- 지방의 수 N
- 3≤N≤1만
- 요청 예산 N개가 빈칸으로 주어짐
- 1≤예산≤10만
- 총 예산 M
- N ≤ M ≤ 10억
출력
- 첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력
접근법
- 150~1의 중간값부터 예산 부여가 가능한지 체크
- 만약 가능하다면 정답값 갱신하고(최댓값으로), s = mid + 1, 아니라면 e = mid -1
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int N, M, max = 0;
static int[] money;
static int answer = 1;
static void binarySearch(int s, int e) {
int mid;
int sum;
while (s <= e) {
mid = (s + e) / 2;
sum = 0;
for (int i = 0; i < N; i++) {
if(money[i] <= mid ) sum += money[i];
else sum += mid;
}
if (sum > M) {
e = mid - 1;
} else {
s = mid + 1;
answer = Math.max(answer, mid);
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
money = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
money[i] = Integer.parseInt(st.nextToken());
max = Math.max(max, money[i]);
}
M = Integer.parseInt(br.readLine());
binarySearch(1, max);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 2776. 암기왕
문제 요약
- 수첩2에 적혀있는 수 순서대로 각각 수첩1에 있다면 1, 없다면 0 출력
시간 제한
- 2초
입력
- 테스트 케이스 T
- 수첩1에 적어놓은 정수의 개수 N
- 1≤N≤100만
- 수첩1에 적힌 N개의 정수들
- 수첩2에 적어놓은 정수의 개수 M
- 1≤M≤100만
- 수첩2에 적힌 M개의 정수들
- 정수들의 범위는 int
출력
- ‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력
코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int T, N, M;
static int[] A;
static int[] B;
static int binarySearch(int s, int e, int target) {
int mid;
while (s <= e) {
mid = (s + e) / 2;
if (target > A[mid]) {
s = mid + 1;
} else if (target < A[mid]) {
e = mid - 1;
} else {
return 1;
}
}
return 0;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
StringTokenizer st;
while (T-- > 0) {
N = Integer.parseInt(br.readLine());
A = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
M = Integer.parseInt(br.readLine());
B = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
B[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(A);
for (int i = 0; i < M; i++) {
sb.append(binarySearch(0, N - 1, B[i])+"\\n");
}
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 2470. 두 용액
문제 요약
- 용액의 특성값을 합쳐 가장 0에 가까운 용액을 만들려고 함
- 이때 두 용액의 특성값을 출력
시간 제한
- 1초
입력
- 전체 용액의 수 N
- 2≤N≤10만
- 용액의 특성값 N개가 빈칸을 두고 주어짐
- -10억 ≤ 특성값 ≤ 10억
- 특성값은 모두 다
출력
- ‘첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int answer = Integer.MAX_VALUE;
static int[] ansValue = new int[2];
static void binarySearch(int s, int e, int key, int[] arr) {
int mid;
while (s <= e) {
mid = (s + e) / 2;
if (key < 0) {
// key가 음수인 경우
if (arr[mid] < 0) {
s = mid + 1;
} else {
if(Math.abs(key) < arr[mid]) e = mid - 1;
else s = mid + 1;
}
} else {
// key가 양수인 경우
if (arr[mid] > 0) {
e = mid -1;
} else {
if(key > Math.abs(arr[mid])) e = mid - 1;
else s = mid + 1;
}
}
if (key != arr[mid] && answer > Math.abs(arr[mid] + key)) {
answer = Math.abs(arr[mid] + key);
ansValue[0] = key;
ansValue[1] = arr[mid];
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] values = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
values[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(values);
for (int i = 0; i < N; i++) {
binarySearch(0, N-1, values[i], values);
}
Arrays.sort(ansValue);
bw.write(String.valueOf(ansValue[0] + " " + ansValue[1]));
bw.flush();
bw.close();
br.close();
}
}