본문 바로가기

전체 글

 (263)
[백준] 10451 : 순열 사이클 JAVA 풀이 입력받는 방식을 제외하면 연결 요소의 개수를 세는 문제와 풀이가 같은 문제였다. import java.io.*; import java.util.*; public class Main { static int[][] graph; static boolean[] visit; static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 테스트케이스의 개수를 입력받음 int T = Integer.parseInt(br.readLine()); // 테스트케이스의 개수만큼 반복 for(int i=0;i
[백준] 11724 : 연결 요소의 개수 JAVA 풀이 우선 연결 요소가 무엇인지 몰라서 검색을 해봤다. 그래프 상에서 이어져 있는 모든 정점들이 있을 때 그것을 하나의 연결 요소라고 한다. 따라서 위 이미지에서는 3개의 연결 요소가 존재한다고 할 수 있다. 연결 요소의 개수를 구하는 방법은 간단하다. 아직 방문하지 않은 정점에 대해 BFS 또는 DFS를 수행하고 그때마다 연결 요소의 개수를 추가해주면 된다. 시작 정점에 대해 BFS 또는 DFS를 수행하면 인접 정점들을 모두 방문하게 되는데 이것은 하나의 연결 요소를 훑은 것과 같은 의미이기 때문이다. import java.io.*; import java.util.*; public class Main { static int[][] graph; static boolean[] visit; static int N..
[백준] 1260 : DFS와 BFS JAVA 풀이 인접행렬 방식으로 풀었다. import java.io.*; import java.util.*; public class Main { // 인접행렬 생성 static int[][] graph; // 방문했는지 확인하기 위한 행렬 static boolean[] visit; // 정점의 개수 static int N; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); // 정점의 개수 N = Integer.parseIn..
[백준] 1158 : 요세푸스 문제 JAVA 풀이 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Queue queue = new LinkedList(); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); // 1부터 N까지의 숫자를 큐에 넣음 for(int..
[백준] 10866 : 덱 JAVA 풀이 기본적인 ArrayList 클래스의 메서드로 풀었다. deque로 푸는 건 또 나중에... import java.io.*; import java.util.*; public class Main{ static ArrayList list = new ArrayList(); public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); for(int i=0;i
[백준] 6588 : 골드바흐의 추측 JAVA 풀이 에라토스테네스의 체로 소수를 판별하고 그 소수들을 ArrayList에 추가한다. 리스트를 앞과 뒤에서부터 읽어 a+b가 n이 되면 출력을 한 뒤 반복문을 종료한다. 이런 식으로 코드를 작성해볼까 했는데 너무 비효율적인 것 같아 방향을 틀었다. 초기에 구상한 코드 import java.io.*; import java.util.*; public class Main { static boolean[] prime = new boolean[1000001]; static ArrayList list = new ArrayList(); public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new Inp..
[백준] 2004 : 조합 0의 개수 JAVA 풀이 팩토리얼 0의 개수 문제와 유사한 문제였다. 뒷자리가 0이라는 건 2와 5가 곱해졌다는 뜻이므로 분모와 분자가 서로소일 때 분자에 남은 2와 5가 짝을 이루는 쌍의 개수가 몇개인지 세면 되겠다는 생각이 들었다. N = 25, M = 12 가 입력됐을 경우 분자는 25 ~ 25-12+1인 14까지를 곱한 값 분모는 12부터 1까지를 곱한 값이 된다. twoCnt = 분자의 2의 개수 - 분모의 2의 개수 - 필요없는 구간의 2의 개수 fivecnt = 분자의 5의 개수 - 분모의 5의 개수 - 필요없는 구간의 5의 개수 두 개의 값을 구한 뒤 더 작은 값을 출력하도록 했다. (여기서 필요없는 구간이란 25~14 이외의 구간이다.) 두 개의 값 중 더 작은 값을 구하는 이유는, 2와 5가 짝을 이룰 때 뒷자..
[백준] 2089 : -2진수 JAVA 풀이 음..자꾸 오답 판정이 나와서 다른 사람들의 풀이과정을 참고했다. 예제 입력에 나온 -13은 -13 = (-2) * 7 + 1 7 = (-2) * 3 + 1 -3 = (-2) * 2 + 1 2 = (-2) * (-1) + 0 -1 = (-2) * (1) + 1 1 = (-2) * 0 + 1 이렇게 풀어볼 수 있다. 노란색으로 표시한 숫자를 아래부터 읽으면 110111 예제 출력과 일치하는 것을 확인할 수 있다. 여기서 첫 번째 식에 주목하자. 사실 -13 / -2를 계산하면 몫이 6이 되고 나머지가 -1이 되어 -13 = (-2) * (6) + (-1)이 된다. 하지만 -2진수는 각 자리에 0또는 1만 올 수 있기 때문에 문제가 발생한다. 따라서 이렇게 n % -2의 결과가 -1인 경우에는 몫에 +1을 ..

티스토리툴바