에라토스테네스의 체란 수학에서 소수를 찾는 방법입니다. 대량의 소수를 찾아야할 때 효과적이며, 소수를 직접 찾는 것이 아니라 일정 범위를 정해놓고 소수가 아닌 수를 지워나가는 것에 가깝습니다. 구현 순서 소수를 판별할 범위 만큼 배열을 할당 2부터 시작해서 범위 최대값의 제곱근까지 루프를 돌면서 소수일 때, 현재 수를 제외한 그 수의 배수에 해당하는 수를 지움(이미 지운 수는 건너뜀) 남아있는 수는 전부 소수 제곱근까지만 확인해도 되는 이유는? 소수를 판별할 범위가 2 ~ n 까지라고 하면, n의 약수는 \(n^{0.5}\)이하이므로 \(n^{0.5}\)까지만 탐색합니다. 결론적으로 제곱근 이상 수들은 이미 한번 지운 것들을 재방문 하는게 됩니다. 코드 n = 1000 is_prime = [True] *..

Next Permutation Algorithm은 순열 알고리즘 중에 하나로 무작위 순열의 다음 순열을 구하는 알고리즘입니다. 시간 복잡도는 O(N)이고 Greedy 알고리즘을 기반으로 합니다. 아래의 수열을 예로 다음에 올 순열을 구해보겠습니다. 5가지의 무작위 숫자가 주어지고 이를 N 배열에 저장합니다. Greedy를 이용하여 N[i] N[i]를 만족하는 j값을 구합니다. 바로 직전 반복문에서 N[i] < N[i + 1]을 만족했기 때문에 j는 최소한 하나는 무조건 존재합니다. j를 찾았으면 N[i]와 N..