반응형 전체 글130 백준 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. 백준 13975번 : 파일 합치기 3 java 이 문제는 허프만 알고리즘을 이용하여 푸는 문제입니다. 허프만 알고리즘에 대하여 우선 설명드리도록 하겠습니다. 허프만 알고리즘이란 압축 단위마다 문자의 출현 빈도를 조사하여 빈도가 높은 순서대로 비트 수가 적은 부호를 부여함으로써 데이터를 압축하는 방식입니다. 간단히 말하면 많이 사용된 문자는 더 적은 비트로 나타내고 적게 사용된 문자는 더 많은 비트를 사용하여 나타내어 효율적으로 문자열을 나타내겠다는 것입니다. 문자열 하나를 예시로 이에 대해 설명해드리겠습니다. AAAAAABBBBCDD라는 문자열이 있습니다. 이 문자열에서 A는 6개, B는 4개, C는 1개 D는 2개가 사용되었습니다. 이를 그림으로 나타내면 아래와 같습니다. 허프만 알고리즘을 이용하기 위해서는 가장 적은 사용 빈도를 가진 두 항을 묶.. 2022. 7. 29. 백준 19238번 : 스타트 택시 java 이 문제는 아기 상어 문제와 유사한 부류의 문제입니다. bfs를 이용하여 출발지에서 도착지까지 가는 거리를 구해서 가스의 양을 확인하면서 진행하는 문제입니다. 이 문제에서는 택시가 출발하여 가장 가까운 거리에 있는 사람을 태운 다음에 그 사람의 목적지까지 택시를 이동시켜주면됩니다. 문제에서 주어진 조건들을 하나하나 구현해주면 되는 문제입니다. import java.io.*; import java.util.*; public class Main { static int N, gas; static boolean canGo = true; static int[][] map; static Node[] start; static Node[] arrival; static int[] dR = {1, -1, 0, 0}; st.. 2022. 7. 28. 백준 2211번 : 네트워크 복구 java 이 문제는 다익스트라 알고리즘을 이용하여 1번 컴퓨터에서 각 컴퓨터로 향하는 최단 경로를 구하고 그 경로를 출력하는 문제입니다. 저는 이를 위하여 PriorityQueue 안에 각각의 노드에는 목표 정점(to)과 그 정점으로 가기 직전의 정점(from), 시작 정점에서 목표 정점까지의 거리(val)를 저장하였습니다. 그리고 각 정점에 처음 방문하였을 때 to와 from을 다른 ArrayList에 담아 최단 경로를 저장하였습니다. import java.io.*; import java.util.*; public class Main { static int N; static List l = new ArrayList(); static List answer = new ArrayList(); public static.. 2022. 7. 27. 이전 1 2 3 4 5 6 7 ··· 17 다음 반응형
