본문 바로가기
반응형

분류 전체보기123

백준 2217번 : 로프 java 이 문제는 배열을 내림차순으로 정렬한 후 로프가 들어 올릴 수 있는 물체의 최대 중량을 구하는 알고리즘입니다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때 각각의 로프에는 w/k 만큼의 중량이 걸립니다. 이를 이용하면 가장 버틸 수 있는 중량이 적은 로프 하나가 버틸 수 있는 최대 중량이 L이라고 했을 때 k x L의 중량을 버틸 수 있다는 것을 의미합니다. 위의 예제에서 10 15 두 개의 로프를 이용하여 문제를 풀 때 가장 버틸 수 있는 중량이 적은 로프는 10입니다. 2개의 로프를 이용하였으므로 10 x 2 = 20, 즉 20이 이 2개의 로프를 이용하였을 때 버틸 수 있는 중량의 총량입니다. 이를 이용하여 이 알고리즘을 해결하였습니다. import java.io.*; import jav.. 2022. 6. 20.
백준 1647번 : 도시 분할 계획 java 이 문제는 최소 비용 신장 트리를 구성하는 문제입니다. 저는 프림 알고리즘을 이용하여 이 문제를 해결하였고 이 알고리즘에 대한 설명은 아래의 문제에 있습니다. 백준 1922번 : 네트워크 연결 java 이 문제는 최소 비용 신장 트리를 만드는 방법입니다. 최소 비용 신장 트리를 만드는 방법에는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 저는 이 문제를 풀 때 프림 알고리즘을 선택해서 dy-coding.tistory.com 저는 프림 알고리즘을 이용하여 최소 비용 신장 트리를 만든 다음 간선 중에서 가장 큰 가중치를 가진 간선을 제거하여 마을을 2개로 나누었습니다. 바로 코드를 보여드리겠습니다. import java.io.*; import java.util.*; public class Main { pu.. 2022. 6. 19.
백준 1922번 : 네트워크 연결 java 이 문제는 최소 비용 신장 트리를 만드는 방법입니다. 최소 비용 신장 트리를 만드는 방법에는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 저는 이 문제를 풀 때 프림 알고리즘을 선택해서 풀었습니다. 크루스칼 알고리즘을 이용하여 최소 비용 신장 트리를 만드는 방법은 아래의 링크에 있습니다. 백준 1197번 : 최소 스패닝 트리 java 이 문제는 최소 비용 신장 트리를 만드는 문제입니다. 최소 비용 신장 트리를 만들기 위한 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있습니다. 크루스칼 알고리즘은 간단히 말해서 dy-coding.tistory.com 프림 알고리즘이란 임의의 정점을 기준으로 그 정점의 경로와 연결된 다른 정점들의 경로 중에서 가장 가중치가 적은 경로를 선택하며 최소 비용 신장 트리를 .. 2022. 6. 18.
백준 3190번 : 뱀 java 이 문제는 사과가 있는 곳을 입력받아서 뱀이 사과가 있는 곳을 지나치면 뱀의 길이를 늘이고 아니면 유지하게 합니다. 그리고 시간이 경과함에 따라서 방향을 회전시키게 해서 뱀이 벽이나 자신의 몸에 머리를 박으면 게임이 끝나게 합니다. 이 문제를 예제 1번을 이용하여 설명드리겠습니다. 예제 1번의 초기 상태는 다음과 같습니다. 위에 spin 큐에 들어가 있는 것들은 X초 후에 어떤 방향으로 회전하는가를 나타냅니다. L이면 보고 있는 방향의 왼쪽으로 회전, D면 오른쪽으로 회전합니다. 사과를 먹으면 길이가 늘어나고 먹지 않으면 길이를 유지합니다. 이제 뱀을 이동시켜보겠습니다. 우선 문제의 조건에 맞게 뱀을 한 칸 앞으로 보냈습니다. 그러나 사과를 먹지 않았으므로 길이가 늘지 않아 빨간 화살표를 지워줍니다. 다.. 2022. 6. 18.
백준 1987번 : 알파벳 java 이 문제는 깊이 우선 탐색을 이용해서 칸을 이동하면서 같은 알파벳이 적힌 칸을 두 번 지나지 않고 최대 갈 수 있는 칸을 구하는 문제입니다. 이 문제에 대해서 그림을 통해 자세히 설명드리도록 하겠습니다. 예제 1번을 표에 나타내면 위의 그림과 같습니다. 저는 이 문제를 풀 때 이미 지나간 알파벳은 set에 저장하여 다시 지나가지 않도록 했습니다. ArrayList나 LinkedList는 contains 메소드에 대한 시간 복잡도가 O(n)입니다. 하지만 HashSet을 통해서 set을 구현하면 O(1)의 시간 복잡도로 contains 메소드를 사용 가능합니다. 따라서 set을 사용하지 않으면 시간 초과가 나므로 set을 사용하였습니다. 이 문제에서 시작점은 1행 1열이니 여기서 dfs를 시작합니다. 이제.. 2022. 6. 17.
백준 14891번 : 톱니바퀴 java 이 문제는 문제에서 주어진 조건에 따라서 문제를 해결할 수 있는 알고리즘을 구현하는 문제입니다. 이 문제에서 주어진 조건에 대해서 설명해드리겠습니다. 위의 그림을 보시면 2번 톱니바퀴를 시계방향으로 굴린다고 가정했을 때 1번 톱니바퀴는 2번 톱니바퀴와 맞닿은 톱니가 서로 반대의 극을 가지고 있기 때문에 2번 톱니바퀴의 반대 방향인 반시계 방향으로 돌아가게 됩니다. 그리고 3번 톱니바퀴는 2번 톱니바퀴와 맞닿은 부분이 같은 극을 가지고 있기 때문에 돌아가지 않습니다. 이 알고리즘을 기반으로 코드를 구현해보도록 하였습니다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws .. 2022. 6. 17.
백준 1065번 : 한수 java 이 문제는 N보다 작거나 같은 한수의 개수를 출력하는 문제입니다. 한수란 어떤 양의 정수 X의 각 자리가 등차수열을 이루는 수입니다. 이러한 수의 예시는 123, 135, 159와 같은 수들이 있습니다. 문제에 대한 코드를 보시면 바로 이해하실 수 있으실 겁니다. import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int count = 0; for(int i = 1; i 2022. 6. 17.
백준 13335번 : 트럭 java 이 문제는 자료 구조 큐를 이용하여 위에서 주어진 조건에 맞게 최단시간을 구하는 알고리즘입니다. 저는 이 문제를 풀기 위해서 대기 중인 트럭들을 보관할 큐와 다리 위에 올라간 트럭들을 저장할 큐를 사용하였습니다. 각각의 큐에는 입력받은 자료의 무게와 인덱스를 저장하게 해서 문제를 해결하였습니다. 그림을 통해서 이를 자세히 설명드리도록 하겠습니다. 위의 그림은 예제 1번을 표현한 그림입니다. truck 큐에 들어가 있는 자료들은 다리에 올라가기 위해서 대기 중인 트럭들을 의미합니다. bridge 큐에 들어있는 자료들은 다리 위에 올라가 있는 트럭들을 의미합니다. location배열은 몇 시간 뒤면 트럭이 다리에서 빠져나오는지를 확인하기 위해서 만든 배열입니다. 트럭이 bridge 큐에 들어가면 해당 ind.. 2022. 6. 16.
반응형

티스토리툴바