반응형 전체 글133 백준 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. 백준 5014번 : 스타트링크 java 이 문제는 너비 우선 탐색을 이용하여 S층에서 G층으로 가기까지 눌러야 하는 버튼의 수의 최솟값을 구하는 문제입니다. 이 문제를 풀기 위해서는 U와 -D 만큼 현재 위치한 층에서 이동하면서 이미 방문한 층이라면 방문하지 않고 방문하지 않았다면 그 층으로 가기 위해서 필요한 버튼의 클릭수를 저장하면서 이동하면 됩니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new Stri.. 2022. 8. 5. 백준 11000번 : 강의실 배정 java 이 문제는 우선순위 큐를 이용하여 강의실의 필요 개수를 찾아내는 문제입니다. 이 문제를 해결하기 위해서는 우선 입력받은 값들을 시작 시간을 기준으로 오름차순으로 정렬해야 합니다. 만약 시작 시간이 같을 경우 종료 시간이 빠른 데이터 값을 앞에 둡니다. 그리고 가장 시작 시간이 빠른 데이터의 종료 시간을 우선순위 큐에 넣습니다. 그 후 다음 데이터 값의 시작 시간이 우선 순위우선순위 큐에 처음 들어있는 값보다 작다면 이 데이터의 종료 시간을 우선순위 큐에 넣습니다. 만약 시작 시간이 우선 순위 큐에 처음 들어 있는 값보다 작다면 우선순위 큐를 poll 해주고 새로운 데이터의 종료 시간을 우선순위 큐에 넣어줍니다. 위와 같이 하는 이유는 기본적으로 시작 시간을 기준으로 정렬하였기 때문에 우선 순위 큐에 들어.. 2022. 8. 3. 백준 1715번 : 카드 정렬하기 java 이 문제는 허프만 알고리즘을 이용하는 간단한 문제입니다. 허프만 알고리즘에 대한 설명은 아래의 글에 있습니다. 백준 13975번 : 파일 합치기 3 java 이 문제는 허프만 알고리즘을 이용하여 푸는 문제입니다. 허프만 알고리즘에 대하여 우선 설명드리도록 하겠습니다. 허프만 알고리즘이란 압축 단위마다 문자의 출현 빈도를 조사하여 빈도가 dy-coding.tistory.com import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in.. 2022. 8. 3. 백준 1946번 : 신입 사원 java 이 문제는 정렬을 이용하여 신입 사원을 뽑는 문제입니다. 이 문제에서 신입 사원을 뽑는 기준은 서류, 면접 등수가 둘 다 다른 지원자보다 낮은 사람은 뽑지 않는 것입니다. 이때 신입 사원이 되기 위해서는 서류, 면접 등수 중 하나는 다른 지원자보다 높아야 합니다. 이를 판별하기 위하여 둘 중 하나를 기준으로 정렬한 후 다른 전형을 비교합니다. 위의 예제 1번에서 테스트 케이스 1번을 기준으로 예시를 들어드리겠습니다. 위의 테스트 케이스 1번은 다음과 같이 나타낼 수 있습니다. 이때 서류의 등수를 기준으로 정렬하겠습니다. 그럼 위의 그림과 같이 정렬됩니다. 그럼 이제 신입 사원을 뽑아보도록 하겠습니다. 서류 전형의 1등인 사람은 다른 사람보다 두 전형의 등수가 낮을 수 없기 때문에 자연스럽게 채용됩니다. .. 2022. 8. 1. 이전 1 2 3 4 5 6 7 ··· 17 다음 반응형
