이 글에서는 주어진 행렬(2차원 배열) 안에서 합이 특정 값(SUM)과 일치하는 두 원소의 쌍(pair)을 찾는 프로그램을 다뤄보겠습니다. 먼저 예시를 통해 문제를 이해해 보겠습니다.
입력 : matrix[n][m] = {
{ 4, 6, 4, 65 },
{ 56, 1, 12, 32 },
{ 4, 5, 6, 44 },
{ 13, 9, 11, 25 }
}, SUM = 20
출력 : Pair exists. (쌍이 존재함)
설명 : 9와 11의 합이 20이며, 이 두 숫자는 행렬 안에 실제로 존재합니다.
입력 : matrix[n][m] = {
{ 5, 7, 3, 45 },
{ 63, 5, 3, 7 },
{ 11, 6, 9, 5 },
{ 8, 6, 14, 15 }
}, SUM = 13
출력 : Pair does not exist. (쌍이 존재하지 않음)
설명 : 합이 13이 되는 두 원소의 쌍이 행렬 안에 존재하지 않습니다.해결 접근 방식
위 문제를 해결하기 위한 두 가지 서로 다른 접근 방식을 살펴보겠습니다.
브루트 포스(Brute-Force) 접근
행렬에 있는 모든 가능한 원소 쌍을 하나씩 검사하면서, 각 쌍의 합이 주어진 SUM과 일치하는지 확인하는 방법입니다. 일치하는 쌍을 발견하면 "쌍이 존재함"을 출력하고, 끝까지 찾지 못하면 "쌍이 존재하지 않음"을 출력합니다. 구현이 매우 간단하다는 장점이 있지만, 시간 복잡도가 O((N*M)²)까지 증가할 수 있다는 치명적인 단점이 있습니다.
효율적인 접근 (해시 활용)
해시(unordered_set)를 활용하면 프로그램의 성능을 크게 개선할 수 있습니다. 행렬을 순회하면서 각 원소를 해시에 저장해 나가고, 동시에 현재 원소에 대해 [SUM − 현재 원소] 값이 이미 해시에 존재하는지 검사합니다. 존재한다면 해당 두 원소의 합이 SUM과 같다는 의미이므로 "쌍이 존재함"을 출력하고 프로그램을 종료합니다. 끝까지 찾지 못했다면 "쌍이 존재하지 않음"을 출력하면 됩니다. 이 방식은 평균적으로 O(N*M)의 시간 복잡도를 가집니다.
C++ 구현 예제
#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차원 배열을 선언하고 원소들을 저장합니다.
- 배열을 순회하면서 (sum - matrix[i][j]) 값이 해시에 이미 존재하는지 확인합니다.
- 조건을 만족하면 "Pair exists."를 출력하고 main 함수를 즉시 종료합니다.
- 조건을 만족하지 않으면 현재 원소를 해시에 삽입하고 계속 탐색하며, 마지막까지 찾지 못하면 "Pair does not exist."를 출력합니다.
마무리
이 글에서는 행렬(2차원 배열)에서 주어진 합과 일치하는 두 원소의 쌍을 찾는 방법을 알아보았습니다. 단순하지만 느린 브루트 포스 방식과, 해시를 활용해 시간 복잡도를 O(N*M)으로 줄인 효율적인 방식을 비교하며 살펴보았고, C++ 코드로 직접 구현까지 진행했습니다. 물론 동일한 로직은 C, Java, Python 등 다른 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되었기를 바랍니다.