Java
백준 JAVA 9342번 염색체
백준 JAVA 9342번 염색체
2021.12.21문제 링크: https://www.acmicpc.net/problem/9342 9342번: 염색체 상근이는 생명과학 연구소에서 염색체가 특정한 패턴인지를 확인하는 일을 하고 있다. 염색체는 알파벳 대문자 (A, B, C, ..., Z)로만 이루어진 문자열이다. 상근이는 각 염색체가 다음과 같은 규칙 www.acmicpc.net 문자열의 조건들을 순차적으로 확인하는 문제이다. String.indexOf()와 String.lastIndexOf()를 이용하면 쉽게 해결이 가능하다. indexOf(char) char와 같은 첫 번째 index를 반환하며 lastIndexOf(char) char와 같은 마지막 index를 반환해준다. 해당 조건들을 하나씩 체크해주면 된다. import java.math.BigIn..
백준 JAVA 1992번 네트워크 연결
백준 JAVA 1992번 네트워크 연결
2021.12.20문제 링크: https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 해당 문제는 최소신장트리의 개념에 가중치가 생겨 모든 정점을 연결할 때 최소 비용을 구하는 문제다. 크루스칼 알고리즘 과 프림 알고리즘으로 해결이 가능하다. find() 함수로 정점의 부모를 찾고 union() 함수로 부모가 다를 경우 부모를 같게 해주어 최소신장트리 조건을 만족시켜준다. 이때 PriorityQueue를 사용하여 가중치를 오름차순으로 정렬시켜준 후 작은 가중치 순서로 진행해준다. import java.math.BigInteger; import java.uti..
백준 JAVA 11657번 타임머신
백준 JAVA 11657번 타임머신
2021.12.19문제 링크: https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 음의 가중치가 있으므로 다익스트라 알고리즘으로는 해결할 수 없다. 따라서 벨만포드 알고리즘을 이용한다. 벨마포드 알고리즘을 이용함에 있어서 음의 사이클이 있으면 안되므로 해당 로직을 한 번더 실행하여 음의 사이클이 있는지 체크해준다. import java.util.*; import java.io.*; class node{ i..
백준 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(조건)을 정리하여 찾으면 간..