[실전 알고리즘] 0x12강 - 수학

 

안녕하세요 여러분, 즐거운 수학 시간입니다. 비록 수학에 대한 원초적인 두려움을 가지고 있는 분이 많다는건 잘 알고 있지만 여기서 말하는 수학이라고 하는게 코딩테스트에서 수학이라는 문제 유형으로 분류되어 출제되는 정도의 개념을 말하는거라 막 컴공에서 배우는, 이름도 무시무시한 이산수학, 선형대수학, 미적분학, 확률과 통계 이런걸 이번 단원에서 다루는건 아닙니다. 필요한 개념 자체는 거의 다 중학교 수학 수준에서 해결이 되기 때문에 너무 겁내시지는 않으셔도 됩니다.

 

또 한편으로 사실 수학으로 분류된 알고리즘 문제들은 기업이 코딩테스트를 통해서 알고 싶어 하는 구현력 내지는 설계 능력을 확인하기에는 조금 적절하지가 않습니다. 그래서 대규모 공채처럼 문제를 직접 회사 측에서 준비를 하는 경우에는 수학 분야의 문제가 잘 안나옵니다. 그래서 비중을 조금 낮게 둬도 괜찮긴 하지만 문제 은행식으로 출제가 된다면 나올 가능성이 없다고는 할 수 없기 때문에 공부를 해두면 좋습니다.

 

이번 강의에서는 다양한 주제를 같이 볼 예정입니다. 사실 수학이라는 분류에 묶이는 문제들이 조금 중구난방이긴 합니다. 그래도 뭔가 얻어갈 수 있는게 분명 있어서 이번에 한 번 해두면 도움이 된다고 생각을 합니다.

 

맨 처음으로 소수에 대해서 알아보겠습니다. 소수의 정의를 먼저 보면 소수는 1과 자기 자신으로만 나누어지는 수, 같은 뜻이지만 다르게 표현하면 약수가 2개인 수입니다. 반면 합성수는 1과 자기 자신을 제외한 다른 약수를 가지고 있는 수를 말합니다. 그리고 1은 소수도 합성수도 아닙니다. 1이 소수가 아니라는 점은 헷갈리시면 안됩니다.

 

어떤 수가 소수인지 아닌지 어떻게 판단을 할지 생각해볼 때 정의를 그대로 이용하면 됩니다. 정의에 적혀있는 것 그대로 수가 1과 자기 자신으로만 나누어지는지, 즉 2부터 N-1까지의 수 중에서 그 수를 나누는 다른 수가 없는지를 보면 됩니다. 그래서 코드로 별로 어렵지 않게 구현을 할 수 있습니다.

 

아주 간단하게 구현을 할 수 있고 n가 1일 때에는 소수가 아니라고 판단을 해야 하기 때문에 02번째 줄과 같은 처리가 들어가야한다는 점은 꼭 생각을 하셔야 합니다. 다음으로 이 함수의 시간복잡도가 얼마인지 생각해봅시다. 보면 n을 i로 나누어보는 연산이 최대 n-2번, 즉 O(n)번 발생합니다. 그렇기 때문에 최종적으로 이 코드는 O(n)에 동작합니다.

 

그런데 간단하면서도 아주 중요한 관찰 한가지를 한다면 시간복잡도를 O(√n)으로 떨굴 수 있습니다. O(n)과 O(√n)의 차이는 굉장히 큽니다. 예를 들어서 n이 10¹² 정도일 때 O(n)은 절대 1초 내로 통과될 수 없는데 O(√n)은 충분히 넉넉하게 통과됩니다.

 

그러면 어떤 관찰이 필요하냐고 했을 때, 합성수 N에서 1을 제외한 가장 작은 약수는 √N 이하라는걸 알아야 합니다. 18, 25, 21로 예를 들어놨는데 N = 18이면 18에서 1이 아닌 가장 약수는 2입니다. 그리고 √18 = 4.xx 이니까 2가 √18 이하입니다. N = 25와 21에 대해서도 마찬가지의 성질이 잘 성립합니다. 이 성질이 시간복잡도와 무슨 상관이 있는지 잘 감이 오지 않을 수도 있는데 그 부분은 조금 있다가 설명을 하고 일단 지금은 저게 왜 성립하는지부터 생각해보겠습니다.

 

이게 사실은 인싸들은 다 알고 있는 증명이긴 한데, 아무튼 증명을 위해 합성수 N에서 1을 제외한 가장 작은 약수를 x라고 둡니다. 만약 N이 21이었다고 치면 x는 3입니다. 그러면 N/x는 자연스럽게 N의 약수입니다. 우리는 1을 빼고 나머지 약수들 중에서는 x가 가장 작다고 했기 때문에 x ≤ (N/x)이 성립합니다. 그러면 우변의 분모 x를 좌변으로 옮기고 났을 때 x² ≤ N이라는 식을 얻을 수 있고 최종적으로 x ≤ √N 이 성립합니다.

 

수학적 증명에 조금 약하다면 N, x와 같은 기호들이 나오면서 조금 헷갈릴 수 있는데 N = 21, x = 3과 같이 수를 하나 넣고 흐름을 그대로 따라가보면 그럭저럭 이해에 도움이 됩니다.

 

위의 증명을 통해 합성수 N에서 1을 제외한 가장 작은 약수는 √N 이하라는걸 알았습니다. 이 성질로부터 어떤걸 바로 알 수가 있냐면, 2부터 N-1까지의 수로 전부 나누어서 소수임을 판정하는 대신에 √N 까지만 나누어보면 된다는 사실을 알아낼 수 있습니다. 만약 합성수였다면 분명 2부터 √N 까지에서 N을 나누는 수가 있어야하고, 그러한 수가 없다면 소수라는걸 바로 알 수 있습니다.

 

그러면 아까의 코드에서 for문이 도는 범위만 조절을 하면 되는데 과연 제곱근을 어떻게 구할 수 있을것인가? 라는 의문이 자연스럽게 들거고 빠르게 검색을 해보신 분이라면 sqrt라는 함수가 있다는건 찾을 수 있습니다. 그런데 sqrt는 쓰면 안됩니다. 아주 까마득하겠지만 0x01강 - 기초 코드 작성 요령 I에서 어떤 얘기를 했냐 기억을 되새겨볼 때 실수의 저장/연산 과정에서 반드시, 오차가 발생할 수 밖에 없다는 얘기를 했습니다. 그리고 sqrt는 실수 연산이기 때문에 오차가 발생할 수 있습니다. 그러면 for문을 어떻게 고쳐야하는가 생각을 하면서 코드를 확인해보겠습니다.

 

