C++로 반복되는 DNA 시퀀스 찾기: 비트 마스킹 기법 완벽 정리

DNA 서열이 주어졌을 때, 그 안에서 반복적으로 나타나는 10글자 길이의 부분 문자열(substring)을 모두 찾는 문제를 풀어보겠습니다. DNA는 A(아데닌), C(시토신), G(구아닌), T(티민)라는 네 가지 뉴클레오타이드의 연속으로 구성됩니다. 예를 들어 "ACGAATTCCG"와 같은 형태죠. DNA를 연구할 때 특정 서열이 여러 번 등장하는지 확인하는 것은 매우 유용한 분석 방법입니다.

문제 정의

주어진 DNA 분자에서 10글자 길이의 서열 중 두 번 이상 나타나는 것을 모두 찾아야 합니다.

예를 들어 입력이 다음과 같다면:

"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

출력은 아래와 같습니다:

["AAAAACCCCC", "CCCCCAAAAA"]

해결 전략: 비트 마스킹(Bit Masking)

단순히 모든 10글자 부분 문자열을 추출해서 비교하면 O(n × 10)의 메모리가 필요해 비효율적입니다. 대신 각 뉴클레오타이드를 2비트 숫자로 인코딩하면 10글자 서열을 단 하나의 20비트 정수로 표현할 수 있습니다.

A → 0 (2비트: 00)
C → 1 (2비트: 01)
G → 2 (2비트: 10)
T → 3 (2비트: 11)

알고리즘의 핵심 단계는 다음과 같습니다.

결과를 담을 배열 ret을 선언하고, 문자열 길이 n을 구합니다.
이미 본 서열을 저장할 집합 visited와, 결과에 이미 추가된 서열을 저장할 집합 visited2를 만듭니다.
각 문자(A, C, G, T)에 해당하는 값(0, 1, 2, 3)을 저장하는 맵 bitVal을 정의합니다.
mask := 0으로 초기화합니다.
i를 0부터 n-1까지 순회하며:
- mask를 왼쪽으로 2비트 시프트합니다 (mask *= 4).
- 현재 문자의 값을 mask에 OR 연산으로 추가합니다.
- mask를 0xFFFFF와 AND 연산하여 하위 20비트만 유지합니다 (10글자 = 20비트).
i가 9 미만이면 아직 10글자가 채워지지 않았으므로 다음 반복으로 넘어갑니다.
현재 mask가 visited에는 있지만 visited2에는 없다면, 처음 발견된 반복 서열이므로 s.substr(i - 9, 10)을 ret에 추가하고 mask를 visited2에 삽입합니다.
매번 mask를 visited에 삽입합니다.

마지막으로 ret을 반환하면 됩니다. 이렇게 하면 동일한 서열이 세 번 이상 나타나도 결과에 한 번만 포함됩니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
    vector<string>findRepeatedDnaSequences(string s) {
        vector <string> ret;
        int n = s.size();
        set <int> visited;
        set <int> visited2;
        map <char, int> bitVal;
        bitVal['A'] = 0;
        bitVal['C'] = 1;
        bitVal['G'] = 2;
        bitVal['T'] = 3;
        lli mask = 0;
        for(int i = 0; i < n; i++){
            mask <<= 2;
            mask |= bitVal[s[i]];
            mask &= 0xfffff;
            if(i < 9) continue;
            if(visited.count(mask) && !visited2.count(mask)){
                ret.push_back(s.substr(i - 9, 10));
                visited2.insert(mask);
            }
            visited.insert(mask);
        }
        return ret;
    }
};
main(){
    Solution ob;
    print_vector(ob.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
}

입력

"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

출력

[AAAAACCCCC, CCCCCAAAAA]

복잡도 분석

이 방식은 문자열을 직접 저장하지 않고 20비트 정수만 다루므로 메모리 사용량이 크게 줄어듭니다. 시간 복잡도는 O(n), 공간 복잡도 역시 O(n) 수준으로, 슬라이딩 윈도우와 비트 연산을 결합한 효율적인 접근법입니다.