[문제 풀이] Softeer "염기서열 커버" – 초염기서열 최소 개수 구하기

김준기·2025년 2월 18일
Softeeralgorithmpython
0

이 포스팅에서는 현대자동차 Softeer의 기출문제 [HSAT 6회 정기 코딩 인증평가 기출] 염기서열 커버를 다루며, 처음 떠올렸던 단순 풀이와 그 한계, 그리고 이를 극복하기 위해 수정한 아이디어와 최종 코드에 대해 설명합니다.

문제 개요

문제 설명

생명 공학을 연구하는 찬홍이는 DNA 염기서열을 연구 중이다. DNA 염기서열은 4종류의 핵염기 a, c, g, t가 일자로 연결된 문자열이며, 일부 좋은 염기서열은 와일드 카드 .를 포함하여 해당 위치에 어떤 염기도 들어갈 수 있음을 의미한다.

목표: 주어진 좋은 염기서열 N개(길이 M)를 모두 커버할 수 있는 “초염기서열”들을 만들 때, 필요한 초염기서열의 최소 개수를 구하라.

  • 입력 예제1

    4 5
a..tt
gc...
a.g.t
.c.ag

    출력 예제1: 2

  • 입력 예제2

    4 1
a
g
c
t

    출력 예제2: 4

  • 입력 예제3

    4 4
a...
.c..
..g.
...t

    출력 예제3: 1

처음 떠올린 풀이

문제를 처음 접했을 때, 각 위치별로 등장하는 실제 염기들을 set에 저장한 후, 가장 많은 후보가 나온 자리의 개수만큼 초염기서열이 필요하다는 단순 아이디어로 접근했습니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
record = [set() for _ in range(M)]

for _ in range(N):
    word = input().rstrip()
    for i, char in enumerate(word):
        if char == '.': continue
        record[i].add(char)

print(len(max(record, key=len)))

위 코드의 의도

이 코드는 각 열(위치)마다 등장하는 실제 염기 후보들을 기록하여, 한 위치에서 허용되는 염기의 종류를 파악하는 데 목적이 있습니다.
즉, "각 열은 독립적"이라는 가정 하에, 후보의 종류가 가장 많은 열의 개수가 초염기서열을 구성할 때 필요한 최소 개수라고 생각한 것입니다.

위 코드의 가장 큰 문제

문제의 핵심은 각 열을 독립적으로 판단하는 것이 아니라, 주어진 좋은 염기서열들 간의 상호 호환성을 고려해야 한다는 점입니다.
즉, 한 초염기서열이 여러 좋은 염기서열을 동시에 커버할 수 있는지 여부(예: 특정 위치에서 서로 다른 염기를 요구하는 경우의 충돌)를 전혀 반영하지 못했습니다.

테스트 결과, 이 단순 접근은 정답률이 약 40% 정도에 머물렀습니다.

개선된 접근 방법

문제 해결을 위해 다음과 같이 문제를 재분석하였습니다.

  1. 문제 목표: 주어진 좋은 염기서열들을 모두 커버하기 위한 초염기서열의 최소 개수를 구한다.
  2. 핵심 아이디어:
    • 서로 호환 가능한 좋은 염기서열들을 그룹으로 묶을 수 있다면, 한 초염기서열로 해당 그룹을 커버할 수 있다.
    • 호환성 판단: 두 염기서열이 같은 초염기서열로 커버 가능하려면, 각 위치에서 두 문자열이 모두 구체적인 염기를 요구하는 경우 서로 동일해야 한다.
  3. 전체 전략:
    • 모든 좋은 염기서열 쌍에 대해 서로 커버 가능한지(can_cover) 미리 계산합니다.
    • 이를 바탕으로, 부분 집합(mask) 단위로 "한 초염기서열로 커버 가능한" 그룹(coverable)을 구합니다.
    • 동적 계획법(DP)과 상태 압축을 이용해, 전체 염기서열을 커버할 수 있는 최소 그룹 수(즉, 초염기서열의 개수)를 계산합니다.

수정된 아이디어 설명

수정된 방법은 각 그룹 내의 염기서열들이 서로 호환되는지를 먼저 판단한 후, 커버 가능한 모든 집합을 이용하여 DP로 최소 그룹 수를 찾는 것입니다.
즉, 단순히 각 열의 후보 수를 따지는 대신, “어떤 부분 집합의 좋은 염기서열들은 한 초염기서열로 동시에 커버될 수 있는가?”를 체크하고, 이를 기반으로 전체 커버 문제를 해결합니다.

