반응형 알고리즘/그리디 알고리즘10 백준 1461번 : 도서관 java 이 문제는 정렬을 이용하여 푸는 그리디 알고리즘 문제입니다. 이 문제를 풀기 위해서 저는 입력받은 값들을 하나의 List에 넣어 정렬할 후 처음 인덱스에 들어있는 인자와 마지막에 있는 인자의 절댓값을 비교하여 절댓값이 큰 쪽이 앞에 오게 정렬했습니다. 그리고 M개만큼 수를 List의 0번 인덱스에서 remove하면서 출력 값 answer에 더해주었고 remove 한 값에서 부호가 바뀔 경우에는 이 List를 뒤집어서 위의 과정을 반복했습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new Buffere.. 2022. 8. 15. 백준 1080번 : 행렬 java 이 문제는 그리디 알고리즘을 이용하여 푸는 문제입니다. 이 문제를 풀기 위해서는 N, M을 입력받은 후 맨 처음 칸부터 행렬 A와 행렬 B가 같은지 확인하여 다르다면 그 칸을 시작으로 3x3만큼의 크기만큼을 바꾸어주어야 합니다. 이 위의 그림은 예제 1번을 나타낸 그림입니다. 이 그림에서 A의 1행 1열은 B의 숫자와 다릅니다. 따라서 이 칸을 기준으로 3x3 크기의 칸의 수를 바꾸겠습니다. 뒤집을 영역의 크기는 아래의 그림과 같습니다. 이를 뒤집으면 아래의 그림과 같이 됩니다. 그리고 A의 1행 1열을 보면 B 행렬과 다르기 때문에 위에 같이 뒤집어 줍니다. 뒤집을 영역은 아래와 같습니다. 이제 아래의 그림과 같이 A행렬과 B행렬이 같아졌습니다. 위와 같이 처음부터 A행렬과 B행렬을 비교해가면 이 문제.. 2022. 8. 14. 백준 12904번 : A와 B java 이 문제는 조건에 맞게 문자열을 변형시켰을 때 S를 이용하여 T를 만들 수 있는지 확인하는 문제입니다. 이 문제를 풀기 위해서 저는 T를 변형시켜 S가 될 수 있는지 확인했습니다. T의 마지막 문자가 A일 경우 문자를 제거하였고 마지막 문자가 B일 경우 이 문자를 제거한 후 문자열을 뒤집었습니다. 이 과정을 T와 S의 길이가 같아질 때까지 반복한 후 두 문자열이 같은지 확인하면 이 문제를 해결할 수 있습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputSt.. 2022. 8. 11. 백준 1092번 : 배 java 이 문제는 정렬을 이용하여 모든 박스를 옮기는 데 걸리는 시간을 구하는 문제입니다. 이 문제를 풀기 위해서는 입력받은 데이터들을 모두 내림차순으로 정렬합니다. 그 후 가장 무거운 무게를 들 수 있는 크레인부터 차례대로 박스를 옮기는 것을 시도합니다. 크레인이 박스를 옮기는 것을 성공하였으면 그 크레인은 이미 사용하였으므로 다음으로 무거운 무게를 들 수 있는 크레인을 이용하여 다음 박스를 옮깁니다. 그리고 그 크레인이 박스를 옮길 수 없다면 그다음 박스를 같은 크레인으로 옮기는 것을 시도합니다. 그리고 마지막 박스까지 순회를 마치거나 모든 크레인을 사용하였다면 다시 가장 무거운 무게를 옮길 수 있는 크레인을 이용합니다. 이 과정을 모든 박스를 옮길 때까지 반복합니다. import java.io.*; imp.. 2022. 8. 10. 백준 2212번 : 센서 java 이 문제는 문제를 이해하는 것이 어려운 문제였습니다. 이 문제는 N개의 센서가 있고 K개의 집중국이 있는데 K개의 집중국을 이용하여 수신 가능 영역의 길이의 합을 구하는 문제입니다. 이 문제에서 수신 가능 영역이 무엇인지를 설명드리겠습니다. 우선 위 문제의 예제 1번은 다음과 같습니다. 이제 이 센서들을 정렬해보겠습니다. 위의 그림과 같이 나옵니다. 이때 수신 가능 영역이란 아래의 그림과 같이 집중국을 세웠을 때 집중국들에 연결된 구역을 의미합니다. 위의 그림으로 예시를 들면 1 ~ 6까지 5에 7 ~ 9까지 2의 수신 가능 영역을 가져 총 7의 거리입니다. 이때 이 수신 가능 영역을 최소로 만들기 위해서는 두 점 사이의 거리가 가장 먼 곳을 제외하면 됩니다. 위의 그림에서는 3과 6의 거리의 차이가 6.. 2022. 8. 9. 백준 2437번 : 저울 java 이 문제는 누적합을 이용하여 해결하는 문제입니다. 이 문제를 풀기 위해서는 우선 입력받은 값들을 정렬합니다. 그리고 첫번째 숫자부터 차례대로 더해가면서 누적합을 만듭니다. 그리고 만약 i+1번 자리에 있는 수가 i번까지의 누적합에 1을 더한 값보다 크다면 누적합에 1을 더한 값은 만들 수 없습니다. 이는 i번까지의 누적합이 그 숫자까지 더했을 때 만들 수 있는 수의 최댓값이기 때문입니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(S.. 2022. 8. 8. 백준 1744번 : 수 묶기 java 이 문제는 두 수를 곱하여 더하는 것이 더 큰 수를 만들 수 있는지, 그냥 더하는 것이 더 큰 수를 만들 수 있을지를 판별하여 더 큰 수를 만들어내는 문제입니다. 이 문제를 풀기 위해서 저는 우선순위 큐를 이용하였습니다. 우선순위 큐에 입력받은 데이터들을 전부 넣은 후 데이터들을 2개씩 poll 하면서 두 수가 모두 음수이거나 0일 때는 곱하여 더하는 것이 더 큰 수를 만들 수 있으므로 그렇게 하였습니다. 그리고 양수일 경우 1이 섞여 있으면 두 수를 그냥 더하는 것이 이득이고 이외에는 곱하는 것이 이득이므로 이렇게 했습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) thr.. 2022. 8. 5. 백준 11000번 : 강의실 배정 java 이 문제는 우선순위 큐를 이용하여 강의실의 필요 개수를 찾아내는 문제입니다. 이 문제를 해결하기 위해서는 우선 입력받은 값들을 시작 시간을 기준으로 오름차순으로 정렬해야 합니다. 만약 시작 시간이 같을 경우 종료 시간이 빠른 데이터 값을 앞에 둡니다. 그리고 가장 시작 시간이 빠른 데이터의 종료 시간을 우선순위 큐에 넣습니다. 그 후 다음 데이터 값의 시작 시간이 우선 순위우선순위 큐에 처음 들어있는 값보다 작다면 이 데이터의 종료 시간을 우선순위 큐에 넣습니다. 만약 시작 시간이 우선 순위 큐에 처음 들어 있는 값보다 작다면 우선순위 큐를 poll 해주고 새로운 데이터의 종료 시간을 우선순위 큐에 넣어줍니다. 위와 같이 하는 이유는 기본적으로 시작 시간을 기준으로 정렬하였기 때문에 우선 순위 큐에 들어.. 2022. 8. 3. 이전 1 2 다음 반응형
