반응형 알고리즘113 백준 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. 백준 2146번 : 다리 만들기 java 이 문제는 bfs를 이용하여 한 섬에서 다른 섬까지의 최단 거리를 찾아서 다리를 만드는 문제입니다. 저는 이 문제를 풀기 위해서 우선 각각의 섬들을 나누었고 다른 섬에 접촉한다면 다리를 만들게 하였습니다. 이를 예제 1번을 예시로 간단히 보여드리겠습니다. 위의 그림과 같이 저는 우선 이 지도의 각각의 좌표들을 확인하여 연결된 부분들을 하나의 섬으로 묶은 다음 같은 섬에 속해있는 땅의 숫자를 같게 만들었습니다. 이후 각각의 섬에서 bfs를 실행하여 가장 먼저 자신의 섬과 다른 섬에 닿았을 때 다리를 건설하게 했습니다. import java.io.*; import java.util.*; public class Main { static int N, min = Integer.MAX_VALUE; static in.. 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. 이전 1 2 3 4 ··· 15 다음 반응형
