본문 바로가기
반응형

전체 글1305

[BOJ] 백준 1747 소수&팰린드롬 출처: https://www.acmicpc.net/problem/1747 Input 31 Output 101 소수(Prime Number)이면서 팰린드롬을 만족하는 숫자를 찾는 문제이다. ※ 아래 두 게시글 참고 - [BOJ] 1259 팰린드롬수 [BOJ] 백준 1259 팰린드롬수 출처: https://www.acmicpc.net/problem/1259 Input 121 1231 12421 0 Output yes no yes 팰린드롬은 [radar], [sees]와 같이 앞뒤로 읽어도 똑같은 단어를 의미한다. 처음 지점 [s]와 끝 지점 [e]에서 부터.. zoosso.tistory.com - 소수(Prime Number) 찾기 소수(Prime Number) 찾기 - 1 zoosso.tistory.com.. 2021. 2. 21.
소수 (Prime Number) 찾기 - 3 해당 게시글은 에라토스테네스의 체를 이용해서 소수 찾기를 구현한 게시글입니다. - 소수 (Prime Number) 찾기 - 1 - 소수 (Prime Number) 찾기 - 2 ★ 에라토스테네스의 체의 핵심은 소수의 배수를 제외 시키는 것이다. 출처: WIKI ▶ 다음과 같이 2~50까지의 숫자가 존재한다. (1은 소수가 아니므로 제외) ▶ 먼저, 『2』의 소수 여부를 판단한다. 소수라면 『2』의 배수를 모두 제외시킨다. (『2』로 나누어지는 합성수들이기 때문.) ▶ 마찬가지로 『3』에 대해서도 동일하게 처리하면 다음과 같다. ▶ 『4』는 앞서 『2』의 배수에서 처리되었으므로 넘어간다. ▶ 이러한 방법으로 소수의 배수를 제외 시키면 소수 여부를 판단하는 대상이 좁혀지기 때문에 효율적이다. 결과적으로 아래 .. 2021. 2. 21.
소수 (Prime Number) 찾기 - 2 해당 게시글은 제곱근 범위를 이용해 소수 찾기를 구현한 내용입니다. - 소수 (Prime Number) 찾기 - 1 - 소수 (Prime Number) 찾기 - 3 해당 숫자의 소수 여부를 판단할 때 해당 숫자의 루트값까지만 계산한다. 이때 나누어 떨어지지 않으면 소수가 아니다! Q) 왜 소수 검사할 때 N의 제곱근까지만 할까? A) N은 소수가 아닌 합성수로 A * B = N 이 가능하다. (A > B) N의 제곱근을 X라고 두면, N = A * B = X * X 성립한다. A > X 라고 하면, B ≤ X가 되어야 하므로 B ≤ X < A 가 되므로 소수를 찾을 때, 제곱근 X (≥ B)까지만 찾으면 확인할 수 있다. 소수 (Prime Number) 찾기 - 1방식과 비교하면 연산 범위를 [2, N].. 2021. 2. 21.
[BOJ] 백준 1259 팰린드롬수 출처: https://www.acmicpc.net/problem/1259 Input 121 1231 12421 0 Output yes no yes 팰린드롬은 [radar], [sees]와 같이 앞뒤로 읽어도 똑같은 단어를 의미한다. 처음 지점 [s]와 끝 지점 [e]에서 부터 거리를 좁혀가며 일치여부를 파악한다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true) { int N = Integer.parseInt(sc.next()); if (N == 0) return; if(isPalindrome(N)) { Syste.. 2021. 2. 21.
[BOJ] 백준 2581 소수 출처: https://www.acmicpc.net/problem/2581 Input 60 100 Output 620 61 m(=60)과 n(=100) 사이의 소수 : 61, 67, 71, 73, 79, 83, 89, 9 (소수가 없는 경우 '-1' 출력) m과 n 사이에 소수가 존재 유무에 따라 소수들의 합과 최솟값 도출. ▶ 소수(Prime Number) 찾기 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = Integer.parseInt(sc.next()); int n = Integer.parseInt(sc.next(.. 2021. 2. 21.
[BOJ] 백준 1978 소수 찾기 출처: https://www.acmicpc.net/problem/1978 Input 4 1 3 5 7 Output 3 배열 원소 중 소수를 찾는 기본 문제이다. ※ 소수(Prime Number)란? 1과 자기자신으로만 나누어 떨어지는 수를 의미. ※ 『1』은 소수가 아니다. ※ 소수(Prime Number) 찾기 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = Integer.parseInt(sc.next()); int[] arr = new int[n]; for(int i=0; i 2021. 2. 20.
소수(Prime Number) 찾기 - 1 소수(Prime Number)란? 1과 자기자신으로만 나누어지는 숫자 ex) 2, 3, 5, 7, ... ★ 소수를 구하는 방법은 크게 3가지 방식이 존재한다. ① 2 ~ N-1 까지 나누어지는지 확인 ② 2 ~ √N 까지 나누어지는지 확인 ③ 에라토스테네스의 체 각 방식을 통해서 효율적인 알고리즘에 대해 알 수 있습니다. 해당 게시글에서는 첫번째 방법에 대해서만 먼저 작성합니다. - 소수 (Prime Number) 찾기 - 2 - 소수 (Prime Number) 찾기 - 3 소수 여부 확인할 때, 가장 먼저 떠오르는 구현 방법은 정의(Definition)를 이용하는 것이다. 즉, 특정 숫자 「X」 에 대해서 2 ~ X - 1 까지 나누어 떨어지는 경우가 있는지 확인하는 방법이다. 직관적인 방법이지만 여.. 2021. 2. 20.
[BOJ] 백준 10211 Maximum Subarray 출처: https://www.acmicpc.net/problem/10211 Input 2 5 1 2 3 4 5 5 2 1 -2 3 -5 Output 15 4 연속된 부분 합 (연속합) 내용 참고 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = Integer.parseInt(sc.next()); while(T-- > 0) { int N = Integer.parseInt(sc.next());; int[] arr = new int[N]; for(int i=0; i 2021. 2. 20.
연속된 부분 합(연속합) - 1 (완전 탐색) ※ 구간합을 구하는 효율적인 방법 연속된 부분 합(연속합) - 1 (완전 탐색) 연속된 부분 합(연속합) - 2 (Prefix Sum) 연속된 부분 합(연속합) - 3 (DP) [구간합] Sum of sub-matrix (2D Array) 완전 탐색 Q) 아래와 같이 배열이 주어질 때 특정 연속 구간의 합 중 최대값을 구하시오. if) 구간의 길이가 5 일 때, 구간의 최대합은? 길이 6을 가지는 시작 지점(start) ~ 끝 지점(end)까지 합을 매번 더해서 구할 수 있습니다. (Sliding Window 혹은 Inchworm Algorithm) 직관적이지만 시간복잡도가 좋다고 할 수는 없습니다. [O(N3) 코드] int ans = 0; int N, A[LM]; void findPartialSum(.. 2021. 2. 20.
[BOJ] 백준 1914 하노이 탑 출처: https://www.acmicpc.net/problem/1914 Input 3 Output 7 1 3 1 2 3 2 1 3 2 1 2 3 1 3 Sample Output을 분석하면 어떻게 옮겨지는지 알 수 있습니다. 이를 재귀적으로 해결할 수 있습니다. 1. 제일 큰 원반을 제외한 N-1개의 원반들을 A 기둥에서 B 기둥으로 이동시킵니다. 2. 제일 큰 원반 한개를 A 기둥에서 C 기둥으로 이동시킵니다. 3. 1번에서 옮겨진 원반들을 B기둥에서 C 기둥으로 이동시킵니다. : 시작점과 도착점이 있고, 도달하기 위한 중간점을 이용해야만 합니다. 문제조건상 N > 20인 경우는 원반들이 옮겨지는 횟수만 구하면 되는데 결국 (2N - 1)을 출력하면 됩니다. ← 수학적으로 증명 하지만 2100은 lon.. 2021. 2. 20.
반응형

티스토리툴바