제시한 코드와 같이 for문이 계속될 조건을 i*i <= n으로 쓰면 됩니다. 저렇게 쓰면 자연스럽게 i가 √N 이하일 때 까지 for문을 돌기 때문에 O(√n)에 소수를 판정할 수 있고 또 모든 연산을 정수에서 처리할 수 있습니다.

 

이 소수 판정법을 대놓고 그대로 가져다쓰면 되는 문제이긴 하지만 아무튼 직접 채점을 해볼 수 있는 문제를 소개하겠습니다. BOJ 1978번: 소수 찾기 문제를 보면 1000 이하의 수에 대해 소수인지를 판단할 수 있으면 풀 수 있고 직접 구현을 해봅시다.

 

제 코드에 대한 자세한 설명은 생략합니다.

 

이렇게 어떤 수 하나가 소수인지 O(√n)에 판단하는 방법을 같이 익혔는데, 만약 1부터 N까지의 모든 수에 대해 그 수가 소수인지 판단하는 알고리즘이 필요하면 어떤 방식으로 구현을 해야 할지 고민을 해봅시다. 가장 쉽게 떠올릴 수 있는 방법은 그냥 각 수가 소수인지 구하는 작업을 매번 반복하는 방법입니다.

 

1이 소수가 아닌건 이미 잘 알고 있으니 범위를 바로 2부터 시작했습니다. 각 수가 소수인지 판정하는게 O(√n)이고 이걸 n번 반복해야 하니 단순하게 계산하면 O(n√n)이지만 사실 N이 합성수면 √n번 나눗셈 연산을 하기 전에 이미 나누어떨어지는 j를 찾아서 break를 합니다. 예를 들어서 105를 생각해보면 3으로 나누자마자 나누어떨어지는걸 보고 break를 합니다. 그래서 생각보다는 빠르게 돕니다. N = 5,000,000일 때 대략 1.8초 정도 걸립니다.

 

그리고 개선을 해보자면, 각 수에 대해서 2부터 √n 사이의 수로 다 나누는 대신 2부터 √n 사이의 소수로만 나누면 됩니다. 자세하게 얘기는 안하겠지만 각 수의 1이 아닌 가장 작은 약수는 무조건 소수일 수 밖에 없어서 그런거고 그 점을 이용해서 이렇게 조금 더 개선을 할 수 있습니다.

 

이렇게 개선을 하고 나면 N = 5,000,000일 때 대략 0.4초가 걸립니다.

 

그런데 에라토스테네스의 체라는 이름의, 범위 내에서의 소수 판정을 하는 훨씬 효율적인 알고리즘이 있습니다. 이 알고리즘은 딱 한 번 보면 바로 이해가 되기 때문에 바로 보여드리겠습니다.

 

그림에 제시된 표는 원래 1차원 배열인데 슬라이드가 좁아서 2차원 배열인 것 처럼 그렸습니다. 1부터 N까지 소수의 목록을 구하고 싶다고 할 때 이렇게 N칸짜리 배열을 만듭니다. 이 배열은 해당 칸의 수가 소수일 경우 true, 소수가 아닐 경우 false의 값을 가집니다. 그림에서는 파란색이 true, 빨간색이 false에 대응됩니다. 초기값으로는 1만 false를 주고 나머지는 다 true를 줍니다.

 

그 다음으로 커서를 하나 둬서 2를 가리키게끔 합니다. 이 커서는 2부터 N까지 진행하면서 소수를 찾은 후에 뭔가 작업을 할 예정입니다.

 

이제 2의 배수인 다른 수들을 다 false로 만들 예정입니다. 2는 내버려두고 4, 6, 8, …을 전부 false로 만듭니다.

 

다음으로 커서를 다음 칸으로 옮깁니다. 현재 커서는 3을 가리키고 있습니다.

 

3도 파란 칸, 즉 소수니까 3은 빼고 다른 3의 배수들을 false로 만듭니다.

 

커서를 한 칸 옮겨보면 이번엔 4인데 4는 현재 빨간 칸입니다. 그러면 4는 소수가 아니라는 의미이기 때문에 그냥 넘어갑니다.

 

커서를 한 칸 옮겨서 5로 왔고 5는 파란 칸이니 소수여서 5의 배수들을 false로 만듭니다.

 

커서가 N에 도달할 때 까지 지금 작업을 계속 반복하면 됩니다. 최종적으로 이와 같이 소수만 파란 칸으로 남아있는걸 볼 수 있습니다. 이렇게 마치 체로 곡식을 거르는 것 처럼 합성수를 제거해나가는 알고리즘을 에라토스테네스의 체라고 부릅니다.

 

구현은 크게 어렵지는 않습니다. 진짜 그냥 앞에서 말한 그대로를 구현한거고 달리 설명이 필요한 부분은 보이지 않습니다. 사실 04번째 줄은 없어도 아무런 문제가 없긴한데 1이 소수가 아니라는걸 강조하는 의미에서 뒀습니다.

 

그런데 이 코드는 지금 수학적으로 개선이 가능합니다. 어떻게 개선을 할 수 있는지를 알려드리겠습니다.

 

그림에서 나타내고 있는 상황에서는 커서가 5를 가리키고 있고 5의 배수인 10, 15, 20, 25, 30, 35를 false로 만들 차례입니다. 그런데 이 5의 배수들을 보면 사실 이미 합성수로 판정이 되어있는 값들이 많습니다. 25와 35만 아직 true이고 나머지는 다 false입니다. 특히 25를 기점으로 앞과 뒤를 보면 혹시 뭔가 느낌이 오는게 없을까요?

 

