Python으로 숫자의 이진 표현에서 가장 긴 연속된 1의 길이 찾는 방법

주어진 숫자를 이진수(binary)로 변환했을 때, 그 표현 안에서 가장 길게 연속된 1(1's)의 길이를 구하는 프로그램을 Python으로 작성해 보겠습니다.

예제

입력: n = 15
출력: 4
15의 이진 표현은 1111이며, 연속된 1의 최대 길이는 4입니다.

알고리즘

이 문제는 비트 연산(bitwise operation)을 활용하면 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 숫자를 입력받습니다.
2. 카운터 변수 c = 0으로 초기화합니다.
3. 숫자가 0이 될 때까지 반복하며, 각 반복마다 카운터를 1씩 증가시킵니다.
4. 매번 n & (n << 1) 연산을 수행하는데, 이 연산은 모든 1의 시퀀스 길이를 한 칸씩 줄여줍니다.

즉, 이 비트 AND 연산을 한 번 수행할 때마다 연속된 1의 묶음이 하나씩 사라지므로, 숫자가 0이 될 때까지 필요한 반복 횟수가 곧 가장 긴 연속 1의 길이가 됩니다.

예제 코드

# 숫자의 이진 표현에서
# 가장 긴 연속된 1의 길이를 찾는 Python 프로그램
def maxlength(n):
   # 결과값 초기화
   c = 0
   # x = 0에 도달할 때까지의
   # 반복 횟수를 셉니다.
   while (n != 0):
      # 이 연산은 모든 1의 시퀀스 길이를
      # 하나씩 줄입니다.
      n = (n & (n << 1))
      c = c + 1
   return c

# 드라이버 코드
n = int(input("숫자를 입력하세요 ::>"))
print("연속된 1의 최대 길이 ::>", maxlength(n))

실행 결과

숫자를 입력하세요 ::>15
연속된 1의 최대 길이 ::>4

동작 원리 살펴보기

n = 15일 때 과정을 단계별로 확인해 보면 다음과 같습니다.

• 1단계: 15는 이진수로 1111 → 15 & (15 << 1) = 1111 & 1110 = 1110, c = 1
• 2단계: 1110 & 1100 = 1100, c = 2
• 3단계: 1100 & 1000 = 1000, c = 3
• 4단계: 1000 & 0000 = 0000, c = 4

숫자가 0이 되었으므로 반복이 종료되고, 최종 결과인 4가 반환됩니다. 이 방법은 별도의 이진수 변환 없이 비트 연산만으로 O(log n) 시간 복잡도 내에 답을 구할 수 있는 효율적인 기법입니다.