목록알고리즘/백준 (16)
우보천리 개발
백준 1325 효율적인 해킹 https://www.acmicpc.net/problem/1325
백준 18352 특정 거리의 도시 찾기 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 아이디어 BFS 알고리즘을 활용하여 시작 도시와 인접한 도시까지의 거리를 구하며 계속 거리를 구해나간다 방문 배열을 만들어 거리를 업데이트한다 처음 거리는 0이고 그 이후 거리는 1만큼 늘어나기 때문에 이전 값에서 +1 해준 값으로 갱신해준다 코드 package baekjoon; imp..
백준 1744 수 묶기 문제 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 아이디어 양수*양수, 음수*음수 를 통해서 가장 큰 값을 도출 할 수 있다 물론 가장 큰 양수끼리의 곱, 그리고 가장 작은 음수 끼리의 곱이다 1의 경우 마지막에 더해주는 방식이 가장 큰 값을 만들 수 있다. 0은 음수가 총 홀수개 있다면 마지막으로 큰 음수에 곱해주면 되고 그렇지 않다면 나머지 음수는 그냥 더해주어야한다 PriorityQueue를 사용해서 양수, 음..
백준 1715 카드 정렬하기 문제 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 아이디어 문제의 예시에도 나와있듯이 최소한으로 비교하기 위해서는 가장 작은 값끼리 먼저 더해야한다 즉 10, 20, 40이면 (10+20) + (30+40) 을 해야함 계속해서 작은 값을 먼저 더해야되기 때문에 PriorityQueue 우선순위큐를 사용하면 된다 코드 package baekjoon; import java.util.*; class BJ..
백준 1931 회의실 배정 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 아이디어 최대한 많은 회의를 진행하려면 종료시간이 짧은 회의부터 진행해야 겹치지 않고 최대한 많은 회의를 할 수 있음 그렇기 위해서는 회의의 종료시간을 오름차순으로 정렬해야함. --> compareTo 사용 회의의 종료시간이 같으면 시작 시간을 기준으로 다시 정렬해야하기 때문에 조건을 추가 코드 package baekjoon; import java.util.*; class BJ1931 { static class Meetings implements Comparable { // 회의 ..
백준 1541번 잃어버린 괄호 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 아이디어 가장 작은 값을 구하기 위해서는 가장 큰 숫자를 빼면 된다 따라서 더하기가 있는 숫자들은 묶어서 더하고, 나머지 숫자는 다 빼면 된다 split() 함수를 써서 특수문자를 사용할 때 이스케이프 기호 사용해주어야함 코드 package baekjoon; import java.util.*; class BJ1541 { public static void m..