일단 먼저 생각해야할건 지금 커서가 5에 있다고 했습니다. 그러면 커서는 2와 3을 거쳐왔고, 자연스럽게 5보다 작은 소인수를 가지는 합성수는 이미 다 걸러졌습니다. 한편으로 제가 25를 계속 강조했습니다. 왜 25를 얘기했냐면, 25보다 작은 5의 배수를 보면 10 = 2 ⨉ 5, 15 = 3 ⨉ 5, 20 = 4 ⨉ 5입니다. 이 값들은 각각 2, 3, 4로 나누어 떨어지고, 다른 말로 표현하면 이들은 5보다 더 작은 소인수가 존재한다는 의미입니다. 즉 커서가 5인 지금 신경을 쓰지 않더라도 이전에 다른 커서에서 이미 false로 바뀌어있다는 의미이고, 우리는 5² = 25부터 false로 바꿔나가면 됩니다. 이 최적화를 적용한 코드를 보겠습니다.

 

코드를 보시면 05, 07번째 줄이 전부 바뀌었습니다. 07번째 줄은 앞에서 설명한 이유 그대로고, 05번째 줄은 i*i가 n보다 커지게 되면 더 이상 아무 값도 바꾸지 않기 때문에 저렇게 개선을 했습니다.

 

또 조금 불필요한, 혹은 과도한 내용일 수도 있어서 아주 얕게만 설명을 하려고 하는 내용이 있습니다. 한 번 확인은 해보시되 잘 이해가 안가면 패스해도 괜찮습니다. 지금 state의 자료형이 vector<bool>입니다. 그런데 만약 자료형을 저게 아니라 bool 배열로 둔다면, 즉 bool state[n]; 으로 정의를 한다면 시간이 꽤 느려집니다. 왜 그런거냐면 아시다시피 bool은 true 혹은 false를 저장하는 자료형인데 사실 정확한 크기는 char처럼 1 byte입니다. 그런데 vector<bool>로 두면 각 bool 한 칸이 1 byte가 아니라 1 bit만 차지하도록 최적화가 이루어집니다. 이 최적화 덕분에 공간도 8배 적게 쓰고, 그리고 결정적으로 cache hit rate가 올라가서 시간도 빨라집니다. 그래서 state를 int 배열이나 vector<int>나 bool 배열로 두는 것 보다 vector<bool>로 두는게 훨씬 좋습니다. 그렇긴 한데 조금 마이너한 내용이기도 하고 이걸 잘못 썼다고 해서 원래 통과되어야할게 시간 초과가 난다거나 하는 일은 잘 없기 때문에 그냥 현대인의 상식 정도로만 받아들이고 넘어가겠습니다.

 

아무튼 이렇게 최적화를 끝내고 나면 시간복잡도는 O(NlglgN)이라는, 생전 처음 볼 시간복잡도가 나오고 N = 10,000,000일 때 0.06초,  N = 50,000,000일 때 대략 0.5초 안에 계산이 끝납니다. 즉 거의 O(N)이라고 보면 될 정도로 굉장히 빠르게 돈다는 얘기입니다.

 

또 위에서 언급한 최적화들을 하지 않더라도 N = 20,000,000일 때 state의 자료형을 vector<bool>로 두면 0.19초, bool 배열로 두면 0.3초, int 배열로 두면 0.58초 정도로 충분히 빠르게 동작합니다. 출제자의 입장에서 에라토스테네스의 체를 아는지 물어보고 싶다고 해도 무식하게 1부터 50,000,000까지 이런 식으로 범위를 잡지는 않을 것입니다. C++ 말고 파이썬같은 다른 언어로 푸는 사람도 고려해서 범위를 잡아야 하니 아무리 크게 잡아봐야 10,000,000 안쪽일거고. 그렇기 때문에 최적화쪽 얘기는 잘 이해가 안가면 패스해도 괜찮습니다. 다만 vector<bool>은 자료형만 저것으로 써주면 cache hit rate이 올라가서 성능이 확 좋아지는데다가 혹시 코딩테스트 이후에 내가 코드 짠거 가지고 면접같은게 추가로 진행되면 나의 유식함을 뽐낼 수 있는 기회가 되니까 살짝 눈도장을 찍어두는 것도 괜찮겠다 하는 생각이 살짝 듭니다.

 

코드도 검증할 겸 BOJ 1929번: 소수 구하기 문제를 풀어보겠습니다. 문제에서는 M 이상 N 이하의 소수를 구하라고 하는데 에라토스테네스의 체를 이용해서 해결이 가능합니다. 에라토스테네스의 체로 1부터 N까지의 수에 대해 소수인지 여부를 구하고, 적절하게 출력을 하면 됩니다.

 

직접 m부터 n까지의 각 수들에 대해 그 수가 소수인지 판단하는 방법으로 구현해보고 제출해서 시간이 얼마나 차이나는지도 짜서 확인해보면 좋은 연습이 될 것 같습니다.

 

소수 관련해서 마지막으로 다룰 주제는 소인수분해입니다 소인수분해는 정수를 소수의 곱으로 나타내는 것을 의미합니다. 예를 들어서 1100 = 2 ⨉ 2 ⨉ 5 ⨉ 5 ⨉ 11입니다. 모든 자연수는 소인수분해하는 방법이 딱 한 가지만 있다는 사실은은 그럭저럭 유명한 사실입니다. 참고로 각 자연수를 소수들의 곱으로 표현하는 방법이 유일하다는건 산술의 기본정리라는 거창한 이름이 붙어있는 정리입니다. 그런데 그렇게까지 깊게 얘기하고 싶은 마음은 없고 그냥 각 자연수를 소수들의 곱으로 표현하는 방법이 유일하다는게 당연한건 아니구나, 그리고 수학적으로 증명이 가능한데 거기까지는 필요가 없고 받아들이면 되는구나 정도로만 생각하고 가겠습니다.

 

그러면 이 소인수분해를 구현하려고 하면 어떻게 해야할까요? 생각보다 좀 막막한데, 수 N이 주어졌을 때 소인수분해를 하라고 하면 맨 처음 해볼 수 있는 시도는 N 이하의 모든 소수를 에라토스테네스의 체로 다 찾은 다음에 그 소수들로 N을 나누어보는 시도입니다. 굉장히 좋은 시도이지만 더 좋은 방법이 있어서 소개를 하겠습니다.

 

