라그랑주 네 제곱수 정리란?
이 튜토리얼에서는 라그랑주 네 제곱수 정리(Lagrange's Four-Square Theorem)에 대해 알아보겠습니다.
라그랑주 네 제곱수 정리는 수학의 대표적인 정리 중 하나로, 모든 자연수는 4개의 정수(음이 아닌 정수) 제곱의 합으로 표현할 수 있다는 내용입니다. 예를 들어, 7은 1² + 1² + 1² + 2² = 7과 같이 나타낼 수 있습니다.
아래 코드는 주어진 자연수 n에 대해 이 조건을 만족하는 4개의 숫자를 찾아 출력하는 프로그램입니다.
동작 원리
코드는 단순한 브루트 포스(Brute Force) 방식을 사용합니다. 4개의 중첩 반복문을 통해 가능한 모든 조합을 탐색하되, 각 숫자가 이전 숫자보다 크거나 같도록(i ≤ j ≤ k ≤ l) 범위를 설정하여 중복된 조합을 제거합니다. 또한 각 숫자의 제곱이 n을 초과하지 않도록 조건을 걸어 불필요한 탐색을 줄였습니다.
C++ 예제 코드
#include <bits/stdc++.h>
using namespace std;
void printSquareCombinations(int n) {
for (int i = 0; i * i <= n; i++) {
for (int j = i; j * j <= n; j++) {
for (int k = j; k * k <= n; k++) {
for (int l = k; l * l <= n; l++) {
if (i * i + j * j + k * k + l * l == n) {
cout << n << " = " << i << "*" << i
<< " + " << j << "*" << j
<< " + " << k << "*" << k
<< " + " << l << "*" << l << endl;
}
}
}
}
}
}
int main() {
int n = 25;
printSquareCombinations(n);
return 0;
}
실행 결과
n = 25를 입력하여 위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
25 = 0*0 + 0*0 + 0*0 + 5*5
25 = 0*0 + 0*0 + 3*3 + 4*4
25 = 1*1 + 2*2 + 2*2 + 4*4
결과 분석
출력 결과에서 확인할 수 있듯이, 25는 세 가지 방식으로 표현됩니다.
- 25 = 0 + 0 + 0 + 5² (단순히 하나의 제곱수인 경우)
- 25 = 0 + 0 + 3² + 4² (두 개의 제곱수의 합)
- 25 = 1² + 2² + 2² + 4² (네 개의 제곱수의 합)
정리에 따라 0도 허용하기 때문에, 어떤 자연수든 반드시 최소 한 가지 이상의 표현을 찾을 수 있습니다.
시간 복잡도
이 알고리즘은 4중 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. n이 작은 경우에는 충분하지만, 매우 큰 수를 다룰 때는 비효율적일 수 있습니다. 참고로 라그랑주 정리에 따르면 해는 항상 존재하는 것이 보장되므로, 해가 존재하는지 여부만 확인한다면 더 효율적인 동적 계획법(DP) 접근도 가능합니다.
마무리
이번 튜토리얼에서는 라그랑주 네 제곱수 정리의 개념과 이를 C++로 구현하는 방법을 살펴보았습니다. 궁금한 점이 있다면 댓글로 남겨주세요!