파이썬 코딩테스트 강좌, DNA 비밀번호

코딩테스트 준비를 위해 많은 사람들이 알고리즘 문제를 풀고 있습니다. 이번 강좌에서는 DNA 비밀번호 문제에 대해 알아보고, 문제를 어떻게 해결할 수 있는지 단계별로 설명하겠습니다.

문제 설명

DNA의 비밀번호는 특정한 패턴의 조합으로 이루어져 있습니다. 주어진 DNA 문자열에서 비밀번호가 되는 서브 문자열이 몇 개 있는지를 찾는 문제가 주어집니다. 다음은 문제의 세부 내용입니다.

문제 정의

주어진 DNA 문자열에서, “””ACGT””” 문자만 포함하고, 길이가 K 이상인 모든 서브 문자열 중에서 서로 다른 서브 문자열의 개수를 세어라.

입력

첫 번째 줄에는 DNA 문자열이 주어진다. (1 ≤ 문자열 길이 ≤ 1000)
두 번째 줄에는 K의 값이 주어진다. (1 ≤ K ≤ 100)

출력

서로 다른 서브 문자열의 총 개수를 출력하라.

문제 해결 과정

이 문제를 효율적으로 해결하기 위해 다음과 같은 단계로 문제를 풀겠습니니다:

1단계: 서브 문자열 생성

주어진 DNA 문자열에서 K 이상의 길이를 가진 모든 서브 문자열을 생성합니다. 이를 위해 문자열의 시작 인덱스를 순회하면서, 각 시작 인덱스에서 K 이상의 길이를 가지는 서브 문자열을 추출합니다.

2단계: 고유한 서브 문자열 저장

생성된 서브 문자열을 집합(Set)에 저장합니다. 집합은 중복을 허용하지 않기 때문에, 서로 다른 서브 문자열만 저장됩니다. 이 과정에서 set 자료형을 활용할 수 있습니다.

3단계: 결과 출력

최종적으로 집합에 저장된 서브 문자열의 개수를 센 후 출력하면 됩니다. 이제 이러한 과정을 코드로 변환해 보겠습니다.

파이썬 코드


def count_unique_dna_substrings(dna: str, k: int) -> int:
    unique_substrings = set()  # 서브 문자열을 저장할 집합
    n = len(dna)

    # 문자열의 모든 시작 위치에 대해 서브 문자열을 추출
    for start in range(n):
        for end in range(start + k, n + 1):  # K 이상인 길이만 고려
            substring = dna[start:end]
            unique_substrings.add(substring)

    return len(unique_substrings)  # 고유한 서브 문자열의 개수 반환

# 입력 받기
if __name__ == "__main__":
    dna_string = input("DNA 문자열을 입력하세요: ")
    k_value = int(input("길이 K를 입력하세요: "))
    
    # 고유 서브 문자열의 수 계산 및 출력
    result = count_unique_dna_substrings(dna_string, k_value)
    print(f"서로 다른 서브 문자열의 개수는: {result}")

코드 설명

위 코드에서 사용한 함수 count_unique_dna_substrings는 두 개의 매개변수를 받습니다: dna 문자열과 k 값입니다. 이 함수는 먼저 빈 집합을 만들어 서브 문자열을 저장할 준비를 합니다. 이후 아랫 단계에서 설명할 반복문을 통해 서브 문자열을 추출합니다.

반복문 해설

첫 번째 반복문은 DNA 문자열의 시작 인덱스(start)를 순회합니다. 두 번째 반복문은 시작 인덱스부터 k 이상의 길이를 가진 서브 문자열을 추출하며, 이를 통해 end 인덱스를 결정합니다. 각 서브 문자열은 집합에 추가되어 서로 다른 경우의 수만 저장됩니다.

이해를 돕는 예시

예를 들어, 입력으로 주어진 DNA 문자열이 ACGTACGT이고 K의 값이 2라면, 생성될 수 있는 서브 문자열은 다음과 같습니다:

AC, ACG, ACGT, ACGTA, ACGTAC, ACGTACGT
CG, CGT, CGTA, CGTAC, CGTACG
GT, GTA, GTAC, GTACG
TA, TAC, TACG
AC, ACG, ACGT

이 처럼 총 14개의 서로 다른 서브 문자열이 존재하게 됩니다.

성능 고려사항

위 코드는 모든 시작 인덱스에 대해 모든 길이의 서브 문자열을 체크하기 때문에, 최악의 경우 시간 복잡도는 O(n^3)이 됩니다. 문자열 길이가 1000에 이르는 경우 성능 문제가 발생할 수 있습니다. 극한의 경우 성능을 개선하기 위하여 Sliding Window 기법을 고려할 수 있습니다.

Sliding Window 기법 적용

Sliding Window 기법을 사용하면 한 번의 순회를 통해 길이 >= K를 가진 서브 문자열의 개수를 쉽게 계산할 수 있습니다. 즉, 한 번의 순회로 문자열의 길이에 대한 정보를 저장하여 탐색하는 방식입니다. 이 기법은 시간 복잡도를 O(n^2) 또는 O(n)으로 줄일 수 있습니다.

마무리

이번 강좌에서는 DNA 비밀번호 문제를 통해 문자열의 서브 문자열을 처리하고, 집합을 활용하여 중복 문제를 해결하는 방법에 대해 알아보았습니다. 이와 같은 문제는 코딩테스트에 자주 등장하므로, 기본적인 문자열 처리 방법을 잘 익혀두는 것이 좋습니다. 다음 강좌에서는 또 다른 유용한 알고리즘 문제를 다루어 보겠습니다.