이 기사에서는 주어진 행렬에서 주어진 합을 갖는 쌍을 찾는 프로그램에 대해 논의할 것입니다. 예를 들어 -
Input : matrix[n][m] = {
{ 4, 6, 4, 65 },
{ 56, 1, 12, 32 },
{ 4, 5, 6, 44 },
{ 13, 9, 11, 25 }
}, SUM = 20
Output : Pair exists.
Explanation : Sum = 20 is equal to the sum of numbers 9 and 11 which exists in the matrix.
Input : matrix[n][m] = {
{ 5, 7, 3, 45 },
{ 63, 5, 3, 7 },
{ 11, 6, 9, 5 },
{ 8, 6, 14, 15 }
}, SUM = 13
Output : Pair does not exist.
Explanation : No pair exists in the matrix whose sum is equal to 7. 해결책을 찾기 위한 접근 방식
이제 위의 문제를 해결하기 위한 두 가지 접근 방식을 설명하겠습니다.
무차별 대입 접근
주어진 행렬의 각 쌍을 고려하고 쌍의 합이 주어진 SUM과 같은지 확인하고 그렇다면 "Pair exist"를 인쇄합니다. 그렇지 않으면 "쌍이 존재하지 않습니다."를 인쇄하십시오. 이 접근 방식을 적용하는 것은 매우 간단하지만 시간 복잡도가 O((N*M)2)까지 증가합니다.
효율적인 접근
이 프로그램은 해시를 사용하여 모든 행렬 요소를 저장한 다음 행렬을 탐색하고 [ SUM &(인덱스 요소) ]의 차이가 동일한지 확인함으로써 효율적일 수 있습니다. 예인 경우 "Exist"를 인쇄하고 프로그램을 종료합니다. NO인 경우 인쇄를 순회한 후 "존재하지 않습니다."
예시
#include <bits/stdc++.h>
using namespace std;
#define n 4
#define m 4
int main() {
int matrix[n][m] = {
{ 5,7, 3,45 },
{ 63, 5, 3, 7 },
{ 11, 6, 9, 5 },
{ 8, 6, 14, 15 }
};
int sum = 7;
unordered_set<int> hash;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (hash.find(sum - matrix[i][j]) != hash.end()) {
cout << "Pair exists." << endl;
return 0;
} else {
hash.insert(matrix[i][j]);
}
}
}
cout << "Pair does not exist." << endl;
return 0;
} 출력
Pair does not exist.
위 코드 설명
- 2차원 배열을 선언하고 그 안에 요소를 저장합니다.
- 배열을 탐색하여 if (sum - matrix[i][j]) !=hash.end()를 찾습니다.
- 조건이 충족되면 "Pair exist"를 인쇄하고 기본 함수에서 반환합니다.
- 그렇지 않으면 배열을 계속 탐색하고 마지막으로 " 쌍이 존재하지 않습니다."를 출력합니다.
결론
이 기사에서 우리는 행렬이나 2차원 배열에서 주어진 합을 가진 쌍을 찾는 것에 대해 논의했습니다. 우리는 이 문제를 해결하기 위한 Brute-force 접근법과 Efficient 접근법에 대해 논의했습니다. 우리는 이 문제를 해결하기 위해 C++ 프로그램에 대해 논의했습니다. 그러나 이 프로그램은 C, Java, Python 등과 같은 다른 언어로 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.