우선 이분 그래프가 정확히 뭔지 몰라 헷갈렸다. 이분 그래프란?모든 정점을 두 가지 색으로 표현인접한 정점을 연결할 때에는 무조건 다른 색상의 것을 연결 처음에 문제를 풀 때 단순하게 싸이클 여부만 판단해서 풀었는데 6%에서 실패했다. 해당 그래프는 각각 독립적으로 두 개가 존재할 수도 있기 때문에 이러한 부분도 고려해야 한다. import java.util.*;import java.io.*;public class BOJ_G4_1707_이분그래프 { static int[] p; static List[] graphs; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new I..

https://www.acmicpc.net/problem/7512 처음에 각각 ni개들에서 합을 구했을 때 나오는 소수 중에서 가장 작은 값을 구하라고 문제를 잘못 파악했는데, 테스트 케이스를 보니, m개의 합에 대한 소수중에서 공통인 소수의 최솟값을 구하는 문제였다. 문제를 정확히 파악하는게 중요하다. 또한 문제에서 정답은 10^7이었는데, m개의 소수의 합을 구했을 때, 소수의 합이 우선 int형의 크기를 초과할 수 있으므로 long 타입으로 선언하는게 중요하다. 그렇게 하지 않아서 ArrayIndexOutOfBoundException이 났었다. 소수를 구할 때, 에라토스테네스의 체를 사용하였다.기본적인 소수를 구하는 알고리즘을 작성한다면 O(N^2)인데, 에라토스테네스의 체를 사용하면 log(Nl..

소수를 구할 때 유용한 방식시간 복잡도: O(NlogN) 1. 2부터 N까지의 수를 나열한다.2. 2부터 가장 작은 수를 소수로 정하고, 2의 배수를 모두 지운다.3. 지우지 않은 수 중에서 가장 작은 수(3)를 소수로 정하고 그 배수(3의 배수)를 지운다. 이렇게 하나씩 지워나가다 보면 지워지지 않는 수들이 있는데 이들이 바로 소수다. public class Main { static boolean[] isPrime; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 2부터 구하고자하는 소수를 N까지 isPri..

https://www.acmicpc.net/problem/2504 다시 풀 문제문제를 처음 봤을 땐 딱봐도 Stack을 사용해야하는 문제라고 생각했지만, 괄호간의 연산에 대해서 덧셈과 곱셈을 어떻게 처리해야할지 고민했던 문제. 다른 사람의 풀이를 참고하여 풀었다. 각각의 case에 대해 경우의 수를 나눠서 backTracking 같이 풀이를 진행하였다. 나는 괄호가 끝날 때, 연산을 진행하려고 했는데, 작성자는 시작하는 괄호가 나왔을 때, 임시로 값을 담아놓고, 만약 괄호가 정상적으로 종료된다면 해당 값을 최종 결과에 저장하는 방식을 사용했다.따라서 만약 시작하는 괄호가 여러 개 나온다면 계속 tmp에 괄호에 해당하는 연산을 곱해주고, 이후 하나의 괄호가 닫힐 때마다, tmp를 해당 값만큼 나눠준다. i..

같이 풀면 좋은 문제 https://www.acmicpc.net/problem/24042 다익스트라 알고리즘- 최단 경로를 위해 사용- 현재 코드는 우선순위 큐를 이용- 가중치 값들이 모두 0보다 커야 한다.(음수일 경우에는 안됨) import java.util.*;import java.io.*;public class DijkstraPqMain { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 인접 행렬로 만듦. int[][] g = new int[N][N]; // MST에 속하면 true. boolean[] v = new bo..