수 록

이전 글 에서 에라토스테네스의 체를 알아보았습니다. 같은 방법으로 백준 6588, 골드바흐의 추측문제를 풀어보도록 하겠습니당. 먼저 문제를 살펴보면 "4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다" 고 합니다. 이 골드바흐의 말을 검증하는 프로그램을 작성하는건데요, 문제의 예시를 표로 정리해 보겠습니다. 4 보다 큰 짝수 두 홀수 소수 20 3 + 17 7 + 13 42 5 + 37 11 + 31 13 + 29 19 + 23 다음으로 입력을 살펴 보겠습니다. 입력으로는 6 이상, 1,000,000 이하 짝수 정수가 주어진다 합니다. 구해야 할 소수의 범위는 1,000,000 까지임을 알 수 있습니다. 테스트 케이스의 숫자 갯수는 주어지지 않았고, 입력에 0 이 주어지면 테스트 케이스 입력..

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 소수 구하는 문제는 에라토스테네스의 체를 이용하는게 가장 편리합니다. 소수란 ? 양의 약수를 두 개만 가지는 자연수. 1과 자기자신으로만 나누어지는 수 위키 백과에서 가져온 그림을 토대로 설명을 하면, 2 부터 목표 수(120) 사이 자기 자신을 제외 한 자신 배수를 모두 지우는 것입니다. 자바 코드로 살펴보겠습니다. public class Eratos { public static void main(String[] args){ int start = 1; int end = 120; // 소수인지 판별하기 위해 길이가 end + 1 인 배열 선언 // 마지막 수도 포함 하기 위해 (end + 1)사용 함. ..

시간 복잡도 주어진 문제 해결을 위한 연산의 횟수를 말한다. 일반적으로 1억번의 연산을 1초의 시간으로 간주해 예측함. 시간 복잡도 유형 빅 - 오메가 (Ω(N)) 최선의 연산 횟수를 나타냄 빅 - 세타 (Θ(N)) 보통의 연산 횟수를 나타냄 빅 - 오 (O(N)) 최악의 연산 횟수를 나타냄 알고리즘에서 빅 - 오 표기법 (O(N)) 을 기준으로 시간을 계산해야한다. 즉, 가장 최악을 염두해 두고 문제를 풀어 나가야한다는 것! 시간 복잡도 도출하기 1. 상수는 계산에서 제외 ex ) 2N + 1 → O(N) , 6N² → O(N²) 상수는 시간계산에 크게 영향을 끼치지 않는다. 2. 식의 값을 가장 큰 대표항만 남겨서 나타낸다. ex ) N² + N→ O(N²) 예시 1. ) N 이하의 자연수 중 3의 ..