모스부호(피보나치 수열)

모스부호는 2가지 신호인 짧은 발신 전류(1)와 긴 발신 전류(00)를 조합해 만듭니다.

만들 수 있는 모스부호의 최대 길이를 줬을 때 두 가지 신호를 적절히 사용해 문자를 만들려고 합니다.

이것의 경우의 수를 출력하는 프로그램을 작성하세요.

예를 들어, 신호의 최대 길이가 4일 때는 0011, 0000, 1001, 1100, 1111을 만들 수 있으므로 경우의 수는 5입니다.

 

지시사항

입력

첫 번째 줄에 모스부호의 최대 길이인 자연수 N을 입력합니다.(1≤N≤1000000)

출력

첫 번째 줄에 만들 수 있는 모스부호의 경우의 수를 15,746으로 나눈 나머지를 출력합니다.

 

입력예시

4

출력예시

5

---

 

문제의 입력값과 출력값을 쭉 적어보니, 피보나치수열이었다.피보나치수열을 리스트로 구현해본 적이 있어서 이번에도 그렇게 해 보았다.input(N) 1 2 3 4 5   6   7   8   9 10output    1 2 3 5 8 12 20 32 52 84

N = int(input())
lst = [1, 2]

if N >= 3:
    for _ in range(3, N + 1):
        lst.append((lst[-1] + lst[-2]))

result = lst[N-1] % 15746
print(result)

 

이렇게 제출을 했더니, 몇 가지 케이스에서 오답처리가 되었다.

처음에는 피보나치 수열을 처리하는 과정에서 시간초과가 되는가 싶어서,

코파일럿의 도움을 받아 좀 더 간단한 피보나치 수열의 구현 방법을 작성해보았다.

 

N = int(input())

if N == 1:
    print(1)
elif N == 2:
    print(2)
else:
    a, b = 1, 2
    for _ in range(3, N + 1):
        a, b = b, (a + b)
    print(b % 15746)

 

그랬더니 위에 코드에서 '오답'으로 나왔던 테스트 케이스들이 '시간초과'로 나오는 것이었다.

어떤 부분이 이런 차이점을 발생시키는 건지 찾아봤다.

 

결론은, 모듈러연산을 마지막에 한번만 수행하게 되면, 처리하는 값이 매우 커지므로 발생하는 문제였다.

첫 번째 코드에서는 리스트의 값이 커져서 오버플로우나 메모리 문제로 '오답'처리가,

두 번째 코드에서는 반복문 내부에서 모듈러 연산을 수행하지 않아 값이 매우 커져 '시간초과'가 발생했을 가능성이 있다.

(모듈러 연산에 대한 정리는 글 아래 짧게 정리하였다.)

 

결국 모듈러 연산을 출력 직전이 아닌 반복문 내부에서 수행하여, 데이터들이 너무 커지는 것을 방지하는 것이 해결책이었고, 아래와 같이 코드를 수정했다.

 

N = int(input())

if N == 1:
    print(1)
elif N == 2:
    print(2)
else:
    a, b = 1, 2
    for _ in range(3, N+1):
        a, b = b, (a+b) % 15746 
    print(b)

 

---

 

모듈러 연산

모듈러 연산은 숫자를 나눌 때 나머지를 구하는 연산입니다. 예를 들어, 10을 3으로 나누면 몫은 3이고 나머지는 1입니다. 이때 나머지 1이 모듈러 연산의 결과입니다.

 

1. 큰 수의 계산:
   • 큰 수를 다룰 때 값이 너무 커지는 것을 방지하기 위해 사용됩니다. 예를 들어, 피보나치 수열이나 팩토리얼 계산에서 모듈러 연산을 사용하면 값이 일정 범위 내에 머물도록 할 수 있습니다.
2. 주기적인 패턴:
   • 주기적인 패턴을 찾거나 생성할 때 사용됩니다. 예를 들어, 원형 배열에서 인덱스를 순환할 때 모듈러 연산을 사용하면 배열의 끝에 도달했을 때 다시 처음으로 돌아갈 수 있습니다.

   index = (index + 1) % array_length
   

3. 해시 함수:
   • 해시 테이블에서 키를 배열의 인덱스로 변환할 때 사용됩니다. 해시 함수는 주어진 키를 특정 범위 내의 인덱스로 변환하는데, 이때 모듈러 연산이 사용됩니다.

   index = hash(key) % table_size
   

4. 짝수/홀수 판별:
   • 숫자가 짝수인지 홀수인지 판별할 때 사용됩니다. 예를 들어, n % 2 == 0이면 짝수, n % 2 == 1이면 홀수입니다.
5. 시간 계산:
   • 시간 계산에서 자주 사용됩니다. 예를 들어, 24시간 형식에서 시간을 계산할 때 모듈러 연산을 사용하면 24를 넘는 시간을 다시 0부터 시작하게 할 수 있습니다.

   hour = (current_hour + added_hours) % 24