알고리즘 효율성

화성으로 탐사선을 보낸다는 소식을 들었습니다 우리는 이 탐사선을 위해 수가 소수인지를 판단하는 알고리즘을 써야 합니다 예를 들어, 이 탐사선이 RSA를 이용하여 통신을 하고 있다고 합시다 이 경우에는, 소수 판단 알고리즘이 내장되어 있어야 합니다 탐사선이든, 우주선이든 우주로 보내는 것을 설계할때는 모든 면에서 효율적이어야 합니다 탐사선을 이루는 부품들은 최대한 가벼워야 하고 부속 시스템들의 전력 소모량은 최소여야 하고요 탐사선을 설계하는 모든 과정에서 에너지와 무게를 절약해야 합니다 우리는 해야 할 일이 정해져 있습니다 이 정도 크기의 숫자를 판단할 수 있어야 하고 이 작업을 매우 빠르게 수행해야 합니다 예를 들어, 90이라는 매우 작은 숫자를 입력하면 이 알고리즘은 이 수를 계산하는 데 걸리는 시간에 가깝게 이를 계산할 수 있어야 합니다 입력 숫자가 커지면서 눈에 띄게 프로그램이 느려지는 현상은 피하고자 합니다 저는 몇몇 사용자들이 남긴 질문을 수학적 관점에서 분석해 보고자 합니다 매우 좋은 질문들이었는데요 우리는 숫자 n이 소수인지 아닌지를 판단하려고 합니다 어느 숫자 n에 대하여, n이 될 수 있는 모든 수의 집합을 생각해 보세요 n이 100이면 이 집합은 2부터 100까지의 숫자입니다 알고리즘이 할 일은 바로 이 집합을 탐색하는 것입니다 한 알고리즘이 어느 공간을 수색하고 있습니다 각 숫자에 다다를 때마다 한 단계라고 생각하세요 아주 기초적인 단계라고요 이 알고리즘은 질문을 하고 있는데요 이 질문은 어느 숫자가 합성수인지를 묻는 질문입니다 숫자 A가 있으면 N이 A로 나누어지는지를 확인해보는 알고리즘이 되겠죠 숫자 A를 여기 놓은 다음 N을 A로 나누는데 나머지가 0이면 N이 A로 나누어떨어짐을 알 수 있고 우리는 A가 N의 약수임을 알 수 있으며 숫자 N이 합성수임을 100% 확신할 수 있습니다 숫자 N이 합성수가 아니라면 계산 과정 내내 불확실합니다 소수일 수도 있지만 확실하지 않습니다 공간 안의 모든 수들을 다 대입해 보아야 하지요 기억하세요, 이 경우에서의 숫자 제한은 N의 제곱근이었습니다 최악의 경우는 N이 소수일 때인데요 이때 우리는 N의 제곱근까지만 수색하고 N은 소수인것을 100% 확신할 수 있습니다 N이 두 소수의 곱인 경우에도 예를 들어 7*7=49의 경우에서 49를 우리 알고리즘에 입력하면 최악의 경우가 발생하죠 N의 제곱근까지 갑니다 첫번째 질문은요, 예를 들어 TheFourthDimension님께서는 이렇게 질문하셨습니다 어떤 수가 2로 나누어떨어지지 않으면 2의 모든 배수들로도 나누어지지 않을 것이고 3, 4, 5 등의 수도 마찬가지로 각 수로 나누어 지지 않으면 각 수의 배수도 그렇지 않을까요? 매우 좋은 지적이네요 우리의 기존 알고리즘은 모든 수로 일일이 나누어 계산했지만 우리가 합성수에 대해 아는 패턴을 이용해 볼 수 있습니다 예를 들어, 어떤 수가 2로 나누어지면 우리는 이가 합성수임을 알 수 있습니다 소수인 2보다 크면요 4는 합성수라고 할 수 있습니다 여기 5를 빠트렸네요, 죄송합니다 4, 6, 8, 10, 아니면 이런 식으로도 셀 수 있습니다 3,5,7,9 이 과정은 우리가 탐색해야 하는 공간을 줄일 것입니다 모든 짝수를 제거하면 우리가 탐색해야 하는 공간은 N의 제곱근이 아니라 N의 제곱근을 2로 나눈 것일 것입니다 우리는 합성수에서 또 다른 패턴을 찾아 이 공간을 더욱 줄일 수 있습니다 이 다른 질문은 우리가 목격자 합성수를 찾는 경우를 다루고 있습니다 이를테면, N은 합성수입니다 라고 결론짓게 할 수 있는 숫자 A를 찾는 것 말이죠 Lola님께서는 이 수가 소수임을 밝힌 즉시 반복문을 떠나는 것이 시간을 절약하지 않을까요? 라고 물으셨습니다 아주 맞는 말입니다 우리가 하고자 하는것이기도 하고요 우리가 사용하는 패턴에 따라 과정을 전개하기 시작하면 목격자 합성수를 발견하게 됩니다 이는 이 수가 시험을 통과하며 일찍 멈추어도 된다는 신호입니다 작업을 멈추고, 합성수임을 밝혔으니 더 이상 탐색하지 않아도 됩니다 이 기능은 매우 유용하나 수가 소수일 때는 도움이 전혀 되지 않습니다 이때는 일찍 멈추는 것이 도움이 안 됩니다 자, 이러한 새로운 기능이 어떻게 공간을 줄여 컴퓨터 내에서 일어나는 작업의 횟수를 줄이는 데 기여하는지 볼 수 있는데요 물론 이는 컴퓨터에 따라 다르지만 전체적으로 시간을 줄이는데 기여할 것입니다 이제 제가 아래에 제작해 놓은 이 정보의 시각화를 보여드릴 텐데요 이는 우리가 두 알고리즘을 작업 횟수에 따라 비교할 수 있도록 해 줍니다 왼쪽에는 알고리즘 A가 있는데요 N을 N의 제곱근 이하에서 2까지의 모든 수를 대입합니다 오른쪽에는 알고리즘 B가 있는데요 이는 말하자면 우리의 향상된 알고리즘입니다 이 경우에서는 N이 2로 나눠지면 2의 배수들은 대입하지 않는 기능을 포함시켰습니다 또한, 합성수임을 구하면 이 프로그램은 일찍 끝납니다 완벽하진 않지만 저는 몇 가지 새로운 기능을 포함시켜 어떻게 되는지 지켜보겠습니다 이제, 이를 실제로 보여드리겠습니다 여기에 보시다시피 알고리즘 A가 있습니다 출력값이 있고 합성수인지 소수인지는 모릅니다 아래에는 작업 횟수가 나와 있습니다 눈에 띄는 건 오른쪽의 알고리즘 같은 경우에는 두 수마다 작업은 하나만 한다는 겁니다 우리는 이 이유를 압니다 이와 같이 짝수일 경우에는 바로 프로그램은 멈출 것입니다 기존 알고리즘은 314번의 작업을 거쳤는데 우리의 새 알고리즘은 한 번의 작업만 거칩니다 2로 나누어지는지 확인을 하기 때문이죠 매우 훌륭하게 최적화시켰네요 그럼에도 불구하고 수가 커지면서 작업 수가 늘어나고 컴퓨터가 오작동하게 되는 지점에 다가가면서 작업수를 나타내는 바는 커지고 붉게 변합니다 이 위쪽의 붉은 선은 작업 수의 한계를 나타냅니다 이 바가 여기에 다다르면 프로그램은 실패하고 우리의 탐사선은 고장이 나겠죠 이 경우에는 브라우저 자체가 오작동 할 것입니다 최대한 가까이 가 보겠습니다 지금 이 선에 접근하니 컴퓨터가 매우 느려졌습니다 브라우저가 오작동할 것 같은 느낌이 드는군요 보시다시피, 개선된 알고리즘은 작업을 두번밖에 거치지 않았지만 최악의 경우도 염두에 두세요 제가 여기 몇 가지 매우 큰 소수를 준비해 왔는데요 우리는 어느 경우이든 다룰 수 있어야 합니다 알고리즘이 어떤 수를 만날지 모릅니다 여기다 큰 소수를 하나 입력하면 어떻게 되는지 보세요 알고리즘 B는 최악의 경우 A보다 절반 가량의 작업을 거치지만 최악의 경우이기 때문에 그래도 매우 많은 양의 작업을 거칩니다 시스템 오작동에 가까워지고 있는데요 이는 그리 큰 소수도 아닙니다 아직 15자리도 접근하지 않았지요 제가 이 12자리 소수를 알고리즘에 넣을 때 어떻게 되는지 살펴봅시다 랙이 걸리고 오작동할 기미가 보입니다 두 알고리즘 모두 선을 넘어섰습니다 성공하지 못했군요 우리의 알고리즘은 아직 충분히 쓸만하지 않습니다 그래도 이제 우리는 우리가 무엇을 고쳐야 하는지 알고 있습니다 이 경우에서는 작업의 횟수입니다 우리의 입력물이 커지면서 생기는 작업 횟수의 증가를 시각화시킬 수 있는 기능도 있습니다 나중에, 직접 알고리즘을 하나 써보고 기존 알고리즘과 비교할 수 있도록 이를 쓰는 방법을 아래에서 가르쳐 드리겠습니다