C++로 배우는 확장 행렬의 이전 요소 찾기 알고리즘

이 글에서는 확장 행렬(Expanding Matrix)과 관련된 문제를 다룹니다. 확장 행렬이란 크기가 일정한 배율에 따라 지속적으로 증가하는 행렬을 의미합니다.

여기서는 문자로 구성된 행렬이 배율 2로 확장되는 경우를 살펴봅니다. 원래 행렬의 크기가 N × N이라면, 확장된 행렬의 크기는 2N × 2N이 됩니다. 특정 위치 (i, j)에 있는 문자열 시퀀스가 주어졌을 때, 바로 왼쪽에 위치한 시퀀스, 즉 (i, (j-1)%N) 위치의 값을 반환해야 합니다.

확장 행렬의 구조 이해하기

초기 확장 행렬을 시각화하면서 문제를 이해해 보겠습니다.

주어진 행렬 -> [ a, b ] [ c, d ], 2×2 행렬
{ a, b, c, d }와 곱셈

A X [ a, b ]
B X [ a, b ]
C X [ a, b ]
D X [ a, b ]
[ c, d ] [ c, d ] [ c, d ] [ c, d ]

확장된 행렬 -> [ aa, ab, ba, bb ]
[ ac, ad, bc, bd ]
[ ca, cb, da, db ]
[ cc, cd, dc, dd ], 4×4 행렬

행렬을 다시 한 번 확장하려면 같은 방식으로 { a, b, c, d }를 곱하면 되며, 이 경우 8×8 크기의 행렬이 만들어집니다.

확장된 행렬 -> [ aaa, aab, aba, abb, baa, bab, bba, bbb ]
[ aac, aad, abc, abd, bac, bad, bbc, bbd ]
[ aca, acb, ada, adb, bca, bcb, bda, bdb ]
[ acc, acd, adc, add, bcc, bcd, bdc, bdd ]
[ caa, cab, cba, cbb, daa, dab, dba, dbb ]
[ cac, cad, cbc, cbd, dac, dad, dbc, dbd ]
[ cca, ccb, cda, cdb, dca, dcb, dda, ddb ]
[ ccc, ccd, cdc, cdd, dcc, dcd, ddc, ddd ]

위와 같은 확장 행렬이 있을 때, 예를 들어 문자열 시퀀스 "bcc"가 주어지면 바로 왼쪽에 있는 시퀀스인 "add"를 반환해야 합니다. 또한 행렬은 순환(circular) 구조로 가정합니다. 즉, 주어진 시퀀스가 (i, 0) 위치에 있다면 (i, N-1) 위치의 시퀀스를 반환합니다.

입력 및 출력 예시

입력: abb
출력: aba
설명: 8×8 행렬에서 abb 바로 왼쪽에 있는 시퀀스는 aba입니다.

입력: aadc
출력: aacd

입력: abbcd
출력: abbcc

기본적인 접근 방법

문제를 처음 접하면 가장 먼저 떠오르는 해결책은 주어진 시퀀스를 포함하는 확장 행렬을 직접 찾는 것입니다. 하지만 이 방법은 상당히 복잡합니다. 해당 크기의 행렬을 먼저 생성한 뒤 시퀀스를 검색해야 하기 때문에 비효율적입니다.

효율적인 접근 방법

몇 개의 초기 확장 행렬을 관찰해 보면, 이전 요소를 손쉽게 찾을 수 있는 규칙적인 패턴을 발견할 수 있습니다. 핵심 규칙은 다음과 같습니다.

문자열 시퀀스를 마지막 인덱스부터 역순으로 순회합니다.
현재 인덱스의 요소가 'b' 또는 'd'라면, 각각 'a' 또는 'c'로 변경하고 순회를 중단합니다.
현재 인덱스의 요소가 'a' 또는 'c'라면, 각각 'b' 또는 'd'로 변경하고 다음(앞쪽) 인덱스로 이동하여 계속 검사합니다.

이 패턴은 이진수 카운팅의 자리올림 원리와 유사합니다. 'b'는 'a'의 다음 값이고 'd'는 'c'의 다음 값이므로, 끝자리부터 감소시키다가 내림이 필요 없는 지점에서 멈추는 방식으로 동작합니다.

C++ 구현 예제

위 접근 방식을 C++ 코드로 구현하면 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    string seq = "abbcd";
    int n = seq.length();
    // 문자열을 끝에서부터 역순으로 순회
    for (int i = n - 1; i >= 0; i--) {
        // 요소가 b 또는 d이면 변경하고 순회 종료
        if (seq[i] == 'b') {
            seq[i] = 'a';
            break;
        }
        if (seq[i] == 'd') {
            seq[i] = 'c';
            break;
        }
        // 요소가 a 또는 c이면 변경하고 앞 요소 검사로 진행
        if (seq[i] == 'a')
            seq[i] = 'b';
        else if (seq[i] == 'c')
            seq[i] = 'd';
    }
    cout << "The Previous sequence is: " << seq;
    return 0;
}

실행 결과

The previous sequence is: abbcc

위 코드의 시간 복잡도는 O(N)으로, 주어진 시퀀스의 길이에 비례합니다. 행렬을 실제로 생성하지 않고도 정답을 구할 수 있어 공간 복잡도 역시 O(1) 수준으로 매우 효율적입니다.

마무리

이번 글에서는 문자 확장 행렬이 무엇이고 어떻게 형성되는지 살펴보았습니다. 아울러 확장 행렬에서 이전 요소를 찾는 문제를 다루었으며, 행렬을 확장할 때 나타나는 패턴을 이해함으로써 이를 효율적으로 해결하는 방법을 확인했습니다.

소개한 C++ 코드는 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮겨 작성할 수 있습니다. 이 튜토리얼이 여러분의 학습에 도움이 되기를 바랍니다.