'r'개의 행과 'c'개의 열로 이루어진 행렬 M[r][c]가 주어졌을 때, 이 행렬이 마르코프 행렬(Markov Matrix)인지 아닌지를 판별하는 것이 목표입니다. 입력된 행렬이 마르코프 행렬이라면 "마르코프 행렬입니다"를 출력하고, 그렇지 않다면 "마르코프 행렬이 아닙니다"를 출력하면 됩니다.
마르코프 행렬(Markov Matrix)이란?
마르코프 행렬은 각 행의 원소 합이 정확히 1이 되는 행렬을 의미합니다. 즉, 행렬 M이 마르코프 행렬일 필요충분조건은 모든 행의 합이 1이라는 것입니다.
다음 예시를 살펴보겠습니다.
0.2 0.3 0.5 0.1 0.7 0.2 0.4 0.5 0.1
위 행렬의 각 행을 더해 보면 다음과 같습니다.
1행의 합 = 0.2 + 0.3 + 0.5 = 1.0 2행의 합 = 0.1 + 0.7 + 0.2 = 1.0 3행의 합 = 0.4 + 0.5 + 0.1 = 1.0
모든 행의 합이 1.0이므로 위 행렬은 마르코프 행렬입니다.
입력·출력 예시
입력: m[][] = { {0.2, 0.3, 0.5},
{0.1, 0.7, 0.2},
{0.4, 0.5, 0.1} }
출력: 마르코프 행렬입니다
입력: m[][] = { {0, 0, 1},
{0, 0.7, 0.3},
{0.5, 0.5, 0} }
출력: 마르코프 행렬입니다
접근 방법
가장 직관적인 방법은 각 행을 순서대로 순회하면서 해당 행의 원소들을 모두 더한 뒤, 그 합이 1인지 확인하는 것입니다. 각 행의 합을 별도의 1차원 배열에 저장해 두었다가 나중에 한 번에 검사할 수도 있지만, 행마다 바로바로 검사하면 추가 메모리 없이도 문제를 해결할 수 있습니다. 모든 행의 합이 1이면 주어진 행렬은 마르코프 행렬이고, 하나라도 1이 아니면 마르코프 행렬이 아닙니다.
알고리즘
시작
1단계 → 매크로 정의: #define n 3
2단계 → 마르코프 행렬 검사 함수 선언
bool check(double arr[][n])
반복문: int i = 0부터 i < n까지 i++
double형 변수 sum = 0으로 선언
반복문: int j = 0부터 j < n까지 j++
sum = sum + arr[i][j]
만약 (sum != 1)이면
false 반환
true 반환
3단계 → main() 함수
double arr[3][3] = { { 0, 0, 1 },
{ 0.5, 0, 0.5 },
{ 0.9, 0, 0.1 } } 선언
만약 check(arr)이 참이면
"마르코프 행렬입니다" 출력
아니면
"마르코프 행렬이 아닙니다" 출력
종료
C++ 구현 코드
#include <iostream>
using namespace std;
#define n 3
// 마르코프 행렬 여부를 검사하는 함수
bool check(double arr[][n]){
for (int i = 0; i <n; i++){
double sum = 0;
for (int j = 0; j < n; j++)
sum = sum + arr[i][j];
if (sum != 1)
return false;
}
return true;
}
int main(){
double arr[3][3] = { { 0, 0, 1 },
{ 0.5, 0, 0.5 },
{ 0.9, 0, 0.1 } };
if (check(arr))
cout << "마르코프 행렬입니다";
else
cout << "마르코프 행렬이 아닙니다";
}
실행 결과
마르코프 행렬입니다
참고 사항
double 타입 연산에서는 부동소수점 오차가 발생할 수 있습니다. 따라서 실무에서는 sum != 1처럼 값을 직접 비교하기보다 fabs(sum - 1.0) > 1e-9와 같이 허용 오차(epsilon)를 두고 비교하는 것이 더 안전합니다. 또한 이 알고리즘은 행렬 전체를 한 번씩만 순회하므로 시간 복잡도는 O(n²)이며, 공간 복잡도는 O(1)입니다.