끄적끄적 코딩
article thumbnail
[Java] 백준 2343번 기타 레슨
알고리즘 2023. 8. 8. 20:48

이분 탐색 문제입니다. N개의 강의를 M개 이하의 블루레이로 녹화할 때 최소 길이를 구해야합니다. 길이를 기준으로 이분탐색을 진행해서 가능한 경우를 찾고 가능하다면 더 짧은 길이가 있는지, 불가능 하다면 더 긴 길이를 탐색하게 하였습니다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))..

article thumbnail
[Java] 백준 1034번 램프
알고리즘 2023. 8. 6. 17:06

브루트포스 문제입니다. 행과 열이 주어지고 켜진 전등(1)과 꺼진 전등(0)이 주어집니다. 열의 버튼을 누르면 해당 열에 있는 전등들은 모두 토글됩니다.(0 -> 1, 1-> 0) 행의 모든 전등이 켜져있는것을 켜져있는 행이라고 합니다. 스위치를 적절히 눌렀을 때의 켜진 행의 최댓값을 구해야합니다. 각 행에 0의 개수를 구합니다. 행의 0의 개수가 K보다 많다면 해당 행은 절대 켜질 수 없는 행입니다. 행의 0의 개수와 K의 홀수 짝수가 일치하지 않으면 켤 수 없는 행입니다. 이를 통해 가능한 경우와 불가능한 경우를 구할 수 있습니다. 가능한 행을 구하고, 같은 모양의 행이 있다면 카운트해줘서 가장 많은 카운트를 출력해주었습니다. import java.util.*; import java.io.*; pub..

article thumbnail
[Java] 백준 3649번 로봇 프로젝트
알고리즘 2023. 8. 6. 03:57

이분탐색 문제입니다. 두개의 값의 합이 x가 되는 값을 찾아야합니다. 만약 값이 여러개라면 더 두개의 차의 절댓값이 더 큰 값들을 출력합니다. 이분탐색은 한개의 값을 고정으로 두고 (고정 값) + (이분탐색을 통해 찾는 값) 이 x가 될 수 있는지 찾습니다. 두 값의 합이 x보다 작으면 left = mid + 1 두 값의 합이 x보다 크면 right = mid - 1 두 값의 합이 x와 같다면 절댓값을 비교해서 더 클 경우 결과값에 저장합니다. 이분탐색 자체는 어렵지 않은 문제이지만 테스트 케이스가 여러개로 이루어져있다는 점을 제대로 확인하지 못하여 시간이 많이 걸렸습니다. while ((s = br.readLine()) != null) { } 입력의 시작 부분에 입력이 null이면 종료하도록 해주었습니..

article thumbnail
[Java] 백준 19539번 사과나무
알고리즘 2023. 8. 4. 02:46

그리디 문제입니다. 물뿌리개 2개가 주어집니다. 1. 1의 높이를 올리는 물뿌리개 2. 2의 높이를 올리는 물뿌리개 2개의 물뿌리개를 이용해서 나무의 높이를 주어진 높이로 정확히 맞출 수 있는지 구해야 합니다. 먼저 3으로 나누어 떨어지는지 확인했습니다. 3으로 나누어 떨어지지 않는 경우는 불가능한 경우입니다. 한번에 1과 2를 사용하며, 2의 경우 1을 2개 사용해서 만들 수 있습니다. 1의 경우 2를 이용해서 만들 수 없습니다. 중요한건 1의 개수가 2의 개수보다 많은지 찾으면 됩니다. 최대한 2를 많이 쓰는 방향으로 생각해봅니다. 11 => 2 2 2 2 2 1 10 => 2 2 2 2 2 7 => 2 2 2 1 3 => 2 1 1 => 1 위를 보았을 때 규칙은 1의 개수는 2로 나누어 떨어지지 ..

article thumbnail
[Java] 백준 5557번 1학년
알고리즘 2023. 8. 3. 02:20

다이나믹 프로그래밍 문제입니다. 수열이 주어지고 수열사이에 +, -를 넣어서 마지막으로 주어진 값을 만들면 됩니다. 가능한 경우의 수를 출력해주어야 합니다. * 계산하는 중간에 0보다 작거나 20보다 큰 경우가 생기면 계산하지 않습니다. 첫번째 값을 해당하는 위치에 넣습니다. 두번째~N-1번째는 (배열에 값 + 현재값), (배열에 값 - 현재값)의 위치에 배열에 값을 더해줍니다. index = j + num; if (index = 0) { next[index] += arr[j]; } 전부 더해주었다면 현재 배열을 더해준 배열로 변경합니다. for (int j = 0; j

article thumbnail
[Java] 백준 3079번 입국심사
알고리즘 2023. 8. 2. 04:25

이분 탐색 문제입니다. M명의 친구들이 전부 심사대를 통과하는데 걸리는 시간을 구해야합니다. 심사대는 전부 시간이 다릅니다. 1. 시간을 구합니다. 2. 해당 시간으로 통과할 수 있는 사람들 수를 구합니다. 3-1. 사람들 수가 M보다 많거나 같다면 더 작은 경우가 있는지 확인합니다. => 1 3-2. 사람들 수가 M보다 적다면 불가능 한 경우로 가능한 경우가 있는지 확인합니다. => 1 위의 과정을 반복해서 최적의 결과값을 찾아냅니다. 해당 과정에서 시간을 구하는 과정은 이분탐색을 사용했습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { B..

article thumbnail
[Java] 백준 2473번 세 용액
알고리즘 2023. 8. 1. 01:24

투포인터 문제입니다. 세개의 숫자를 골라서 합의 절대값이 0과 가장 가까운 값들을 찾아야합니다. 두개의 숫자를 고르는 (용액, 두 용액) 문제와 유사합니다. N이 5000이므로 O(N^2)으로 처리할 수 있습니다. 0~N까지 고정점을 두고 나머지 두개의 수를 투포인터로 이동하면서 0과 가까운 수를 찾아주었습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new Buffered..

article thumbnail
[Java] 백준 1323번 숫자 연결하기
알고리즘 2023. 7. 31. 03:49

수학 문제입니다. N이 x개 있는 수가 있을 때 K로 나누어지는지 찾고 몇번만에 나누어지는지를 출력해야합니다. N이 x개 있다는 것은 31이 N이고 x가 5면 3131313131입니다. N이 K로 나눈 나머지를 확인하고, 0이 아니라면, 나온 나머지를 N과 연결하여 다시 위의 과정을 반복합니다. 0이 나온다면 성공한 케이스로 횟수를 출력해주고, 같은 나머지가 나올 경우는 실패한 경우로 -1을 출력해줍니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStrea..

검색 태그