문제 소개
행렬을 구성하는 전체 요소의 개수가 주어졌을 때, 해당 요소 개수로 만들 수 있는 서로 다른 차수(order)의 행렬이 총 몇 개인지 계산하는 것이 이번 글의 목표입니다. 행렬의 차수는 m×n 형태로 표현되며, 여기서 m은 행(row)의 개수, n은 열(column)의 개수를 의미합니다.
핵심 아이디어: 약수의 개수 구하기
이 문제의 핵심은 사실 약수(divisor)의 개수를 구하는 것과 같습니다. 전체 요소 수가 N일 때, m×n = N을 만족하는 순서쌍 (m, n)의 개수가 곧 만들 수 있는 행렬의 개수입니다. 즉, N의 모든 약수가 각각 하나의 유효한 행 개수가 되며, 열의 개수는 자동으로 N/m으로 결정됩니다.
예시 1
입력: int numbers = 6
출력: 4
설명: 6개의 요소로 만들 수 있는 행렬의 차수는 (1, 6), (2, 3), (3, 2), (6, 1)로 총 4가지입니다.
예시 2
입력: int numbers = 40
출력: 8
설명: 40개의 요소로 만들 수 있는 행렬의 차수는 (1, 40), (2, 20), (4, 10), (5, 8), (8, 5), (10, 4), (20, 2), (40, 1)로 총 8가지입니다.
해결 접근 방법
- 행렬을 구성하는 데 사용할 전체 요소 개수를 입력받습니다.
- 계산을 위해 해당 값을 함수로 전달합니다.
- 서로 다른 차수의 행렬 개수를 저장할 임시 변수 count를 선언합니다.
- i를 1부터 입력값 number까지 1씩 증가시키며 반복문을 실행합니다.
- 반복문 안에서 number % i == 0, 즉 i가 number의 약수라면 count를 1씩 증가시킵니다.
- 반복이 끝나면 count를 반환합니다.
- 최종 결과를 출력합니다.
C++ 코드 구현
#include <iostream>
using namespace std;
// 주어진 요소 개수로 만들 수 있는 서로 다른 차수의 행렬 개수를 세는 함수
int total_matrices(int number){
int count = 0;
for (int i = 1; i <= number; i++){
if (number % i == 0){
count++;
}
}
return count;
}
int main(){
int number = 6;
cout<<"주어진 요소 개수로 만들 수 있는 서로 다른 차수의 행렬 개수: "<<total_matrices(number);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
주어진 요소 개수로 만들 수 있는 서로 다른 차수의 행렬 개수: 4
성능 최적화 팁
위 방식은 1부터 N까지 모든 수를 검사하므로 시간 복잡도가 O(N)입니다. N이 매우 큰 경우에는 제곱근까지만 검사하고 약수 쌍의 대칭성을 활용하면 시간 복잡도를 O(√N)까지 줄일 수 있습니다. i가 N의 약수라면 N/i 역시 약수이므로, i ≤ √N 범위에서만 반복하면서 i != N/i일 때는 count를 2씩 증가시키고, i == N/i일 때는 1만 증가시키면 됩니다.
마무리
"주어진 요소 개수로 만들 수 있는 행렬의 차수 개수" 문제는 결국 약수의 개수를 구하는 문제와 동일합니다. 나눗셈 연산과 반복문만으로 간단히 해결할 수 있으며, 약수 쌍의 대칭성을 활용하면 더욱 효율적인 알고리즘을 작성할 수 있습니다.