본문 바로가기
반응형

전체 글133

백준 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.
백준 2638번 : 치즈 java 이 문제는 (0, 0)에서 bfs를 실행하여 위의 그림 1, 2, 3과 같이 바깥공기와 2면 이상이 닿은 치즈들을 녹이면서 몇 초 후에 치즈가 전부 없어지는지 구하는 문제입니다. 저는 각각의 치즈가 주변에 공기가 몇 칸이 있는지를 확인하기 위해서 air 배열을 이용하였습니다. import java.io.*; import java.util.*; public class Main { static int N, M, cheeseNum = 0, time = 0; static int[][] map; static int[][] air; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; public static void main(String[] args.. 2022. 7. 26.
백준 2637번 : 장난감 조립 java 이 문제는 위상 정렬을 이용하여 부품을 만들어야 하는 우선순위를 만든 뒤 우선순위에 있는 부품을 만들기 위해서 필요한 우선순위가 뒤에 있는 부품의 개수를 더하며 푸는 문제입니다. 위의 예제 입력 1번을 예시로 설명하겠습니다. 예제 입력 1번의 N은 7입니다. N은 만들어야하는 개수가 1개입니다. 7을 만들기 위해서는 우선 6을 3개, 5를 2개, 4를 5개 만들어야 합니다. 그리고 6을 1개 만들기 위해서는 3을 3개, 4를 4개, 5를 2개 만들어야 합니다. 이때 6을 3개 만들어야 하므로 3을 3x3인 9개, 4를 12개, 5를 6개 만들어야 합니다. 그리고 5를 만들기 위해서는 1을 2개, 2를 2개 만들어야 합니다. 5는 7을 만들기 위해서 2개, 6을 만들기 위해서 6개가 필요해 총 8개가 필요.. 2022. 7. 25.
백준 1766번 : 문제집 java 이 문제는 위상 정렬과 우선순위 큐를 이용하여 푸는 문제입니다. 먼저 푸는 것이 좋은 문제들이 존재하여 이를 조건에 맞게 정렬해주는 위상 정렬 알고리즘을 사용하고 문제를 풀 때 낮은 번호의 문제를 먼저 푸는 것이 좋기 때문에 우선순위 큐를 이용하여 낮은 번호의 문제를 뽑아내야 합니다. 위의 예제를 살펴보도록 하겠습니다. 위 문제는 위와 같은 구조를 이루고 있습니다. 1번과 2번 문제는 각각 3번, 4번 문제를 먼저 해결해야 하므로 parentNum이 1입니다. 이제 parentNum이 0이라서 먼저 풀어도 상관없는 정점들을 PriorityQueue에 넣어줍니다. 이제 PriorityQueue의 가장 앞에 있는 문제를 풀어주겠습니다. 3번 문제를 풀었으니 이제 1번 문제의 parentNum이 0이 되어 풀.. 2022. 7. 24.
백준 1719번 : 택배 java 이 문제는 각각의 번호마다 다익스트라 알고리즘을 적용하여 각각의 정점마다 다른 정점까지 갈 때의 최단경로에서 처음으로 거쳐가는 정점을 출력하는 문제입니다. 저는 최단 경로에서 처음 거쳐가는 정점을 구하기 위해서 firstGo라는 배열을 따로 만들어서 이 정점에 오기 위해서 처음 거쳐야 하는 정점을 저장하게 만들었습니다. 이 firstGo라는 배열은 초기값으로 자기 자신의 정점 번호를 가지고 있습니다. 그리고 시작 정점에서 다른 정점을 거쳐서 자신의 정점으로 오는 것이 더 효율적이라면 firstGo 배열에서 그 정점의 인덱스에 저장되어 있는 정점을 저장하게 하는 식으로 최단 경로에서 처음 간 정점을 구하게 만들었습니다. 위의 그림과 같은 그래프가 있다고 가정하겠습니다. 이 그래프를 이용하여 다익스트라 알고.. 2022. 7. 23.
백준 5972번 : 택배 배송 java 이 문제는 다익스트라 알고리즘을 이용하는 기초 문제입니다. 다익스트라 알고리즘에 대한 설명은 아래의 링크에 있습니다. 백준 1753번 : 최단경로 java 이 문제는 다익스트라 알고리즘을 푸는 문제입니다. 이 문제를 풀 때 유의하셔야 하는 점은 메모리 제한이 256MB라는 점입니다. 저는 이 문제를 풀 때 처음에는 들어온 자료들을 2차원 배열에 입 dy-coding.tistory.com import java.io.*; import java.util.*; public class Main { static int N; static List l = new ArrayList(); static int[] dist; public static void main(String[] args) throws IOExceptio.. 2022. 7. 22.
반응형

티스토리툴바