..

에라토스테네스의 체 알고리즘의 변형. k번째 수를 출력하는 것으로 처음엔 하려고 했는데 뭔가 잘못되었는지 계속 틀렸다고 나와서 입력 범위도 크지 않으니까 그냥 배열에 다 몰아서 k번째 수를 출력하는 것으로 풀었다.

EASY

에라토스테네스의 체 알고리즘을 사용하여 100점을 받았다. Swift로 완전히 같은 코드를 짜서 돌렸는데 말도 안되게 느리다... 진짜 말도 안되게 느려... 그래서 25점밖에 받지 못했다.

에라토스테네스의 체를 사용하여 1부터 입력 까지의 소수를 구하고, 두 소수의 차가 작은 골드바흐 파티션을 출력해야 하므로 입력 / 2 에서부터 시작하여 해당 값이 소수이면 입력 에서 입력 / 2 를 뺀 값도 소수인지 판별하고 둘 다 소수이면 골드바흐 파티션을 출력하고 해당 반복문을 빠져나간다.

구간 내의 소수를 판별해야 하므로 에라토스테네스의 체 알고리즘을 사용해야 시간초과가 나지 않는다.

무제 Java ArrayList 의 배열을 생성해 주고, 배열의 각 요소에 대해서도 ArrayList 를 초기화해주어야 한다. ArrayList 의 인덱스는 시작 정점을 나타내고, 그 요소의 ArrayList 의 요소는 시작 정점과 연결되어 있는 정점을 나타낸다. Swift [[Int]] 형의 배열을 생성하고, 인덱스로 접근하기 위해 repeating 할 수 있는 생성자를 이용하여 초기화한다. Java 로 풀 때처럼 그래프를 저장한다. BFS 시작 정점에 대하여 탐색되었다고 체크하고, 그 정점을 Enqueue 한다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐의 요소를 Dequeue 한다. 그 요소와 이어져 있는 정점들을 순회하면서, 정점이 탐색된 상태가 아니라면, 탐색된 상태로 변경하고, 큐에 넣는다...

import java.io.*;import java.util.*; class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int count = Integer.parseInt(in.readLine()); int[][] array = new int[count][2]; for(int i=0; i

문자열 처리. 하지만 KMP 알고리즘 이라는 관련 알고리즘이 따로 있는 것 같다. 나중에 공부해보자...

import java.io.*;import java.util.*; class Edge { int start; int end; Edge(int start, int end) { this.start = start; this.end = end; }} class Main { static boolean[] isChecked; static Edge[] array; public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int cases = Integer.parseInt(in.readLine()); for(int i=0; i

import java.io.*;import java.util.*; class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int count = Integer.parseInt(in.readLine()); String[] input = in.readLine().split(" "); final int base = Integer.parseInt(input[0]); for(int i=1; i