알고리즘
백준 JAVA 1753번 최단경로
백준 JAVA 1753번 최단경로
2021.12.19문제 링크: https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 최단경로 문제다. 방향성과 음의 가중치가 없으므로 다익스트라 알고리즘으로 해결이 가능하다. 설명은 주석으로 표시하겠습니다. import java.util.*; import java.io.*; class node implements Comparable{ // 우선순위 큐를 사용하기 위해 상속받는다. int end; int cost; public no..
백준 JAVA 2252번 줄세우기
백준 JAVA 2252번 줄세우기
2021.12.18문제 링크: https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 키를 정렬하는데 있어서 약간의 순서를 줬다. 즉 어떤 학생 앞에는 정해진 학생이 앞에 있어야 하는 것이다. arr배열에 조건의 수를 적어주고 list[해당 학생].add(앞에 서야하는 학생)식으로 선언해준다. arr[학생]==0 일 경우에 StringBuilder에 추가해주며 해당 학생 앞에 서야하는 학생의 arr을 낮춰준다. 이때 낮춰준 학..
백준 JAVA 14567번 선수과목
백준 JAVA 14567번 선수과목
2021.12.18문제 링크: https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 원하는 과목을 듣기 위해선 선수 과목을 들어야 하는 문제이다. 즉 조건을 체크하면서 순서를 체크하는 문제이다. 순서대로 입력이 주어지므로 반복문을 통해서 첫 번째 강의부터 마지막 강의까지 조건들을 체크해주면 된다. 한 과목마다 조건의 최댓 값을 찾은 후 +1 해주면 해당 과목을 들을 수 있는 학기가 나온다. 과목마다 들을 수 있는 학기를 arr 배열에 담고 list[해당과목].add(조건)을 정리하여 찾으면 간..
백준 JAVA 19532번 수학은 비대면 강의입니다.
백준 JAVA 19532번 수학은 비대면 강의입니다.
2021.12.10문제 링크: https://www.acmicpc.net/problem/19532 19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net 단순한 브루트 포스 문제이다. ax+by=c 와 dx+ey=f를 만족하는 x,y를 반복문을 통해서 모든 경우의 수를 탐색해주면 된다. import java.util.*; import java.io.*; public class Main { public static void main(..
백준 JAVA 14891번 톱니바퀴
백준 JAVA 14891번 톱니바퀴
2021.12.04문제 링크: https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 시뮬레이션 문제로서 하나의 톱니바퀴를 돌렸을 때 옆에 있는 톱니바퀴들이 돌아간다면 상태 배열을 변경시키고 상태 배열에 따라서 시계방향, 반시계방향으로 돌려주면된다. 시작 지점에서의 시계, 반시계 방향으로 퍼져나가는 것을 생각해주면 어려운 문제는 아니다. import java.util.*; import java.io.*; class info{ int num; int dir; publ..
백준 JAVA 1197번 최소 스패닝 트리
백준 JAVA 1197번 최소 스패닝 트리
2021.12.01문제 링크: https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 스패닝 트리(MST)의 가장 기본적인 문제라고 할 수 있다. find를 통하여 부모를 찾고, union을 통하여 부모가 다를 경우 합치는 방식이다. import java.util.*; class Node implements Comparable{ int start, end, weight; public Node(int start, int..