k일 후 활성 셀과 비활성 셀 개수 구하기

문제 개요

흥미로운 알고리즘 문제를 하나 살펴보겠습니다. 크기가 n인 이진 배열(binary array)이 주어져 있다고 가정합니다. 단, n은 3보다 커야 합니다. 배열에서 1(true)은 활성(active) 상태를, 0(false)은 비활성(inactive) 상태를 의미합니다. 함께 주어진 숫자 k만큼의 날이 지난 뒤, 배열에 남아 있는 활성 셀과 비활성 셀의 개수를 구하는 것이 목표입니다.

상태 변화 규칙은 다음과 같습니다. 매일 i번째 셀은 왼쪽 셀과 오른쪽 셀의 값이 서로 다르면 활성(1)이 되고, 같으면 비활성(0)이 됩니다. 가장 왼쪽 셀과 가장 오른쪽 셀은 한쪽 방향에 이웃한 셀이 존재하지 않으므로, 항상 0으로 고정됩니다.

예제로 이해하기

배열이 {0, 1, 0, 1, 0, 1, 0, 1}이고 k = 3이라고 가정해 보겠습니다. 날짜별로 상태가 어떻게 바뀌는지 확인해 보겠습니다.

• 1일 후: {1, 0, 0, 0, 0, 0, 0, 0}
• 2일 후: {0, 1, 0, 0, 0, 0, 0, 0}
• 3일 후: {1, 0, 1, 0, 0, 0, 0, 0}

따라서 최종 결과는 활성 셀 2개, 비활성 셀 6개입니다.

알고리즘

핵심 아이디어는 XOR 연산입니다. 두 비트가 같으면 XOR 결과는 0, 다르면 1이 되므로, "좌우 셀이 다른가?"라는 조건을 간단히 arr[i-1] ^ arr[i+1]로 표현할 수 있습니다. 양 끝 셀은 이웃이 없으므로 0과의 XOR 연산으로 처리합니다.

activeCellKdays(arr, n, k)

begin
    make a copy of arr into temp
    for i in range 1 to k, do
        temp[0] := 0 XOR arr[1]
        temp[n-1] := 0 XOR arr[n-2]
        for each cell i from 1 to n-2, do
            temp[i] := arr[i-1] XOR arr[i+1]
        done
        copy temp to arr for next iteration
    done
    count number of 1s as active, and number of 0s as inactive, then return the values.
end

주의할 점은 현재 상태를 기준으로 다음 날의 상태를 동시에 계산해야 하므로, 원본 배열을 직접 수정하지 않고 임시 배열(temp)에 결과를 저장한 뒤 복사해야 한다는 것입니다.

C++ 구현 예제

#include <iostream>
using namespace std;
void activeCellKdays(bool arr[], int n, int k) {
    bool temp[n]; // temp는 arr의 복사본을 저장
    for (int i=0; i<n ; i++)
        temp[i] = arr[i];
    for(int i = 0; i<k; i++){
        temp[0] = 0^arr[1]; // 왼쪽 끝 셀 값 설정
        temp[n-1] = 0^arr[n-2]; // 오른쪽 끝 셀 값 설정
        for (int i=1; i<=n-2; i++) // 모든 중간 셀에 대해 좌우 값이 다르면 1 저장
        temp[i] = arr[i-1] ^ arr[i+1];
        for (int i=0; i<n; i++)
            arr[i] = temp[i]; // 다음 반복을 위해 temp를 arr에 복사
    }
    int active = 0, inactive = 0;
    for (int i=0; i<n; i++)
        if (arr[i])
            active++;
        else
            inactive++;
    cout << "Active Cells = "<< active <<", Inactive Cells = " << inactive;
}
main() {
    bool arr[] = {0, 1, 0, 1, 0, 1, 0, 1};
    int k = 3;
    int n = sizeof(arr)/sizeof(arr[0]);
    activeCellKdays(arr, n, k);
}

실행 결과

Active Cells = 2, Inactive Cells = 6

출력 결과에서 알 수 있듯이, 3일이 지난 후 배열에는 활성 셀이 2개, 비활성 셀이 6개 남게 됩니다. 이 알고리즘의 시간 복잡도는 O(n × k)이며, 공간 복잡도는 O(n)입니다.