n × n 크기의 행렬과 정수 변수 x가 주어집니다. 행렬의 요소들은 이미 정렬된 상태로 배치되어 있으며, 우리의 목표는 x보다 작거나 같은 요소의 개수를 계산하는 것입니다.
예제 1
입력 −
matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {6, 7, 8}}, X = 4
출력 −
count is 4
설명 − 행렬의 각 요소를 값 x와 비교하면, 4보다 작거나 같은 요소는 1, 2, 3, 4로 총 4개입니다.
예제 2
입력 −
matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {6, 7, 8}}, X = 0
출력 −
count is 0
설명 − 행렬의 모든 요소를 값 x와 비교해도 0보다 작거나 같은 요소는 하나도 없으므로 개수는 0입니다.
프로그램에 사용된 접근 방식
- 행렬의 크기를 입력받아 n × n 크기의 행렬을 생성합니다.
- i를 0부터 행 크기까지 반복하는 외부 루프를 시작합니다.
- 외부 루프 안에서 j를 0부터 열 크기까지 반복하는 내부 루프를 시작합니다.
- matrix[i][j] ≤ x 인지 확인하여, 참이면 count를 1 증가시키고 그렇지 않으면 해당 조건은 건너뜁니다.
- 모든 탐색이 끝나면 총 개수를 반환합니다.
- 결과를 화면에 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
#define size 3
// 전체 요소 개수를 세는 함수
int count(int matrix[size][size], int x){
int count=0;
// 행렬을 행 단위로 순회
for(int i = 0 ;i<size; i++){
for (int j = 0; j<size ; j++){
// 행렬의 값이 x보다 작거나 같은지 확인
if(matrix[i][j]<= x){
count++;
}
}
}
return count;
}
int main(){
int matrix[size][size] ={
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int x = 5;
cout<<"정렬된 행렬에서 x보다 작거나 같은 요소의 개수는: "<<count(matrix,x);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
정렬된 행렬에서 x보다 작거나 같은 요소의 개수는: 5
시간 복잡도와 최적화 팁
위 방법은 행렬의 모든 요소를 한 번씩 확인하므로 시간 복잡도는 O(n²)입니다. 하지만 행렬이 정렬되어 있다는 특성을 활용하면 더 효율적으로 개선할 수 있습니다.
- 행별 이진 탐색: 각 행이 오름차순으로 정렬되어 있으므로, 각 행마다 upper_bound(이진 탐색)를 적용하면 시간 복잡도를 O(n log n)으로 줄일 수 있습니다.
- 계단식 탐색(Staircase Search): 오른쪽 상단 모서리에서 시작하여 현재 값이 x보다 크면 왼쪽으로, 작거나 같으면 아래로 이동하는 방식으로 O(n) 시간에 해결할 수 있습니다.