백준

백준 - 색칠하기 13265 자바

https://www.acmicpc.net/problem/13265 13265번: 색칠하기 각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다. www.acmicpc.net 오차피 두가지 색상밖에 없으므로 시작노드 색깔을 1로 시작노드와 연결된 노드들을 -1로 설정 bfs 돌리면서 인접한 노드가 이미 색칠 되어 있고 현재 노드 색깔 + 인접노드 색깔이 0이 아니면 사이클이 있는거므로 impossible, bfs가 정상적으로 다 돌면 possible import java.io.*; import java.util.*; public class Main { static ArrayList list..

백준 - Packet Routing 6951 java

https://www.acmicpc.net/problem/6951 6951번: Packet Routing The date is October 29th, 1969. Today, scientists at UCLA made history by exchanging data between two computers over a network. The transmission wasn't very spectacular: only the first two letters of the word login were received before the system crashed. www.acmicpc.net [문제 해설] 해당 문제는 패킷 라우팅에 관한 설명입니다. 패킷에서 패킷까지의 이동 거리가 주어지고 입력으로 들어오는 패..

백준 - 친구비 16562

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net [문제 접근] union-find 알고리즘 사용 union 함수에서 부모 설정할 때 cost가 더 낮은 친구로 설정 1 ~ N 까지 find 함수로 부모를 찾아 준 후 cost를 더해 주고, 방문 처리를 통해 이미 더해준 집합은 건너뜀 [Java] import java.io.BufferedReader; import java.io...

백준 - 연속합 1912 java

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net [문제 접근] input으로 주어진 값이 너무 커서 완전 탐색으로 접근하게되면 시간 복잡도가 어마어마 해질거 같았습니다. 그래서 dp 메모제이션으로 문제 접근을 해봤습니다. 우선 저는 연속된 수를 골랐을 때, 연속된 수를 고르지 않았을 때 두 가지 경우로 나누어서 생각했는데요 dp[i] 배열에는 i번째 수에서 최대로 만들 수 있는 값을 저장하면 점화식은 아래와 같아집니다. dp[i] = Math.max(dp..

백준 - 문자열 집합 조합하기 25328

[문제 해결] 문자열 X, Y, Z 에서 K개를 선택해 나온 조합에서 같은 문자열이 2개 이상 나온 문자열을 출력하는 문제 X, Y, Z 조합을 구하면서 HashMap을 이용해 문자열이 나온 빈도수를 기록한다. 빈도수가 2 이상인 문자열들을 오름차순 출력 [Java] import java.io.*; import java.util.*; public class Main { static HashMap map = new HashMap(); public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String x = br.readLi..

백준 - 캠프 준비 16938

https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 조합 백트래킹으로 완전 탐색 [Java] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int ans = 0; static int arr[]; static boolean visited[]; static int l,r,x; public static void main(String[] args) throws IOException { BufferedR..