문제 개요
정수 값으로 구성된 행렬이 주어졌을 때, 특정 정수 k가 행렬 안에서 몇 번 나타나는지 그 빈도(등장 횟수)를 계산하는 것이 이번 문제의 목표입니다. 행렬의 크기는 사용자가 지정할 수 있으며, 아래 프로그램에서는 4×4 크기를 기준으로 설명합니다. 행렬은 matrix(i, j) = i + j라는 규칙으로 생성되며, 인덱스는 0부터 시작하므로 첫 번째 원소는 matrix[0][0] = 0이 됩니다.
입력 및 출력 예시
입력 − int size = 4, k = 4
출력 − 4×4 행렬에서 4의 등장 횟수는 3
설명 −
matrix[i][j] = i+j (i = j = 4)
Matrix[4][4] = {
0, 1, 2, 3
1, 2, 3, 4
2, 3, 4, 5
3, 4, 5, 6
}
숫자 k, 즉 4는 이 행렬에서 3번 나타납니다.
입력 − int size = 3, k = 1
출력 − 3×3 행렬에서 1의 등장 횟수는 2
설명 −
matrix[i][j] = i+j (i = j = 3)
Matrix[3][3] = {
0, 1, 2
1, 2, 3
2, 3, 4
}
숫자 k, 즉 1은 주어진 행렬에서 2번 나타납니다.
접근 방법
n×n 행렬의 크기와 행렬에서 찾고자 하는 정수 값 'k'를 입력받습니다.
i를 0부터 행(row) 크기까지 반복하는 루프를 시작합니다.
루프 내부에서 j를 0부터 열(column) 크기까지 반복하는 또 다른 루프를 시작합니다.
matrix[i][j] = i + j 값을 설정합니다.
matrix[i][j] == k인지 검사합니다.
조건이 참이면 count를 1 증가시키고, 거짓이면 해당 데이터를 무시합니다.
count 값을 반환합니다.
결과를 출력합니다.
예제 코드
#include <cmath>
#include <iostream>
using namespace std;
int count(int size, int k){
int count = 0;
int matrix[size][size];
for(int i = 0; i<size; i++){
for(int j = 0; j<size; j++){
matrix[i][j] = i+j;
if(matrix[i][j] == k){
count++;
}
}
}
return count;
}
int main(){
int size = 4;
int k = 4;
int total = count(size, k);
if(total>0){
cout<<"Count of frequency of "<<k<<" in a matrix of size "<<size<<"X"<<size<<" where matrix(i, j) = i+j is: "<<total;
} else {
cout<<"Frequency of element is 0 that means it is not present in a matrix";
}
}
출력 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다 −
Count of frequency of 4 in a matrix of size 4X4 where matrix(i, j) = i+j is: 3
심화 학습: O(n) 최적화 방법
이 문제는 사실 중첩 루프 없이도 해결할 수 있습니다. matrix[i][j] = i + j = k를 만족하려면 각 i에 대해 j = k − i가 유일하게 결정되므로, 유효한 쌍 (i, j)의 개수만 세면 됩니다.
i와 j는 모두 0 이상 size−1 이하여야 하므로, i의 유효 범위는 max(0, k − (size−1)) ≤ i ≤ min(k, size−1)입니다. 이 범위에 속하는 i의 개수가 곧 정답이 됩니다.
예를 들어 size = 4, k = 4인 경우, i는 1부터 3까지이므로 유효한 쌍은 (1,3), (2,2), (3,1)의 3개가 되어 답은 3입니다. 이 방식을 활용하면 시간 복잡도를 O(n²)에서 O(n)으로 크게 줄일 수 있어, 행렬의 크기가 커질 때 특히 유용합니다.