개발 공부 블로그

소수구하는 방법 1: N√N 의 시간 복잡도 -> 2초 초과 x 임의의 자연수 N=16이라면 약수는 1,2,4,8,16 이 된다. *(pxq) 1x16 2x8 4x4 8x2 16x1 p와 q는 N의 약수이기 때문에 N을 임의의 수로 나누면 임의의 수가 √N 보다 작다면 결국 나머지는 √N 보다 클 수밖에 없다. 즉, p와 q중 하나는 반드시 √N 보다 작거나 같다. √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면 이는 1과 N을 제외한 다른 자연수가 N의 약수라는 의미이므로 소수가 아니게 됩니다. //소수 구하기 static boolean isPrime(int num) { for(int i=2; i

17836번: 공주님을 구해라! (acmicpc.net) 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 3 11 20 0 1 2 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 정답 : 14 출력 : 12 5 11 25 0 1 2 0 0 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 정답 : 20 출력 :..

17478번: 재귀함수가 뭔가요? (acmicpc.net) 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 풀이 1 import java.util.ArrayList; import java.util.Scanner; public class Main { static String s=""; static String s1="\"재귀함수가 뭔가요?\""; static String s2="\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어."; static String s3="마을 사람들은..

11729번: 하노이 탑 이동 순서 (acmicpc.net) 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net -> ArrayList로 담아서 출력했더니, 시간 초과 -> StringBuilder로 시간 초과 문제 해결 import java.util.ArrayList; import java.util.Scanner; public class Main { static int answer=0; static StringBuilder sb; public static void main(String[] args) ..

연결 요소(Connected Component) (velog.io) 연결 요소(Connected Component) 그래프 중에서는 위 그림과 같이 여러 개로 나누어져 있을 수도 있다. 위 그림을 보고 두 개의 그래프라고 볼 수도 있지만, 하나의 그래프에 두 개의 연결 요소를 가진다고 볼 수도 있다. 그 이유 velog.io 11724번: 연결 요소의 개수 (acmicpc.net) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net import java..

- N명중에서 5명만 친구관계여도 된다는 것 !!! - 각 사람이 4번 이상의 연결이 이루어져야 한다. - 관계의 가중치가 주어지지 않음 -> BFS보다 DFS import java.util.*; class Main { static ArrayList[] arr; static int answer=0; static int N; static boolean[] visit; public static void main(String args[]) throws Exception { Scanner sc=new Scanner(System.in); N=sc.nextInt(); int M=sc.nextInt(); arr=new ArrayList[N]; for(int i=0;i

3671번: 산업 스파이의 편지 (acmicpc.net) 3671번: 산업 스파이의 편지 각 테스트 케이스에 대해 종이조각을 적절히 배치해서 만들 수 있는 서로 다른 소수의 개수를 출력한다. 이때, 모든 종이 조각을 사용하지 않아도 된다. (7과 1이 있을 때, 만들 수 있는 소수는 7, www.acmicpc.net 백트래킹 import java.util.*; import java.io.*; public class Main3 { static boolean[] visit; static int N; static ArrayList arr; static String s; static char[] c; public static void main(String[] args) throws IOException { Bu..

1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main2 { static int M,N; static int[][] edge; static boolean[] visit; static StringB..

10026번: 적록색약 (acmicpc.net) 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net boolean[] v; Arrays.fill(v, false) : 모든 배열을 false로 초기화 import java.io.*; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Deque; import java.util.StringTokenizer; class Main { static int[] dx= {0,1,0,-1}; sta..

20291번: 파일 정리 (acmicpc.net) 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net TreeMap - 키값이 자동으로 정렬!! - map.keySet() String 함수 str.subString(i) : index i 부터 끝까지의 부분 문자열 str.indexOf(문자): 문자가 위치한 인덱스 리턴 str.contains(title): str 문자열이 title을 포함하는가 import java.util.*; public class Main { public static void main(String[..