이 글에서는 주어진 행렬(matrix) 또는 2차원 배열에서 최대 합을 가지는 쌍(pair)을 찾는 방법에 대해 알아보겠습니다.
입력 : matrix[m][n] = {
{ 3, 5, 2 },
{ 2, 6, 47 },
{ 1, 64, 66 } }
출력 : 130
설명 : 요소 쌍 64와 66의 합인 130이 최대 합입니다.
입력 : matrix[m][n] = {
{ 55, 22, 46 },
{ 6, 2, 1 },
{ 3, 24, 52 } }
출력 : 107
설명 : 요소 쌍 55와 52의 합인 107이 최대 합입니다.문제 해결 접근 방법
주어진 문제를 효과적으로 해결할 수 있는 몇 가지 접근 방식을 간단히 살펴보겠습니다.
브루트 포스(Brute-force) 접근법
가장 직관적인 방법은 브루트 포스 방식입니다. 먼저 MAX 변수를 첫 두 요소의 합으로 초기화한 뒤, 배열을 순회하면서 모든 쌍의 합을 검사하고 기존 MAX보다 큰 값이 나오면 새로운 합으로 갱신하는 방식입니다. 그러나 이 방법은 시간 복잡도가 O((m×n)²)로 매우 비효율적이며, 행렬의 크기가 커질수록 실행 시간이 급격히 늘어난다는 단점이 있습니다.
효율적인 접근법
훨씬 효율적인 방법은 MAX1과 MAX2라는 두 변수를 활용하는 것입니다. 두 변수를 정수형의 최솟값으로 초기화한 후 2차원 배열을 한 번만 순회하면서 현재 요소가 MAX1보다 큰지 확인합니다. 만약 크다면 MAX2에는 기존 MAX1 값을 넣고, MAX1에는 현재 요소를 대입합니다. 이 과정을 반복하면 자연스럽게 행렬에서 가장 큰 두 개의 수를 찾을 수 있고, 이 두 수의 합이 곧 최대 합이 됩니다. 이 방식의 시간 복잡도는 O(m×n)으로 매우 효율적입니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int main() {
int m = 3, n = 3;
// 초기값으로 행렬 생성
int matrix[m][n] = {
{ 55, 22, 46 },
{ 6, 2, 1 },
{ 3, 24, 52 }
};
// 두 개의 최댓값을 저장할 MAX1과 MAX2 초기화
int MAX1 = INT_MIN;
int MAX2 = INT_MIN;
int result;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 현재 요소가 MAX1보다 큰지 확인
if (matrix[i][j] > MAX1) {
MAX2 = MAX1;
MAX1 = matrix[i][j];
}
// 현재 요소가 MAX1과 MAX2 사이에 있는지 확인
else if (matrix[i][j] > MAX2 && matrix[i][j] <= MAX1) {
MAX2 = matrix[i][j];
}
}
}
// 두 최댓값을 더해 최대 합 계산
result = MAX1 + MAX2;
cout << "maximum sum in Matrix : " << result;
return 0;
}실행 결과
maximum sum in Matrix : 107
코드 설명
- 요소들을 2차원 배열에 저장하고, MAX1과 MAX2를 정수형의 최솟값(
INT_MIN)으로 초기화합니다. - 행렬 전체를 순회하면서 다음 조건을 검사합니다.
- 현재 요소가 MAX1보다 크면, MAX2에 기존 MAX1 값을 대입하고 MAX1을 현재 요소로 교체합니다.
- 현재 요소가 MAX1보다 작고 MAX2보다 크면, MAX2를 현재 요소로 교체합니다.
- 순회가 끝나면 MAX1과 MAX2를 더해 결과를 계산하고 출력합니다.
마무리
이 글에서는 주어진 행렬에서 최대 합을 가지는 쌍을 찾는 방법을 살펴보았습니다. 비효율적인 브루트 포스 방식부터 O(m×n) 시간 복잡도를 가지는 효율적인 탐색 방식까지 다루었으며, 실제로 동작하는 C++ 코드도 함께 확인했습니다. 이 로직은 Java, C, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.