https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net ㅇ 문제 입력한 수를 만족하는 소수의 합을 구하는 문제이다. 소수를 찾아야 하니 에라토스테네스의 체를 이용해여 접근한다. ◆ 핵심 아이디어 1. 입력값까지의 소수를 구해야 한다. 2. 입력값의 소수의 합을 출력한다. 3. 소수의 합(골드바흐 파티션)이 여러 개일 경우, 두 소수의 차이가 가장 적은 것을 출력한다. 4. 소수는 작은 것부터 출력한다. ◆ 에라토스테네스의 체 htt..
ㅇ 소수란? 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 예를 들어 10보다 작은 소수는 2, 3, 5, 7이 있다. ㅇ 소수 찾기 소수를 찾는 방법은 총 3가지가 있다. 1. N을 N보다 작은 자연수로 모두 나누기 2. N의 제곱근보다 작은 자연수로 모두 나누기 3. 에라토스테네스의 체 이용하기 ㅇ N보다 작은 자연수로 나누기 첫번째 방법은 매우 간단하면서 기초적인 방법이다. N보다 작은 수로 모두 나누어 만약 나누어 떨어지는 것이 없다면 N은 소수일 것이다. 예를 들어보자. 만약 6이 주어졌을 때 1보다 크고 6보다 작은 수, 2, 3, 4, 5로 모두 나누어보자. 6 / 2 = 3 6 / 3 = 2 6 / 4 = 1 ... 2 6 / 5 = 1 ... 1 6은 2와 3으로 나누어 떨어..
ㅇ 알고리즘이란? 컴퓨터가 특정 문제를 해결하는 방식이다. 물론 특정 문제를 해결하는 방식이 많이 있지만, 그중에서도 효율적인 방식을 찾는 것이 중요하다. 이러한 효율적인 알고리즘을 찾는 기준은 시간복잡도이다. ㅇ 시간복잡도란? 알고리즘의 시간 복잡도는 성능을 나타내는 척도 중 하나로 알고리즘의 수행 시간을 나타낸다. 즉, 프로그램이 얼마나 많은 시간이 걸리는지를 나타내는 것이다. 다시 말하면, 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주한다. 시간복잡도가 큰 알고리즘은 작은 데이터에서도 느리게 동작하는 반면, 시간복잡도가 작은 알고리즘은 빠르게 동작한다. ㅇ 시간복잡도 유형 이러한 시간복잡도를 정의하는 3가지 유형이 있다. ①..