이것도 에라토스테네스의 체처럼 일단 방법을 보여드리고 설명을 하겠습니다. 바로 1100을 소인수분해하는 과정을 같이 보겠습니다. 쓰이는 변수를 보면 N에는 소인수분해를 할 수를 담아두고 i는 2로 시작해서 1씩 증가합니다. 소인수 목록은 말 그대로 소인수의 목록을 저장할 곳입니다. 이제 뭘 하냐면, 우선 N이 i로 나누어지는지 확인합니다. 즉 N에서 소인수를 뽑아내는 상황입니다. 1100은 2로 나눠지기 때문에 소인수 목록에 2를 추가하고 N을 2로 나눕니다.

 

이 작업을 N이 i로 나누어지지 않을 때 까지 계속 반복합니다.

 

N은 275가 되었고 N은 더 이상 i로 나누어지지 않습니다. 그러면 이 때 i를 1 증가시킵니다.

 

i는 3이 됐지만 여전히 N은 i로 나누어지지 않습니다. 또 다시 i를 1 증가시킵니다.

 

i는 4가 됐지만 여전히 N은 i로 나누어지지 않습니다. 또 다시 i를 1 증가시킵니다.

 

현재 i는 5고 N은 i로 나누어집니다. i가 2일 때 한 것 처럼 5로 계속 나누겠습니다.

 

이렇게 5를 2개 뽑아냈고 N은 11이 됐습니다. 이제 N은 i로 나누어지지 않으니까 i를 1 증가시킵니다. i는 5, 6, 7, 8, 이렇게 올라갈텐데 생략하고 바로 11로 보내겠습니다.

 

i는 11이 되었고 N은 i로 나누어지니 11을 뽑아내겠습니다.

 

이렇게 N이 1이 되는 순간 모든 소인수를 뽑아낸거고 과정이 끝납니다. 보면 소인수 목록을 잘 구한걸 확인할 수 있습니다. 일단 방법은 이렇고, 그런데 할 얘기가 조금 더 있습니다.

 

첫 번째로 이 방법이 소인수 목록을 잘 구한다는걸 확신할 수 있을지 생각해봅시다. 소인수 목록을 잘 구한다는건 소인수 목록에 적힌 수들을 곱했을 때 N이 되어야 하고, 또 소인수 목록에 있는 수들이 전부 소수여야 한다는걸 의미합니다. 과정을 생각해보면 N에서 i를 나누고 목록에 i를 추가하니 소인수 목록에 적히 수들의 곱이 N인건 크게 무리없이 받아들일 수 있습니다.

 

그런데 목록에 있는 수들이 반드시 소수인가 생각을 해보면 이건 그렇게 막 당연하지는 않습니다. 과정을 보면 i가 2에서 시작해 1씩 증가하면서 N을 나눌 수 있는 수인지 확인을 했고 나눌 수 있는 수일 경우에는 목록에 추가를 했는데 i가 소수인지를 별도로 확인하지는 않았습니다. 그래서 이 사실을 증명 할 필요가 있는데 수학적으로 깔끔하게 증명을 하고 가는게 괜찮을수도 있지만 덜 중요한 내용에서 괜히 피곤하게 만들 것 같아서 대략적으로만 설명을 하겠습니다.

 

일단 결론적으로 얘기해서 목록에 있는 수는 반드시 다 소수입니다. 왜 그렇냐면, 귀류법으로 만약 목록에 소수가 아닌 수가 있다고 가정해봅시다. i가 2부터 시작하니까 1은 절대 목록에 등장할 수 없고, 소수가 아닌 수가 있다면 그 수는 반드시 합성수입니다. 그런데 합성수는 소수인 약수를 반드시 가집니다. 15로 예를 들어보면 15는 3 혹은 5라는 소수인 약수를 가집니다. 그러면 목록에 15가 있다고 가정을 하면 N은 i가 15일 때 15로 나누어 떨어졌다는 뜻입니다. 그런데 이런 상황은 있을 수 없습니다. i가 15이기 이전에 i가 3인 순간이 있었을거고 과정을 생각해보면 그 당시에 더 이상 3으로 나누어지지 않을 때 까지 3을 계속 나누고 소인수 목록에 추가를 했습니다. 그러면 N에 더 이상 3이라는 소인수는 없습니다. 그런 상황에서 N이 15로 나누어 떨어지는 일은 절대 생길 수 없습니다. 예시는 15로 들었지만 다른 임의의 합성수를 가지고 얘기를 해도 비슷한 논리 전개로 만약 목록에 다른 합성수가 있다면 그 합성수에 어떤 소인수 p가 있을텐데 이미 i가 그 합성수에 도달했을 때 N에 p는 남아있지 않기 때문에 모순이라는 식으로 증명을 할 수 있습니다. 그렇기 때문에 이 알고리즘이 소인수분해를 잘 한다는건 납득을 할 수 있습니다.

 

두 번째로 생각할 문제는 시간복잡도입니다. 일단 시간복잡도는 N이 소수이면 중간에 나눠지는 과정 없이 i가 N까지 올라가야 하니 O(N)의 시간복잡도를 가집니다. 그런데 이 알고리즘도 저희가 O(√n)으로 만들 수 있습니다.

 

O(√n)으로 만들기 위한 아이디어는 소수판정하는 알고리즘이랑 동일합니다. 우리가 N을 i로 나누는 이유는 N에서 소인수 i를 빼내기 위해서였습니다. 그러면 i*i가 N보다 커지게 되면 더 이상 나누어보는 작업을 하지 않더라도 N에는 √n 이하의 소인수가 없다, 다르게 말하면 N은 소수다 라는것을 알 수 있어서 불필요한 연산을 줄일 수 있습니다.

 

앞의 상황을 가지고 설명을 하자면 이렇게 i가 5일 때 5의 인자를 빼고 나니 N이 11이 되었습니다. 그러면 i*i가 N보다 커졌고 N이 만약 합성수였다면 소수판정법때 말한 것 처럼 √n 이하의 소인수를 가져야하니 5부터 10까지는 굳이 안해봐도 이들중에 N을 나눌 수 있는 수는 없다는걸 알 수 있습니다. 그래서 여기서 과정을 바로 종료하고 N이 1이 아닐 경우 그 수를 소인수 목록에 추가해주면 됩니다.

 

