이 글에서는 처음 세 항이 등차수열(A.P.)을 이루고 마지막 세 항이 등비수열(G.P.)을 이루는 사중항(quadruple)의 개수를 구하는 다양한 접근 방법을 소개합니다. 먼저 등차수열과 등비수열의 기본 개념부터 짚고 넘어가겠습니다.
기본 개념: 등차수열과 등비수열
등차수열(Arithmetic Progression, A.P.)
인접한 두 항의 차이, 즉 공차(d)가 항상 일정한 수열입니다.
예: 1, 3, 5, 7, 9 → 공차 d = 2
등비수열(Geometric Progression, G.P.)
각 항에 고정된 수, 즉 공비(r)를 곱하여 다음 항을 만드는 수열입니다.
예: 3, 6, 12, 24, ... → 공비 r = 2
문제 정의
N개의 정수로 구성된 배열 arr[]에서 다음 조건을 모두 만족하는 인덱스 사중항 (a, b, c, d)의 개수를 구하는 것이 목표입니다.
- arr[a], arr[b], arr[c]가 등차수열을 이룬다
- arr[b], arr[c], arr[d]가 등비수열을 이룬다
- 사중항의 네 인덱스는 서로 달라야 한다
다음 예시를 통해 살펴보겠습니다.
입력 : arr[ ] = { 9, 6, 4, 2, 1, 2 }
출력 : 2
설명 : 사중항은 인덱스 { 3, 2, 1, 0 }과 { 5, 2, 1, 0 }에 위치하며, 두 경우 모두 { 2, 4, 6, 9 }로 등차수열(2, 4, 6)과 등비수열(4, 6, 9)을 동시에 만족합니다.
입력 : arr[ ] = { 2, 6, 1, 4, 2 }
출력 : 2
설명 : 사중항은 인덱스 { 1, 3, 0, 2 }와 { 1, 3, 4, 2 }에 위치하며, 두 경우 모두 { 6, 4, 2, 1 }로 등차수열(6, 4, 2)과 등비수열(4, 2, 1)을 동시에 만족합니다.
문제 해결 접근 방법
이 문제를 해결하기 위한 두 가지 방법을 소개합니다.
1. 브루트 포스(Brute Force) 방식
가장 직관적인 방법으로, 네 개의 중첩 반복문을 사용해 가능한 모든 사중항을 검사합니다. 먼저 처음 세 요소가 등차수열을 이루는지 확인하고, 만약 그렇다면 나머지 세 요소가 등비수열을 이루는지 추가로 확인합니다. 두 조건을 모두 만족하면 카운트 변수를 1 증가시킵니다. 다만 이 방식은 시간 복잡도가 O(n⁴)이므로 실행 시간이 매우 오래 걸린다는 치명적인 단점이 있습니다.
2. 효율적인 방식(Efficient Approach)
이 방식에서는 먼저 배열 내 모든 요소의 등장 횟수를 해시맵에 저장합니다. 그런 다음 두 번째 요소(b)와 세 번째 요소(c)가 될 값을 기준으로 두 개의 중첩 반복문을 실행합니다. 이때 첫 번째 요소는 공차를 이용해 arr[b] − (arr[c] − arr[b])로 구할 수 있고, 네 번째 요소는 공비 관계를 이용해 arr[c] × arr[c] / arr[b]로 구할 수 있습니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
int main (){
unordered_map < int, int >map;
int arr[] = { 2, 6, 1, 4, 2 };
int size = sizeof (arr) / sizeof (arr[0]);
// 모든 요소를 처리하며 등장 횟수 증가
for (int a = 0; a < size; a++)
map[arr[a]]++;
int count = 0;
// 두 번째 & 세 번째 요소를 위한 중첩 반복문 실행
for (int b = 0; b < size; b++){
for (int c = 0; c < size; c++){
if (b == c)
continue;
// 현재 선택된 요소의 카운트 감소
map[arr[b]]--;
map[arr[c]]--;
// 공차를 이용해 첫 번째 요소 찾기
int first = arr[b] - (arr[c] - arr[b]);
// GP 관계를 이용해 네 번째 요소 찾기
int fourth = (arr[c] * arr[c]) / arr[b];
if ((arr[c] * arr[c]) % arr[b] == 0){
// 두 요소가 다르면 카운트 증가
if (arr[b] != arr[c])
count += map[first] * map[fourth];
else
count += map[first] * (map[fourth] - 1);
}
map[arr[b]]++;
map[arr[c]]++;
}
}
cout <<"Number of quadruples: " << count;
return 0;
}
실행 결과
Number of quadruples: 2
코드 설명
이 코드는 조합론적 사고를 활용합니다. 두 번째 요소(b)와 세 번째 요소(c)를 고정한 상태에서 중첩 반복문을 돌며, 공차를 이용해 첫 번째 요소 arr[b] − (arr[c] − arr[b])를, 공비 관계를 이용해 네 번째 요소 arr[c] × arr[c] / arr[b]를 계산합니다. 따라서 특정 (b, c) 조합에 대한 사중항의 개수는 '첫 번째 숫자 후보의 개수 × 네 번째 숫자 후보의 개수'가 됩니다. 여기서 arr[c]²가 arr[b]로 나누어떨어지는지 확인하는 이유는 네 번째 요소가 정수여야 하기 때문입니다. 또한 b와 c의 값이 같을 때는 자기 자신을 중복해서 세지 않도록 카운트에서 1을 빼주어 처리합니다. 이 코드의 시간 복잡도는 O(n²)로, 브루트 포스 방식보다 훨씬 효율적입니다.
마무리
이 글에서는 처음 세 항이 등차수열이고 마지막 세 항이 등비수열을 이루는 사중항의 개수를 구하는 문제를 다루었으며, 브루트 포스 방식(O(n⁴))과 해시맵을 활용한 효율적인 방식(O(n²)) 두 가지로 해결하는 방법을 살펴보았습니다.
여기서는 C++로 문제를 해결했지만, 동일한 로직은 Java, Python, C 등 다른 프로그래밍 언어로도 충분히 구현할 수 있습니다.