하한(lower bound)과 상한(upper bound)이 주어졌을 때, 다음 조건을 만족하는 비전이적(nontransitive) 삼중항 (x, y, z)을 찾는 문제를 생각해 보겠습니다.
- (x, y)는 서로소(coprime), 즉 최대공약수(GCD)가 1
- (y, z)도 서로소
- 그러나 (x, z)는 서로소가 아님
문제 이해하기
예를 들어 하한이 2, 상한이 10이라면 후보 집합은 {2, 3, 4, 5, 6, 7, 8, 9, 10}입니다. 이 범위에서 가능한 삼중항 중 하나는 (4, 7, 8)입니다. (4, 7)과 (7, 8)은 각각 서로소 관계이지만, (4, 8)은 최대공약수가 4이므로 서로소가 아니어서 비전이적 조건을 충족합니다.
접근 방식: 완전 탐색(Brute Force)
가장 직관적인 방법은 주어진 범위 내에서 만들 수 있는 모든 삼중항을 하나씩 생성한 뒤, 위의 세 가지 조건을 순서대로 검사하는 것입니다. 조건을 만족하는 첫 번째 삼중항을 발견하면 결과를 저장하고 탐색을 종료합니다.
C++ 구현 코드
#include <iostream>
#include <algorithm>
using namespace std;
bool isCoprime(int a, int b){
return (__gcd(a, b) == 1);
}
void tripletInRange(int left, int right) {
bool flag = false;
int A, B, C;
// left와 right 사이의 모든 가능한 삼중항을 생성하고 조건 검사
for (int a = left; a <= right; a++) {
for (int b = a + 1; b <= right; b++) {
for (int c = b + 1; c <= right; c++) {
if (isCoprime(a, b) && isCoprime(b, c) && !isCoprime(a, c)) {
flag = true;
A = a;
B = b;
C = c;
break;
}
}
}
}
if (flag == true) {
cout << "(" << A << ", " << B << ", " << C << ")" << " 은(는) "
<< left << "부터 " << right << " 사이에서 가능한 삼중항 중 하나입니다" << endl;
} else {
cout << left << "부터 " << right << " 사이에는 해당 조건을 만족하는 삼중항이 없습니다" << endl;
}
}
int main() {
int left = 2, right = 10;
tripletInRange(left, right);
}실행 결과
(8, 9, 10) 은(는) 2부터 10 사이에서 가능한 삼중항 중 하나입니다
코드의 핵심은 isCoprime() 함수입니다. 이 함수는 <algorithm> 헤더에서 제공하는 __gcd() 내장 함수를 사용해 두 수의 최대공약수가 1인지 판별합니다. 세 겹의 반복문은 a < b < c 순서로 조합을 생성하여 같은 삼중항이 중복해서 검사되지 않도록 합니다.
복잡도 분석
- 시간 복잡도: 세 겹의 반복문 때문에 O(n³)입니다. 여기서 n은 범위 내 원소 개수(right − left + 1)이며, 각 검사마다 GCD 계산에 추가로 O(log n)이 소요됩니다.
- 공간 복잡도: 결과 저장을 위한 변수 몇 개만 사용하므로 O(1)입니다.
범위가 넓어지면 완전 탐색은 빠르게 느려지지만, 로직이 단순하고 정확성을 보장하기 때문에 작은 범위나 학습 목적의 구현에는 매우 효과적인 접근 방식입니다.