다음 슬라이드에서는 바로 코드를 보여드릴테니 그 전에 직접 구현을 해보도록 합시다. 구현을 한 다음에 BOJ 11653번: 소인수분해 문제에 제출해 올바르게 짰는지 확인해봅시다.

 

코드는 이렇게 간단하게 만들 수 있습니다. 그냥 출력만 하면 되니까 따로 목록을 어디 저장하지 않고 바로바로 출력을 시켜줬고 15번째 줄에서 n이 1이 아닐 때에만 왜 n을 출력했는지는 여러분이 직접 고민해보시는걸로 하겠습니다.

 

이렇게 소수와 관련해서 할 얘기를 다 했습니다. 소수 챕터에서 다룬걸 다시 정리하면 소수판정과 소인수분해는 모두 O(√n)이다, 그래서 n이 10¹² 정도 되더라도 소수판정이나 소인수분해를 해낼 수 있다. 그리고 1부터 n까지의 수 중에서 소수 목록을 구하는건 에라토스테네스의 체를 쓰면 된다로 요약이 가능합니다.

 

두 번째로 할 얘기는 최대공약수입니다. 최대공약수 전에 먼저 약수부터 보면 약수는 어떤 수를 나누어떨어지게 하는 수입니다. 예를 들어서 18의 약수는 1, 2, 3, 6, 9, 18이 있습니다. 그러면 주어진 수 N의 약수 목록을 어떻게 구할지 생각해보면 이건 좀 많이 쉽다고 생각합니다. 그냥 1부터 N까지 for문 돌면서 다 나눠보면 됩니다.

 

이렇게 O(N)에 약수 목록을 다 구할 수 있습니다.

 

그런데 이것도 O(√n)에 가능합니다. 왜 가능하냐면 약수끼리 곱이 N이 되게끔 짝을 지을 수 있어서 그렇습니다. 18의 약수를 보면 1, 2, 3, 6, 9, 18이 있는데 1과 18을 곱하면 18이고 2와 9,  3과 6을 봐도 마찬가지입니다. 다른 말로 표현을 하면 1, 2, 3만 구하고 나면 6, 9, 18은 자동으로 따라옵니다. 그리고 곱해서 N이 되는 두 수를 생각해보면 둘 중에 작은 수는 √n 이하이기 때문에 이번에도 √n 까지만 처리를 해주면 됩니다.

 

다만 제곱수일 때에는 살짝 예외 처리를 해줘야 하는데, 16을 예로 들어보겠습니다. 16의 약수는 1, 2, 4, 8, 16이고 곱이 16이 되게끔 짝을 지어보면 4는 자기 자신과 곱해서 16이 되어서 따로 놉니다. 이런 경우를 신경을 안쓰면 약수 목록에서 4가 빠지거나 반대로 4가 2번 들어가는 일이 생길 수 있습니다.

 

제 코드를 확인해봅시다. 06번째 줄에서 j가 div.size() - 1부터 시작하는 이유는 약수 목록을 크기 순으로 저장하게끔 하기 위해서입니다. 그리고 07번째 줄의 처리를 했기 때문에 제곱수일 때에도 잘 동작합니다.

 

그런데 06번째 줄에서 (int)는 왜 쓴걸까요? 왜 이걸 써서 int로 형변환을 시켜주는지 생각해봅시다. 0x03강 - 배열 단원에서 얘기를 했었지만 vector의 size() 멤버 함수는 unsigned를 반환합니다. 그래서 만약 div.size()가 0이라고 한다면 (int)가 없다고 할 때 32비트 컴퓨터 기준으로 div.size() - 1은 -1을 값으로 가지는게 아니라 unsigned int가 되어서 2³² - 1, 즉 4294967295를 값으로 가집니다. 다만 이 상황에서는 적어도 1은 div에 들어가니까 div vector의 크기가 0일리는 없고, 설령 억지로 divisor(0)을 호출한다던가 해서 div의 크기를 0으로 만들어도 4294967295를 int j에 넣는 과정에서 형변환이 다시 한 번 일어나서 j에 -1이 정상적으로 담깁니다. 그래서 (int)가 없으면 n = 0일 때 int overflow가 발생하는건 맞는데, 그럼에도 불구하고 소 뒷걸음질 치다가 쥐 잡은 것 마냥 이 코드가 잘 동작합니다.

 

그런데 만약 06번째 줄의 코드가 int j = 0; j <= div.size() - 1; j++ 였다면 이 코드는 j가 0에서 시작해 계속 커져서 런타임에러가 났을거고 size() 멤버 함수와 관련해 주의를 다시 한 번 환기시킬켬 저기에 (int)를 써놨습니다.

 

약수를 했으면 드디어 최대공약수에 대해서 얘기를 할 수 있습니다. 최대공약수는 영어로 Greatest Common Divisor고 줄여서 GCD라고 많이들 씁니다. 아무튼 최대공약수는 두 자연수의 공통된 약수 중에서 가장 큰 약수를 의미하고 예시로 20과 12를 보면 공통된 약수는 1, 2, 4가 있는데 GCD는 그 중에서 가장 큰 4입니다. 그러면 주어진 두 수의 GCD를 어떻게 구할 것인가 생각을 할 때 지금까지 배운걸 응용하면 두 수의 약수 목록을 다 뽑아내고 정렬을 이용하거나 혹은 조금 시간에서 손해를 보더라도 그냥 편하게 이중 for문을 돌던가 해서 겹치는 약수를 찾아낸 뒤 그 중에서 가장 큰 것을 확인하면 그게 GCD입니다. 그런데 이것보다 훨씬 효율적인 유클리드 호제법이라는 방법이 있어서 설명드리겠습니다.

 

유클리드 호제법이라는 이름이 뭔가 좀 스웩도 있고 어려울 것 같이 생겼는데 사실 내용은 진짜 단순합니다. 유클리드 호제법은 두 수 A, B에 대해서 A를 B로 나눈 나머지를 r이라고 하면 GCD(A, B) = GCD(B, r)이다는 내용입니다. 유클리드 호제법으로 GCD(20, 12)를 구해보면 20을 12로 나눈 나머지는 8이니까 GCD(20, 12) = GCD(12, 8)이고 12를 8로 나눈 나머지는 4이니까 GCD(12, 8) = GCD(8, 4)이고 이렇게 가다가 GCD(4, 0)까지 오고 나면 0은 모든 수의 배수이기 때문에 값이 4임을 바로 알 수 있습니다. 이 성질이 왜 참인건가는 과감하게 넘어가겠습니다. 제가 웬만하면 조금 과하다싶은 것 까지도 당연하게 넘어가지 않고 다 설명하는걸 선호하는데 이 유클리드 호제법 만큼은 너무 복잡해서 그냥 그렇구나 하고 넘어가겠습니다.

 

