코딩테스트: 모듈러 연산의 특성과 파이썬 int특성(04.07)

푼 문제:

피보나치 수, 둘만의 암호

 

피보나치 수(12945)

문제 내용

문제 이해:

반복문을 이용해 DP로 피보나치 수열을 만들어야한다. 매우 큰 입력값에도 정확한 값이 나와야한다.

 

시도 1: 마지막에 모듈러 연산만 하고 그냥 피보나치 수열 구하는 반복문 쓰기

def solution(n):
    fib=[0,1]
    for i in range(2,n+1):
        fib.append(fib[i-1]+fib[i-2]) 
    
    return fib[n]%1234567

잘 작동하여 정답 처리 되었다. 근데 중간에 확인하기위해 프린트를 한번 넣어보니 다음과 같은에러를 발생 시켰다.

ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

값의 크기가 너무 커서 int자료형이 담을 수 있는 최댓값을 넘어가서 오류가 발생한 것으로 보였다.

해결?: 모듈러 연산의 특성 이용하기

모듈러 연산(나머지 연산)은 3가지 특성을 가지고 있다.

이중 첫번째 특성을 이용하여, 배열에 새로운 피보나치 수를 더할 때 적용하여 범위를 제한할 수 있다.

 

def solution(n):
    fib=[0,1]
    for i in range(2,n+1):
        fib.append(fib[i-1]+fib[i-2]%1234567)
    
    return fib[n]%1234567

위의 특성에서 보여준 식과 다르게 'fib[i-2]%1234567'와 'return fib[n]%1234567'에만 적용한 이유는 모듈러 연산의 합동 개념 때문이다.

17과 7은 mod 10에 대해 합동이다

아무튼 이렇게 하자 중간에 출력을 시켜도 에러가 발생하지는 않았다.

그런데 이상하지 않은가? 자료형의 최댓값을 넘어갔다면, 첫번째 시도에서는 print함수를 사용 하든 하지 않든 에러가 발생했어야 했는데, 마지막에 모듈러 연산만 넣으면 오류가 없다. 심지어 모듈러 연산을 아예 안해도 터미널에 출력을 안하면 오류가 발생하지 않는다!

 

원인의 탐구

오류를 자세히 읽어보자, 이 오류가 정수 자료형의 문제가 아님을 알 수 있었다.

for integer string conversion; use sys.set_int_max_str_digits() 

즉, 문자열 자료형으로 변환 할때 문제가 발생하는 것이었다. 그럼 그냥 정수 자체는 크기 문제가 없느냐? 궁금해서 찾아봤더니 파이썬3 에서는 int자료형이 arbitrary precision을 제공하는데, 이는  자료형이 정해진 크기만큼만 메모리 공간을 차지하는 것이 아니라, 사용할 수 있는 모든 공간을 써서 값을 저장할 수 있게 한다. 즉 사용가능한 메모리 크기가 제한선이고, 그 안에서는 얼마든지 큰 수도 처리할 수 있다.

하지만 자료형을 str으로 변환하려 하면, 정해진 자릿수의 한계가 있어서 오류가 생긴다.

 

 

둘만의 암호(155652)

 

문제내용

문제 내용

주어진 입력에 따라 암호문을 복호화 해야한다. z 이후 a로 돌아오는 것을 구현할 줄 아는지가 관건이다.

 

해결: set와 모듈러 연산을 이용하기

def solution(s, skip, index):
    codex=set('abcdefghijklmnopqrstuvwxyz')-set(skip)  # 복호화표 만들기: 문자들 추리기
    codex=sorted(list(codex)) # 다시 정렬(set 연산시 정렬 깨질 수 있음)
    string=''
    for c in s:
        indx=codex.index(c)  # 해당 문자의 복호화표에서의 위치 찾기
        indx =(index+indx)%len(codex)  # index만큼 뒤로 이동. 모듈러 연산 이용
        string += codex[indx]
    return string

set의 차집합 연산을 통해 손쉽게 skip에 있는 문자들을 걸러낼 수 있다.

리스트의 index 메서드를 통해 특정 요소의 인덱스를 역으로 구할 수 있다.

모듈러 연산을 이용해 손쉽게 순환조회를 구현할 수 있다.

그러나 index메서드를 통해 순회하며 인덱스를 찾는 것은 느린편이다.

 

해결2 : 딕셔너리와 for문 이용하기

def solution(s, skip, index):
    codex=sorted(list(set('abcdefghijklmnopqrstuvwxyz')-set(skip)))
    length=len(codex)
    reverse_codex={x:i for i,x in enumerate(codex)}
    string=''
    print(codex)
    for c in s:
        indx=reverse_codex[c]
        indx =(index+indx)%length
        string += codex[indx]
    return string

이 방식은 요소의 값에 따른 복호화표에서의 인덱스를 찾기 위해 리스트의 메서드를 사용하지 않고 값을 키로, 인덱스를 밸류로 가지는 딕셔너리를 사용한다. 이런 딕셔너리를 만들 기 위해 리스트 컴프리헨션 문법을 적용한 for문을 사용할 수 있다.

 

해결3. ascii_lowercase

from string import ascii_lowercase
def solution(s, skip, index):
    codex=sorted(list(set(ascii_lowercase)-set(skip)))
    ...

말 그대로 알파벳 소문자가 사전순으로 하나씩 들어있는 문자열을 string 모듈로부터 가져올 수 있다. 일일히 a부터 z까지 칠 필요가 없다.

사실 임포트 안하고 반복문과 chr()을 이용해도 되지만 아무튼 편하다.

 

배운점

1. 모듈러 연산자의 특성을 다시 배웠다. 큰 수의 모듈러 연산에 응용할 수 있다.

2. 파이썬의 int 자료형의 특성을 알게 됐다.

3. string모듈로부터 종류별로 모아놓은 문자열을 가져올 수 있다.

whitespace = ' \t\n\r\v\f'
ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_letters = ascii_lowercase + ascii_uppercase
digits = '0123456789'
hexdigits = digits + 'abcdef' + 'ABCDEF'
octdigits = '01234567'
punctuation = r"""!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~"""
printable = digits + ascii_letters + punctuation + whitespace

 

레퍼런스

https://ahracho.github.io/posts/python/2017-05-09-python-integer-overflow/

[기초 파이썬] 파이썬 3에는 오버플로우가 없다?

https://python-reference.readthedocs.io/en/latest/docs/ints/

int — Python Reference (The Right Way) 0.1 documentation