최종 코드 및 변수 설명

최종 코드는 다음과 같습니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
seqs = [input().rstrip() for _ in range(N)]

def can_cover(s1, s2):
    for i in range(M):
        # 두 문자열 모두 구체적 염기를 요구하는 경우 서로 같아야 함
        if s1[i] != '.' and s2[i] != '.' and s1[i] != s2[i]:
            return False
    return True

# compared 배열: 모든 염기서열 쌍의 호환성 미리 계산
# compared[i][j]가 True이면, 염기서열 i와 j는 한 초염기서열로 커버 가능하다.
compared = [[False] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        compared[i][j] = can_cover(seqs[i], seqs[j])

# coverable 배열: mask로 표현되는 염기서열 집합이 한 초염기서열로 커버 가능한지 저장
# coverable[mask]가 True이면, mask에 포함된 모든 염기서열은 서로 호환되어 한 초염기서열로 커버할 수 있다.
coverable = [False] * (1 << N)
coverable[0] = True  # 빈 집합은 의미상 커버 가능

for mask in range(1 << N):
    indices = [i for i in range(N) if mask & (1 << i)]
    ok = True
    for i in range(len(indices)):
        for j in range(i + 1, len(indices)):
            if not compared[indices[i]][indices[j]]:
                ok = False
                break
        if not ok:
            break
    coverable[mask] = ok

# dp 배열: dp[mask]는 mask에 해당하는 염기서열들을 커버하기 위해 필요한 최소 초염기서열의 개수
# 예를 들어, N=4에서 mask가 0b1011이면 0, 1, 3번 염기서열이 커버된 상태를 의미.
dp = [N for _ in range(1 << N)]
dp[0] = 0

for mask in range(1 << N):
    remain = mask ^ ((1 << N) - 1)  # 아직 커버되지 않은 염기서열, 즉 전체 집합에서 현재 mask를 뺀 나머지.
    sub = remain
    while sub:
        # 현재 remain의 모든 부분 집합(sub)을 순회합니다.
        # sub가 coverable하다는 것은, sub에 포함된 염기서열들이 한 초염기서열로 커버 가능한 그룹이라는 의미입니다.
        if coverable[sub]:
            next_mask = mask | sub  # 기존에 커버된 염기서열(mask)에 sub에 해당하는 염기서열을 추가.
            dp[next_mask] = min(dp[next_mask], dp[mask] + 1)
        # (sub - 1) & remain : remain 내의 다음 부분 집합을 구하는 전형적인 방법입니다.
        sub = (sub - 1) & remain


print(dp[-1])

변수 및 배열 설명

  • compared
    모든 좋은 염기서열 쌍의 호환성을 미리 계산한 2차원 배열입니다.

    • compared[i][j] = True이면, 염기서열 i와 j가 한 초염기서열로 커버 가능하다는 뜻입니다.

  • coverable
    각 부분 집합(mask)으로 표현되는 좋은 염기서열 그룹이 한 개의 초염기서열로 모두 커버 가능한지 여부를 저장합니다.

    • coverable[mask] = True이면, mask에 포함된 모든 염기서열들이 서로 호환되어 한 초염기서열로 커버할 수 있다는 의미입니다.

  • dp
    상태 압축(dynamic programming)을 사용하여, 현재까지 커버된 좋은 염기서열 집합(mask)에 대해 필요한 초염기서열의 최소 개수를 저장합니다.

    • 예시:
      • N=4일 때, mask = 0b1011은 0, 1, 3번 염기서열이 커버된 상태를 나타냅니다.
      • dp[mask]는 해당 상태에 도달하기 위해 사용된 초염기서열의 최소 개수를 의미합니다.

dp 전이 과정과 remain의 의미

다음 코드는 dp 상태를 갱신하는 부분입니다.

for mask in range(1 << N):
    remain = mask ^ ((1 << N) - 1)  # 아직 커버되지 않은 염기서열
    sub = remain
    while sub:
        # sub가 coverable하다면, mask와 합쳐 새로운 상태로 전이
        if coverable[sub]:
            next_mask = mask | sub
            dp[next_mask] = min(dp[next_mask], dp[mask] + 1)
        sub = (sub - 1) & remain

왜 remain을 구할까?

  • 목적:
    현재 mask는 이미 커버된 염기서열을 나타냅니다.
    remain 은 전체 염기서열 집합에서 아직 커버되지 않은 염기서열을 추려내기 위해 계산합니다.
  • 이유:
    • 효율적인 전이:
      dp를 업데이트할 때, 이미 커버된 염기서열은 다시 고려할 필요가 없습니다.
      따라서 남은(아직 커버되지 않은) 염기서열만 대상으로 한 번에 한 초염기서열로 커버 가능한 부분 집합(sub)을 탐색합니다.
    • 정확한 상태 전이:
      remain을 구함으로써, 현재 상태(mask)에서 추가해야 할 염기서열만 집중적으로 탐색할 수 있으며, 이를 통해 dp 상태를 올바르게 업데이트할 수 있습니다.

dp 전이 과정 상세 설명 및 시뮬레이션 예시

  1. mask와 remain

    • mask: 현재까지 커버된 염기서열을 비트마스크로 표현한 상태입니다.
    • remain: 전체 집합에서 mask에 해당하는 비트를 제외한, 아직 커버되지 않은 염기서열을 나타냅니다.
      • 예를 들어, N=3일 때 전체 집합은 0b111입니다.
      • 만약 mask = 0b010 (두 번째 염기서열만 커버됨)라면,
        remain = 0b010 ^ 0b111 = 0b101 → 첫 번째와 세 번째 염기서열이 아직 커버되지 않은 상태입니다.

  2. 부분 집합(sub) 순회

    • remain에 포함된 염기서열들 중에서, 한 초염기서열로 커버 가능한 그룹(sub)을 모두 탐색합니다.
    • 예를 들어, remain = 0b101일 경우 가능한 sub는:
      • sub = 0b101
      • sub = 0b100
      • sub = 0b001
      • (sub = 0은 반복문 종료 조건이므로 제외)

  3. dp 상태 전이 (업데이트)

    현재 Mask (binary)Remain (binary)선택한 sub (coverable)다음 Mask (mask | sub)dp 업데이트설명
    000111111111dp[111] = dp[000] + 1 = 1초기 상태(000)에서 모든 염기서열(111)을 한 번에 커버
    000111101101dp[101] = dp[000] + 1 = 1초기 상태(000)에서 염기서열 0,2(101)을 커버
    010101101111dp[111] = min(dp[111], dp[010] + 1) = 2상태 010에서 남은 염기서열 0,2(101)을 커버하여 전체(111) 도달
    • 현재 상태 mask에서, coverable한 부분 집합 sub를 선택하면 새로운 상태 next_mask = mask | sub가 됩니다.
    • 이때, dp[next_mask]는 dp[mask]에 초염기서열 1개를 추가한 값과 비교하여 최솟값으로 갱신됩니다.
    • 예시 시뮬레이션 (N=3):
      • 초기 상태: mask = 0b000 (아무것도 커버하지 않음), 따라서 dp[0] = 0
        → remain = 0b111 (전체 염기서열 모두 미커버)
      • 만약 sub = 0b111가 coverable하다면,
        next_mask = 0b000 | 0b111 = 0b111 → dp[0b111]는 dp[0] + 1로 1이 됩니다.
      • 혹은 coverable한 다른 부분 집합이 있다면, 각 상태에서 최소 초염기서열 수가 dp 배열에 갱신되어 전체 상태(mask = 0b111)에 도달할 때까지 진행됩니다.

이 과정은 현재 커버 상태(mask)에서 출발해, 아직 커버되지 않은 염기서열(remain) 중 한 번에 커버 가능한 그룹(sub)을 선택하여 전체 염기서열을 커버하는 최소 초염기서열 개수를 찾기 위한 핵심 전이 과정입니다.

마무리

초기 단순 접근은 각 열의 후보 수에만 의존하여 문제의 핵심인 서로 다른 좋은 염기서열 간의 호환성을 간과했습니다.
수정된 아이디어는 미리 호환성을 계산하고, 상태 압축 DP를 통해 최소 초염기서열 개수를 구하는 방식으로 문제의 복잡한 조건을 해결할 수 있었습니다.

문제 풀이 과정에서 부분 집합(마스크) 탐색과 상태 압축 DP를 경험할 수 있어 매우 유익한 문제였습니다. 여러분도 다양한 아이디어로 문제에 도전해보시기 바랍니다!

이상으로 Softeer "염기서열 커버" 문제 풀이 및 분석을 마칩니다. 질문이나 의견은 댓글로 남겨주세요!

profile
김준기
코딩 잘하고 싶은 백엔드 개발자
이전 포스트

FCM: 웹 푸시 알림 구현 시 발생한 오류 해결하기

다음 포스트

[문제 풀이] Softeer "업무 처리"

0개의 댓글