구현은 진짜 간단합니다. 저는 재귀로 구현을 했는데 재귀를 안쓰고 구현해도 while을 이용해서 간단하게 구현을 할 수 있습니다. 시간복잡도는 O(log(max(a,b)))여서 로그로 돌기 때문에 굉장히 빠릅니다. 그리고 C++17 기준으로는 아예 gcd 함수가 numeric 헤더 파일 안에 들어있고 또 C++17 이전에도 gcc에는 비록 비표준이지만 __gcd 함수가 내장되어 있어서 저 짤막한 4줄짜리 코드조차도 안쓰고 그냥 있는걸 가져다쓰곤 합니다. 그런데 혼동을 줄 수도 있을 것 같아서 이 정도로만 설명을 드릴테니 나중에 직접 문제를 풀면서 다른 사람의 코드를 보고 땡기시면 라이브러리에 있는걸 가져다 쓰면 됩니다.

 

그리고 최대공약수를 구할 수 있으면 최소공배수도 따라옵니다. 최소공배수는 Least Common Multiple(LCM)이라고도 부르는데, 아무튼 A ⨉ B = GCD(A, B) ⨉ LCM(A, B)이라는 관계식이 성립하기 때문에 GCD를 이용해서 LCM을 계산할 수 있고, 코드를 보면 a * b를 한 후에 gcd(a, b)를 나누는게 아니라 gcd(a, b)를 먼저 나눴습니다. 그렇게 한 이유는 int overflow를 방지해주기 위해서입니다. 만약 a * b / gcd(a, b)로 계산했다면 a와 b가 10⁹일 때 lcm(a, b)는 10⁹임에도 불구하고 overflow가 발생하게 됩니다.

 

3번째 주제는 연립합동방정식입니다. 연립합동방정식이라고 하니 마치 초동역학위치전환기와 같이 이름에서부터 상당한 압박감이 드는 단어입니다. 리뉴얼 전에는 먼저 합동식을 나타내는 ≡ 기호의 수학적 정의를 설명하고 합동식 연산에서의 덧셈, 뺄셈, 곱셈, 나눗셈 등을 하나하나 다 짚었습니다. 그런데 비록 합동식과 관련이 있는 내용들을 정규교과과정에서 다루긴 하는데 합동식이라는 표현이나 ≡ 이 기호를 써서 식을 나타내는게 등장하지는 않아서 오히려 기호와 엄밀한 수학적 정의를 투입시키는게 더 혼동을 준다는 생각을 했습니다. 그래서 과감하게 기호는 배제한 설명을 드리겠습니다.

 

문제를 보기 전에 나름대로 간단한 수학 퍼즐을 하나 생각해보겠습니다. 이런 유형의 문제를 본 적이 있으신지 모르겠습니다. 저는 사실 어렸을 때 수학경시대회를 나가곤 했었어서 본 적이 있는데 교육과정에서도 이런걸 하는지 조금 가물가물하긴 합니다. 아마 교육과정에서 나오지는 않는 내용이긴 할텐데 한편으로는 경시대회 레벨까지 가지 않아도 문제집에서 심화 레벨 뭐 이런쪽으로 가면 나올법하다 싶기도 합니다. 아무튼 민경 선생님을 위해 학생 수를 구해야 합니다. 어떻게 구해야할지 고민해봅시다.

 

문제를 조금 더 수학적으로 얘기를 해보면 30 이하의 수 중에서 6으로 나눈 나머지가 3이고 5로 나눈 나머지가 2인 수를 찾는 문제란걸 알 수 있습니다. 이런 문제들을 우리는 연립합동방정식이라고 부르고, 어떻게 풀지 고민을 해보면 쉽게 생각나는 방법은 학생이 0명일 때, 1명일 때, ... 29명일 때 이렇게 각각에 대해 6으로 나눈 나머지와 5로 나눈 나머지를 확인해보는 방법입니다. 손수 계산을 다 해보면, 혹은 코드로 짜면 학생 수가 27명이란걸 알아낼 수 있습니다. 그런데 30가지를 다 해보는 대신에 조금 더 효율적으로 할 수 있는 방법은 없을까요?

 

당연히 효율적인 방법이 있으니까 이렇게 말을 드립니다. 일단 이렇게 표를 하나 보여드리면 혹시 조금 느낌이 오는게 없을까요? 0에서 29 사이의 수 중에서 6으로 나눈 나머지가 3이고 5로 나눈 나머지가 2인 수를 찾는건 바로 답하기가 어렵지만 6으로 나눈 나머지가 3인 수들의 목록만을 달라고 하면 그건 3부터 시작해서 6씩 더해나가면 되니 3, 9, 15, 21, 27임을 쉽게 알 수가 있습니다. 그러면 0, 1, 2, ..., 29에 대해서 다 해보는 대신에 3, 9, 15, 21, 27만 가지고 5로 나눈 나머지가 2인지를 확인하면 확인해야 하는 수를 30개에서 5개로 확 줄일 수 있습니다. 코드를 보면 이전과 달리 i가 0부터 29까지 도는 대신에 3에서 시작해서 6씩 더해가는걸 확인할 수 있습니다.

 

그러면 실제로 문제에서 어떻게 활용을 할 수 있는지 BOJ 6064번: 카잉 달력 문제를 보면서 얘기를 해보겠습니다. 문제를 읽고 잘 생각해보면 상황이 앞에서 살펴본 학생 수 구하기 문제와 굉장히 비슷합니다. 첫 번째 예제인 10 12 3 9를 보면 10으로 나눴을 때 3이고 12로 나눴을 때 9인 수를 찾아야하고, 답인 33은 이걸 잘 만족합니다.

