백준
백준 JAVA 17609번 회문
백준 JAVA 17609번 회문
2021.12.24문제 링크: https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제를 접할 때 회문이 아닐 경우에 for문을 중첩해서 한 글자씩 빼낸 후 확인을 했을 경우 시간초과가 나왔다. (해당 코드 첨부) import java.math.BigInteger; import java.util.*; import java.io.*; public class Main { static int t; static boolean check; public static void main(String [] ar..
백준 JAVA 11722번 가장 긴 감소하는 부분 수열
백준 JAVA 11722번 가장 긴 감소하는 부분 수열
2021.12.23문제 링크: https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 해당 문제를 처음에는 DFS로 시도했지만 시간초과로 실패했다. 그래서 DP로 다시 풀어 보았다. import java.math.BigInteger; import java.util.*; import java.io.*; public class Main { static int [] arr; static int t; ..
백준 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..