이 문제에서는 하나의 행렬(matrix)이 주어지며, 우리의 과제는 이 행렬의 상삼각형(upper triangle) 요소들의 합과 하삼각형(lower triangle) 요소들의 합을 각각 계산하여 출력하는 프로그램을 작성하는 것입니다.
하삼각형(Lower Triangle)이란?
하삼각형은 주대각선(main diagonal)을 기준으로 아래쪽에 위치한 모든 요소를 의미합니다. 주대각선 위쪽의 요소들은 모두 0으로 표현됩니다.
M00 0 0 … 0 M10 M11 0 … 0 M20 M21 M22 … 0 … Mrow0 Mrow1 Mrow2 … Mrow col
상삼각형(Upper Triangle)이란?
반대로 상삼각형은 주대각선을 포함하여 그 위쪽에 위치한 모든 요소를 의미하며, 주대각선 아래쪽의 요소들은 모두 0으로 표현됩니다.
M00 M01 M02 … M0col 0 M11 M12 … M1col 0 0 M22 … M2col … 0 0 0 … Mrow col
문제 이해를 위한 예시
입력:
{{5, 1, 6}
{8, 2, 0}
{3, 7, 4}}
출력:
상삼각형의 합 = 18
하삼각형의 합 = 29
설명:
상삼각형의 합 = 5 + 1 + 6 + 2 + 0 + 4 = 18
하삼각형의 합 = 5 + 8 + 2 + 3 + 7 + 4 = 29위 예시에서 상삼각형에는 인덱스 조건 i <= j를 만족하는 요소들이 포함되고, 하삼각형에는 j <= i를 만족하는 요소들이 포함됩니다. 두 경우 모두 주대각선 요소가 중복으로 포함된다는 점에 유의하세요.
해결 방법
이 문제의 가장 간단한 해결 방법은 반복문(loop)을 사용하여 배열을 순회하는 것입니다. 행렬의 모든 요소를 탐색하면서 각 요소의 인덱스 관계를 확인하고, 상삼각형 요소의 합은 uSum 변수에, 하삼각형 요소의 합은 lSum 변수에 각각 누적합니다.
알고리즘 단계
- 행렬의 크기(row, col)를 정의합니다.
- 상삼각형 합(uSum)과 하삼각형 합(lSum)을 저장할 변수를 0으로 초기화합니다.
- 이중 반복문으로 행렬 전체를 순회합니다.
i <= j인 경우 해당 요소를 uSum에 더합니다.j <= i인 경우 해당 요소를 lSum에 더합니다.- 두 합계를 출력합니다.
C++ 구현 예제
아래는 위 해결 방법의 동작을 보여주는 프로그램입니다.
#include <iostream>
using namespace std;
int row = 3;
int col = 3;
void sum(int mat[3][3]) {
int i, j;
int uSum = 0;
int lSum = 0;
// 상삼각형 요소의 합 계산
for (i = 0; i < row; i++)
for (j = 0; j < col; j++) {
if (i <= j) {
uSum += mat[i][j];
}
}
cout<<"상삼각형의 합: "<<uSum<<endl;
// 하삼각형 요소의 합 계산
for (i = 0; i < row; i++)
for (j = 0; j < col; j++) {
if (j <= i) {
lSum += mat[i][j];
}
}
cout<<"하삼각형의 합: "<<lSum<<endl;
}
int main() {
int mat[3][3] = { { 5, 1, 6 },
{ 8, 2, 0 },
{ 3, 7, 4 }};
sum(mat);
return 0;
}실행 결과
상삼각형의 합: 18 하삼각형의 합: 29
시간 및 공간 복잡도
- 시간 복잡도: O(N²) — 행렬의 모든 요소를 한 번씩 순회해야 하므로 N×N 행렬 기준 O(N²)입니다.
- 공간 복잡도: O(1) — 추가적인 저장 공간 없이 두 개의 합계 변수만 사용하므로 상수 공간이 필요합니다.
만약 두 개의 분리된 반복문 대신 하나의 반복문 안에서 두 조건을 동시에 검사하면, 같은 결과를 얻으면서도 코드를 더 간결하게 만들 수 있습니다.