본격적인 풀이에 들어가기 전에 2가지 사실을 생각을 해보고 갈 필요가 있습니다. 첫 번째로 문제에서 <M:N>이 달력의 마지막 해라고 했는데, 이 해는 LCM(M, N)번째 해입니다. LCM은 앞에서 얘기했듯 최소공배수입니다. <M:N>이 되려면 그 해가 M으로도 나눠져야 하고 N으로도 나눠져야 하니 LCM(M, N)이란걸 쉽게 떠올릴 수 있습니다.

 

두 번째 성질은 문제의 설명이나 예제를 보고 알아낼 수 있는건데 당장 N = 10이고 M = 12일 때 <7:2>로 표현되는 해가 없어서 답이 -1입니다. 10으로 나눈 나머지가 7인 수는 홀수인데 정작 동시에 12로 나눈 나머지가 2이려면 짝수여야 하니 이런 해는 없습니다. 그래서 일단 이 2가지를 염두에 두고 논의를 이어가겠습니다.

 

쉽게 생각할 수 있는 방법은 1번째 해부터 LCM(M, N)번째 해까지에 대해서 N으로 나눈 나머지가 x이고 M으로 나눈 나머지가 y인지를 확인하는 방법입니다. 이거 아까 학생 수 얘기할 때의 논리 흐름과 비슷하죠? 일단 여기까지 구현을 해보도록 하겠습니다. 일반적인 나머지 연산의 상황과 다르게 x가 0에서 N-1까지가 아니라 1에서 N까지라는 점에 유의해서 코드를 짜야 합니다. 짜고 나서 코드를 확인해보도록 합시다.

 

코드를 보면 x가 N일 때, y가 M일 때에는 그냥 0으로 만들어서 예외 처리를 했습니다. M과 N이 최대 40000이어서 LCM(N,M)은 최대 40000²이고 얘는 int의 최대 범위인 21억 어쩌구보다 작습니다. 저는 그걸 확인한 후에 lcm 함수의 type을 int로 뒀고, 여러분도 비슷한 사고를 거쳐서 type을 정했다고 믿습니다. 또한 15, 16번째 줄에서 그냥 i <= lcm(m, n); 으로 쓰는 대신에 왜 저렇게 l이라는 변수를 하나 뒀냐면, 저 변수가 없으면 매번 for문을 돌 때 마다 lcm(m, n)을 계산하기 때문에 속도가 굉장히 늦어집니다.

 

아무튼 이렇게 짜서 예제를 돌려보면 답은 잘 나옵니다. 그런데 시간복잡도는 어떻게 될까요? O(LCM(N, M))이고 LCM(N, M)은 최대 NM이니 O(NM)입니다. N, M이 최대 40000이어서 이건 시간 초과입니다.

 

그러면 어떻게 개선을 해야하냐고 했을 때, 이미 앞에서 설명을 잘 했기 때문에 또 설명을 하지는 않겠습니다. 1부터 LCM(N, M)까지를 다 보는 대신에 M으로 나눈 나머지가 x인 목록만을 변수 i에 넣고 for문을 돌리면 LCM(N, M) / M개의 수만 확인을 하면 되고, LCM(N, M) / M은 최대 N이기 때문에 시간 내에 잘 돌아갑니다. 코드를 직접 짜보시고 그 다음에 제 코드를 확인합시다.

 

16번째 줄을 보면 i가 1부터 시작해서 l까지 가는 대신, x에서 시작해 m씩 증가하는 방식으로 바뀐걸 볼 수 있습니다. 17번째 줄의 처리는 왜 들어갔냐면, x = M, y = N일 때 LCM(M, N) 대신 0을 반환하는걸 막으려고 들어갔습니다. 이렇게 짜면 시간 제한을 넉넉하게 통과할 수 있습니다.

 

마지막으로 생각해볼 점 3개를 던지고 단원을 마무리하겠습니다. 첫 번째로 1번째 해부터 LCM(M, N)번째 해까지를 봐야하는건 맞는데, 사실 코드에서 l = lcm(m, n)을 계산해서 i <= l을 하는 대신 그냥 i <= m*n 으로 두고 for문을 돌려도 답은 똑같이 잘 나옵니다. 이렇게 하면 굳이 gcd, lcm 함수를 쓸 필요가 없어서 더 편한데 왜 lcm(m, n)을 계산하지 않고 m*n까지로 범위를 잡아도 똑같이 잘 동작하는지 고민을 해봅시다.

 

두 번째로 지금은 2개의 식에 대해서 해결을 해야 했는데 만약 식이 3개 혹은 4개 이렇게 더 늘어나면 어떻게 될까요? 예를 들어 <x:y:z> 꼴이 되어서 K로 나눈 나머지가 z여야 한다는 조건이 추가된 상황을 생각해봅시다. 식이 2개일 때에는 LCM(N,M) / M개의 수, 즉 최대 N개의 수를 확인했는데 식이 3개일 때에는 몇 개의 수를 확인해야 할까요? 언뜻 생각하기에는 NK개의 수를 확인해야하나 싶을 수 있지만 바로 답을 알려드리면 N+K개의 수만 확인하면 됩니다. 이 부분도 한 번 고민해보도록 합시다.

 

마지막에 다룰 얘기는 코딩테스트의 범위를 벗어나는 얘기여서 대회를 노릴 분만 참고하면 됩니다. 원래 대회에서는 연립합동방정식을 중국인의 나머지 정리로 풉니다. 중국인의 나머지 정리는 N, M에 대한 로그 스케일로 돌기 때문에 N, M이 10⁹ 정도로 크더라도 아주 빠르게 계산할 수 있습니다. 다만 중국인의 나머지 정리를 이해하려면 모듈로 역수, 확장된 유클리드 호제법 등을 다 알아야하기 때문에 강의에서는 다루지 않을 예정이고 따로 자료를 찾아보시는걸 추천드립니다.

 

마지막 주제는 이항계수입니다. 일단 설명을 하려면 순열과 조합을 알고 있어야 하는데 이를테면 색깔이 다른 공 n개 중에서 k개를 선택하는데 순서를 고려해 뽑는 경우는 순열이고, 순서를 고려하지 않고 뽑는 경우는 조합이다. 그리고 순서를 고려해서 뽑으면 nPk개,  순서를 고려하지 않고 뽑으면 nCk개이다, 이정도는 알고 있다고 생각을 하고 설명을 하겠습니다. 혹시 설명을 듣다가 헷갈리는게 있으면 고등학교 수학 수준의 순열과 조합 지식을 공부하고 오는걸 추천드립니다.

 

