연속된 1이 없는 이진 문자열의 개수를 세는 파이썬 프로그램

이 글에서는 아래와 같은 문제에 대한 해결 방법을 자세히 알아보겠습니다.

문제 정의

문제: 양의 정수 N이 주어졌을 때, 길이가 N인 모든 이진 문자열 중에서 연속된 두 개의 1이 나타나지 않는 문자열의 개수를 구해야 합니다.

예를 들어 N=3이라면, 가능한 조합은 000, 001, 010, 100, 101로 총 5가지입니다. 반면 011, 110, 111은 연속된 1을 포함하고 있으므로 제외됩니다.

접근 방식: 동적 계획법(DP)

이 문제는 피보나치 수열과 밀접한 관련이 있으며, 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 각 길이 i에 대해 두 가지 상태를 추적합니다.

• a[i]: 길이가 i이고 마지막 문자가 '0'으로 끝나는 문자열의 개수
• b[i]: 길이가 i이고 마지막 문자가 '1'로 끝나는 문자열의 개수

점화식은 다음과 같이 정의됩니다.

• a[i] = a[i-1] + b[i-1] → 어떤 문자열 뒤에든 '0'을 붙일 수 있으므로, 이전 단계의 모든 문자열에 '0'을 추가한 경우의 수입니다.
• b[i] = a[i-1] → 연속된 1을 피하려면 '1'은 반드시 '0'으로 끝나는 문자열 뒤에만 붙일 수 있습니다.

따라서 최종 답은 a[n-1] + b[n-1]이 됩니다.

구현 예제

# 연속된 1이 없는 이진 문자열의 개수를 세는 함수
def countStrings(n):
    a=[0 for i in range(n)]
    b=[0 for i in range(n)]
    a[0] = b[0] = 1
    for i in range(1,n):
        a[i] = a[i-1] + b[i-1]
        b[i] = a[i-1]
    return a[n-1] + b[n-1]

# 메인
n=5
print("문자열의 개수: ",countStrings(n))

출력 결과

문자열의 개수: 13

위 코드에서 모든 변수는 지역 범위(local scope) 내에서 선언되며, 각 단계별 참조 관계는 아래 그림과 같습니다.

N=5일 때 답이 13이 되는 과정을 단계별로 살펴보면 다음과 같습니다.

최종 결과는 a[4] + b[4] = 8 + 5 = 13입니다.

결론

이 글에서는 동적 계획법을 활용하여 연속된 1이 포함되지 않는 길이 N의 이진 문자열 개수를 계산하는 파이썬 프로그램을 작성하는 방법을 배웠습니다. 이 접근 방식의 시간 복잡도는 O(N), 공간 복잡도 역시 O(N)입니다. 흥미롭게도 결과값이 피보나치 수열과 동일한 패턴을 따르기 때문에, 두 개의 변수만 유지하면 공간 복잡도를 O(1)까지 줄일 수 있다는 점도 기억해두면 좋습니다.