반응형 알고리즘/자료구조12 백준 13975번 : 파일 합치기 3 java 이 문제는 허프만 알고리즘을 이용하여 푸는 문제입니다. 허프만 알고리즘에 대하여 우선 설명드리도록 하겠습니다. 허프만 알고리즘이란 압축 단위마다 문자의 출현 빈도를 조사하여 빈도가 높은 순서대로 비트 수가 적은 부호를 부여함으로써 데이터를 압축하는 방식입니다. 간단히 말하면 많이 사용된 문자는 더 적은 비트로 나타내고 적게 사용된 문자는 더 많은 비트를 사용하여 나타내어 효율적으로 문자열을 나타내겠다는 것입니다. 문자열 하나를 예시로 이에 대해 설명해드리겠습니다. AAAAAABBBBCDD라는 문자열이 있습니다. 이 문자열에서 A는 6개, B는 4개, C는 1개 D는 2개가 사용되었습니다. 이를 그림으로 나타내면 아래와 같습니다. 허프만 알고리즘을 이용하기 위해서는 가장 적은 사용 빈도를 가진 두 항을 묶.. 2022. 7. 29. 백준 16562번 : 친구비 java 이 문제는 분리 집합을 이용하여 학생들이 서로 친구인지 아닌지 확인하면서 친구비를 지불하는 문제입니다. 이 문제에서는 한 무리의 학생들이 서로 친구일 경우 가장 적은 친구비를 주어도 되는 학생을 찾아 친구비를 지불하면 됩니다. 위 문제의 예제 1번은 다음과 같이 친구관계를 맺고 있습니다. 이 문제에서는 1, 3번 학생이 친구이고 2, 4, 5번 학생이 친구입니다. 따라서 이 그룹 중에서 각각 한 명씩만 친구가 되면 됩니다. 1번 학생의 친구비가 10이고 3번 학생의 친구비가 20이니 1번 학생에게 친구비를 지불해줍니다. 2번 학생의 친구비가 10이고 4번 학생의 친구비가 20, 5번 학생의 친구비가 30이니 2번 학생에게 친구비를 지불합니다. 따라서 20의 금액만 있다면 주어진 모든 학생들과 친구가 될 .. 2022. 7. 20. 백준 1717번 : 집합의 표현 java 이 문제는 분리 집합을 이용하여 해결하는 문제입니다. 분리 집합이란 union-find 함수를 이용하여 자신과 연결되어 있는 정점인지 확인하여 연결되어 있지 않다면 연결하는 알고리즘입니다. 이 문제에서는 0이 처음 입력으로 주어졌을 경우 뒤의 두 정점을 이어주고 1이 입력으로 들어올 경우 두 정점이 연결되어 있는지를 확인하여 YES나 NO를 출력하면 됩니다. 코드를 바로 보여드리겠습니다. import java.io.*; import java.util.*; public class Main { static int[] parent; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(ne.. 2022. 6. 30. 백준 1043번 : 거짓말 java 이 문제는 지민이가 이야기하는 것에 대한 진실을 아는 사람이 주어질 때 이 사람들과 같은 파티에 갔던 사람들에게 들키지 않고 지민이가 얼마나 많은 파티에서 거짓말을 할 수 있는지 구하는 문제입니다. 이 문제를 풀 때 우선 지민이가 말한 것에 대한 진실을 아는 사람들을 입력받습니다. 그리고 그 사람들과 같은 파티에 갔던 사람들을 union-find를 이용하여 합쳐줍니다. 그리고 그 사람들이 갔던 파티를 제외한 다른 파티의 개수를 세어 출력하면 됩니다. 이에 대한 코드를 보여드리겠습니다. import java.io.*; import java.util.*; public class Main { static int[] parent; public static void main(String[] args) throws.. 2022. 6. 29. 백준 1976번 : 여행 가자 java 이 문제는 분리 집합을 이용하여 푸는 문제입니다. 분리 집합이란 여러 개의 분리된 집합들이 있을 때 이 집합들에 대한 연결 관계를 입력받아 연결하여 이를 이용하는 문제입니다. 이 문제에서는 N개의 도시에 대한 연결 관계를 입력받아서 M개의 도시를 여행할 수 있는지 확인하는 문제입니다. 한번 갔던 도시라도 연결되어 있기만 하다면 갈 수 있습니다. 코드를 바로 보여드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int[] parent; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new In.. 2022. 6. 29. 백준 20040번 : 사이클 게임 java 이 문제는 분리 집합을 이용하여 푸는 문제입니다. 첫 번 째 줄에서 N과 M을 받은 후 N개의 정점에서 M개의 선을 이을 때 사이클이 생기지 않으면 0을 출력하고 사이클이 생기면 사이클이 생겼을 때 입력받은 간선의 수를 출력하는 문제입니다. 예제 1번은 모든 간선을 이어도 아래와 같이 사이클이 없으므로 0을 출력합니다. 하지만 예제 2번은 중간에 사이클이 생깁니다. 언제 사이클이 생기는지 보여드리겠습니다. 첫 번째 간선을 입력받았을 때 다음과 같은 모습입니다. 두번째 입력을 받았을 때 위와 같은 모습입니다. 세번째 입력을 받았을 때 다음과 같은 모습입니다. 그리고 네번째 입력을 받을 때 사이클이 생깁니다. 따라서 4를 출력합니다. 이 문제를 풀면서 그래프가 생기는가 생기지 않는가는 union-find 함.. 2022. 6. 29. 백준 1021번 : 회전하는 큐 java 이 문제는 덱 자료구조를 이용하여 어떤 방향으로 연산을 해야 더 효율적으로 자료들을 찾을 수 있는지를 구현하는 문제입니다. 위의 문제에서 1 2 3번 연산을 각각 설명해드리도록 하겠습니다. 위와 같은 덱이 있다고 가정해보겠습니다. 만약 제가 찾아야 하는 수가 2라면 표를 왼쪽으로 한번 움직이는 것이 오른쪽으로 5번 움직이는 것보다 적게 움직입니다. 따라서 위 문제에서 2번 연산을 해줍니다. 2번 연산을 해줭 왼쪽으로 표를 한번 움직여주면 다음과 같은 표가 나옵니다. 덱의 맨 앞에 찾고자하는 수인 2가 왔으므로 1번 연산을 해서 2를 덱에서 제거해주도록 하겠습니다. 그럼 다음과 같은 그림이 나옵니다. 이제 6을 찾아보도록 하겠습니다. 6이 현재 있는 인덱스는 3번입니다. 3번에 있는 값을 0번으로 가져오기.. 2022. 6. 15. 백준 1158번 : 요세푸스 문제 java 이 문제는 자료 구조의 일종인 큐를 이용해서 요세푸스 순열을 구하는 문제입니다. 요세푸스 순열이란 K번째 사람을 제거해주면서 제거된 순서대로 출력하는 문제입니다. 이를 표로 조금 더 이해하기 쉽게 나타내겠습니다. 위 표를 보시면 어떤 순서로 사람이 제거되고 제거된 다음에는 배열이 어떻게 남아 있는지를 확인하실 수 있습니다. 저는 이 문제를 해결하기 위해서 큐를 사용하였습니다. 우선 큐에 사람들을 순서대로 넣습니다. 그리고 K번 만큼 뒷사람을 찾아갑니다. 뒷사람을 찾아가면서 지나친 사람들은 pop한 후 다시 offer해서 맨 뒤로 보내줍니다. 찾아간 인덱스에 있는 사람을 pop해서 answer배열에 넣습니다. 이 과정은 N번 반복하면 위의 Output처럼 결과가 나옵니다. 이를 코드로 보여드리겠습니다. i.. 2022. 6. 14. 이전 1 2 다음 반응형