일단 계산식은 여기 적혀있는 그대로고, 순서를 고려하지 않고 5개에서 3개를 뽑는 경우의 수는 5! / (3!2!) = 10, 순서를 고려해 5개에서 3개를 뽑는 경우의 수는 5! / 2! = 60입니다. 이 순열과 조합 부분은 경우의 수를 계산하도록 하는 수학 유형의 문제에서도 쓰일 수 있고, 시뮬레이션 혹은 백트래킹 파트에서 시간복잡도를 가늠할 때에도 쓰일 수 있기 때문에 익혀둘 필요가 있습니다.

 

BOJ 11050번: 이항 계수 1 문제를 보면 nCk를 계산하도록 하고 있습니다.

 

n과 k의 제한이 작기 때문에 그냥 우리가 알고 있는 식을 곧이곧대로 구현하면 아주 쉽게 통과가 가능합니다.

 

여기까지는 괜찮은데 n과 k가 좀 커지면 상황이 달라집니다. 11051번: 이항 계수 2 문제를 보겠습니다. 보면 n과 k의 제한이 최대 1000으로 좀 커진걸 확인할 수 있습니다. 마찬가지로 n!/(n-k)!k! 이 식을 어떻게 활용할 수는 없을까 생각을 해보면, n!과 (n-k)!과 k! 각각은 n과 k가 한 100 정도만 되어도 long long으로도 담을 수 없을 만큼 엄청 커집니다. 물론 n!, (n-k)!, k! 각각을 10007로 나눈 나머지를 알 수 있긴 합니다. 수 하나 곱하고 10007로 나누고 이걸 반복하면 됩니다. 그런데 문제는, n!과 (n-k)!과 k! 각각을 10007로 나눈 나머지를 알고 있다고 한들 저희는 지금 10007로 나눈 나머지 안에서 나눗셈을 하는 방법을 몰릅니다. 예를 들어서 3 / 53을 10007로 나눈 나머지 안에 계산하는 방법을 모릅니다. 대회를 준비하시는 분들은 나중에 모듈로 역수를 배우고 나면 나눗셈 연산을 처리할 수 있게 되어서 n과 k가 한 백만 정도로 커져도 이항 계수를 쉽게 계산할 수 있긴 한데 코딩테스트 레벨에서 다룰 얘기는 아니어서 넘어갑니다.

 

그러면 다시 문제로 돌아와서 이 문제는 과연 어떻게 해결을 해야 하는가 생각해볼 때 아마 고등학교 시절 배우긴 했겠지만 까먹고 있을수도 있는 성질 하나가 여기서 좀 잘 쓰입니다. 뭔 성질이냐면 nCk = (n-1)C(k-1) + (n-1)Ck 이라는 성질입니다. 저게 왜 성립하냐고 했을 때 수식을 가지고 계산을 해봐도 알 수 있긴한데 또 다른 설명 방법이 있습니다.

 

nCk는 순서를 고려하지 않고 n개에서 k개를 뽑는 경우의 수입니다. 여기 그림대로면 5개에서 3개를 뽑는게 5C3입니다. 그러면 여기서 어느 하나를 눈여겨봅시다.(별을 달아놓은 물건) 그러면 5개에서 3개를 뽑는 경우는 2개의 경우로 분류가 되는데 첫 번째로 내가 눈여겨보는게 뽑혔을 때, 그러면 남은 4개 중에서 2개를 뽑아야 하니 4C2입니다. 두 번째로 내가 눈여겨보는게 뽑히지 않을 때, 그러면 남은 4개 중에서 3개를 뽑아야 하니 4C3입니다. 그렇기 때문에 5C3 = 4C2 + 4C3이고 nCk = (n-1)C(k-1) + (n-1)Ck 인것도 마찬가지로 설명할 수 있습니다. 이 설명이 잘 이해가 안간다라고하면 그럴 수 있습니다. 이게 엄청 중요한 내용은 아니니까 이해가 잘 안가면 식만 외우고 유도 과정은 몰라도 크게 상관은 없습니다.

 

아무튼 그러면 저 식을 가지고 바로 dp를 할 수 있습니다. d[i][j] = iCj 라고 두면 d[i][j] = d[i-1][j-1] + d[i-1][j]라는 식을 바로 얻을 수 있습니다. int overflow에 주의해서 코드를 작성해봅시다.

 

저는 그냥 1000 by 1000을 다 채우고 답을 출력하게끔 했고, 테이블을 채우는 순서와 int overflow만 조심하면 크게 문제는 없어보입니다.

 

이렇게 나름 좀 길었던 수학 단원이 끝이 났습니다. 사실 조금 아쉬운건 수학 단원의 문제들이 진짜 많고 또 되게 중구난방입니다. 이쪽 분류의 문제들이 옛날 수학 경시대회에서 활용되던 몇몇 아이디어들을 차용해서 내는 경우가 종종 있어서 그런 문제들은 쓰이는 테크닉을 모르면 아예 풀 수가 없는데 테크닉 자체는 너무 지엽적이어서 이거를 꼭 해야할까 하는 마인드로 몇 개 빠진게 있습니다. 대표적으로 팩토리얼에서 0의 개수로 장난치는 문제가 있습니다. 또 그런 문제들이 기업이 코딩테스트를 통해 알고 싶어하는 능력을 평가하기에 별로 적절한 문제라고 생각하지도 않습니다.

 

그래도 문제은행식으로 출제되는 코딩테스트에서는 운나쁘게 그런 지엽적인 테크닉을 알아야만 풀 수 있는 문제가 나올수도 있고 이거는 아무도 장담할 수 없는 상황입니다. 그래서 비록 강의 내에서 다루지는 않았지만 연습 문제에는 조금 지엽적인 것 같은 문제도 많이 넣어놨습니다. 그러니까 꼼꼼하게 대비를 하고 싶다고 하면 연습 문제도 꼭 풀어보셔야 합니다.