파이썬 과제 풀이(유리수를 이용한 n에서 m진수 변환 코드)

 2학년 전공 필수인 파이썬 프로그래밍 과제 풀이이다. 난이도가 상당해서 과제임에도 불구하고 한번 올려본다. 

(파이썬을 처음 보는 수강생이라는 기준)

 

 나도 파이썬이 처음이라 기초 문법 부분에서 골머리를 상당히 썩었는데 이해가 안가는게 대체 왜 들여쓰기로 실행을 구분하는가와 변수의 타입이 너무 헷갈린다는 점이다. 제일 놀라웠던 점은 num : int; 로 선언한 변수에 소수 계산을 넣으니 바로 float 타입으로 바뀌어버리는,,, 진짜 아예 예상을 못한 부분이어서 디버깅 할 때 애먹었다. 형변환은 대체 왜 변수를 괄호로 감싸는지,, 형변환 할 때 (int) 이런 식으로 복붙하는게 편한데 int(num),,, ? 

퍼포먼스 적인 부분은 제하고도 그냥 언어적으로 완성이 덜 된 느낌 ? 그닥 효율적인지 모르겠는 언어이다. 입문을 아예 파이썬으로 했다면 모를까 다른 프로그래밍 언어를 접하고 사용하기엔 그닥,,, 인 언어같다. 특히 간단한 코드 작성이 아닌 소규라도 프로젝트 단위 에선 더더욱

 

 

-----------------------------------------------------------------------

교수님의 요구 조건은 아래와 같다.

 

m 진법의 수를 나타내는 문자열 str을 n 진법의 수를 나타내는 문자열로 변환하는 함수 convert_base(str, m, n, p)를 작성하는 과제이다. 마지막 파라메터 p는 최대 소수점 몇째 자리까지 계산할지 정해주는 용도이다. m과 n의 범위 즉 진법은 2진법부터 36진법까지로 하자. 36진법의 경우는 0부터 9까지 열 개의 digit과 A부터 Z까지 알파벳 26글자를 모두 활용하게 된다.

정수만을 변환하는 경우는 파이썬의 붙박이 함수 int를 활용하거나, int를 활용하지 않더라도 아니더라도 chatGPT에 물어보면 너무 쉽게 된다. 그래서 이 과제는 소수점이 있는 경우까지 포함하는 수를 진법 변환하는 내용이다. 물론 이것도 chatGPT에게 물어보면 또 작성을 못해주는 건 아니라 아래와 같은 구현상의 추가 제약조건을 따라 과제를 진행하기로 한다.

바로 유리수 계산을 통해서 하자는 것이다. 보통 chatGPT에게 그냥 물어보면 해주는 방식은 대략 정수 부분을 변환한 다음, 소수점 이하 부분은

• m진수 소수 형태의 문자열을 컴퓨터의 실수 표현(즉, 이진수)로 변환
• 컴퓨터의 실수 표현(즉, 이진수)를 n진수 소수 형태의 문자열로 변환

이렇게 컴퓨터의 이진수 실수 표현 단계를 중간에 거쳐간다.

이렇게 하는 게 사실 일반적으로 더 간편하고 빠른 방법이긴 하지만

• m진수에서 이진수 실수로 갈 때 오차 발생 가능
• 이진수에서 n진수 실수로 갈 때 오차 발생 가능

이렇게 오차가 두 번씩 발생하므로 m진법에서 n진법으로 한번에 변환하면 한번만 발생할 오차가 불필요하게 두 번 발생되며 오차가 누적될 가능성이 있다는 것이 단점이다. (특히, m과 n 모두 2가 아닌 서로 다른 소인수를 포함하는 경우)

그래서 좀 느리고 불편하지만 (그리고 일반적인 방법이 아니라 아무래도 chatGPT에게 물어보기도 더 까다롭고 ... 열심히 물어보면 뭐 대답할 수 있게 만들 수 있을지도 모르는데 뭐 그건 그거 나름대로 상당한 노력이라) 컴퓨터 이진수가 아닌 오차가 없는 유리수 표현(즉, 분수)과 연산을 통해 소수점 이하의 m진법에서 n진법 변환을 수행하는 것이 이번 과제의 핵심이다.

 

 

여기서 교수님께서 요구하신 질문을 내가 해석한대로 간단하게 요약한다면 

m -> 2진수 -> n진수로 변환하는 방식은 오차가 두번 발생하니

 유리수 표현(즉, 분수)과 연산을 통해 소수점 이하의 m진법에서 n진법 변환을 수행 

 

하라는 과제이다.

 

문제 1번 (5점+5점+10점 = 30점). 분수의 덧셈, 뺄셈, 나눗셈 함수 작성

import math # math.lcm, math.gcd 등등 활용을 위해 import

# 통분해서 계산하고 결과는 약분해서
def addFrac(q1, q2):
    lcm = math.lcm(q1[1],q2[1])
    numer = lcm // q1[1] * q1[0] + lcm // q2[1] * q2[0]
    return (numer // math.gcd(lcm,numer), lcm // math.gcd(lcm,numer))


# 통분해서 계산하고 결과는 약분해서
def subFrac(q1, q2):
    lcm = math.lcm(q1[1],q2[1])
    numer = lcm // q1[1] * q1[0] - lcm // q2[1] * q2[0]
    return (numer // math.gcd(lcm,numer), lcm // math.gcd(lcm,numer))

# q1을 q2로 나눈 몫(정수)과 나머지(유리수)를 순서쌍으로 리턴
# 나머지도 유리수이므로 마찬가지로 약분한 결과로
def divFrac(q1, q2):
  numer = q1[0] * q2[1]
  denom = q1[1] * q2[0]
  return (numer // math.gcd(numer,denom),denom // math.gcd(numer,denom))

파이썬이 처음이라 좀 조잡한 코드인데 대충 구현만 해봤다. 메인 코드가 아니기에 패스.

 

문제 2번 (10점). 0부터 9까지 글자와 A부터 Z까지 글자를 정수로 변환

2진법부터 36진법까지의 수를 표현하는 문자열에 나타나는 각 글자를 수치로 변환하는 데 활용할 아래의 digit2int 함수를 작성하라.

def digit2int(c):
    if not isinstance(c, str):
        return -1
    elif c.isdigit():
        return int(c)
    elif c.isalpha():
        if(len(c) > 1):
            return -1
        if ord(c.upper()) < 65 or ord(c.upper()) > 90: # 알파벳이 아닌 경우
            return -1
        else:
            return ord(c.upper()) - 55
    else:
        return -1

귀요미지만 파이썬 예외처리를 처음 해봐서 은근 오래걸렸다. 그리고 가끔 isalpha에 한글 들어가도 true 반환 하던데 딱히 이유를 알고싶지 않아서 패스

 

2.5번 : m진법 자연수(음이 아닌 정수)를 나타내는 문자열 str을 n진법 자연수를 나타내는 문자열로 변환하는 함수 convert_base_nat(str, m, n)을 작성하라.

정수에 대한 진법 변환은 오차가 없으므로 어떤 방식을 활용하든 크게 관계없다. 2진법에서 36진법까지 모두 작동하기만 하면 된다. 그러니까 붙박이 함수 int를 활용해도 좋다.

이 함수를 사용할 때는 우량한 형태의 str이 들어온다고 가정할 것이므로, 함수 몸체에서 str이 올바른 m진법 자연수의 형태의 문자열인지 따로 검사하는 validation은 하지 말라.

이 함수는 과제를 완성하기 위해서 필요하므로 반드시 작성해야 하지만 chatGPT에게 물어봐도 이정도는 간단히 해줄 것이이므로 이 부분을 완성하는 것에 대한 과제 점수는 없다.

 

def convert_base_nat(str_, m, n):
    result = 0
    for c in str_:
        result = result * m + digit2int(c)
    converted = ""
    while result > 0:
        digit = result % n
        converted = str(int2digit(digit)) + converted
        result = result // n
    return converted

 

 

문제 3번 (60점). convert_base(str, m, n, p) 함수 작성

m 진법의 수를 나타내는 문자열 str을 n 진법의 수를 나타내는 문자열로 변환하는 함수 convert_base(str, m, n, p)를 작성하라.

str이 우량한 형태인지, 즉 m진법의 정수 혹은 실수(소수점 하나 포함) 형태인지 검사하는 내용을 포함하라. 만일 불량한 입력이면 ValueError를 raise하라.

str이 정수 형태라면, 그냥 앞서 작성한 convert_base_nat을 호출하기만 하면 된다.

str이 소수점이 하나 포함횐 형태라면, 정수 부분은 convert_base_nat를 활용해 변환하고, 소수점 아래 부분을 분수 혹은 여러 개의 분수로 표현하여 중간에 2진법을 거치지 않고 직접 m진법에서 m진법으로 분수의 덧셈 뺄셈 나눗셈 등의 연산을 활용한 소수점 아래 자리들에 대한 진법 변환을 하라. 그리고 정수 부분이 변환된 문자열과 소수점 아래 자리들이 변환된 문자열을 가운데 '.'을 두고 이어붙여서 리턴하면 될 것이다.

마지막 파라메터 p는 최대 소수점 몇째 자리까지 계산할지 정해주는 용도이다. m과 n의 범위 즉 진법은 2진법부터 36진법까지로 하자. 36진법의 경우는 0부터 9까지 열 개의 digit과 A부터 Z까지 알파벳 26글자를 모두 활용하게 된다.

 

메인 문제인데 진법 변환을 하는 법을 4년전 쯤에 배웠던 지라 기억이 안나서 굉장히 애먹었다. 개념 잡고 전부 푸는데 4시간 가까이 걸린듯 하다...

 우선 내가 생각한 문제 풀이 방법이다.

결국 문제의 핵심은 유리수 표현(즉, 분수)과 연산을 통해 소수점 이하의 m진법에서 n진법 변환을 수행인데

 어떻게 유리수에서 진수의 변환을 하는가,,? 이것이 문제이다. 여기서 막혀서 금방 끝낼걸 질질 끌어버렸다..

 이 문제를 풀려면 우선적으로 소수의 진법 표현 방식부터 이해를 해야한다..

10진법 기준에서 소수의 표현은

0.123456789 이러한 형식으로 나타난다. 

2진법은 ? 

0.101010101

이런 형식으로 나타난다.

여기서 저 한자리 한자리가 의미하는 것이 뭔지 알아보자.

 

근본적으로 소수는 1에 수렴할 수는 있어도 1은 되지 못한다. 대부분의 컴퓨터에서 소수는 2진법으로 표현된다.

0.1(2진법)이 의미하는 것은 0.5(10)이다.

0.11(2)은 ? 0.75(10)이다. 

0.5(10) 이나 0.75(10)은 2진법에서 나누어 떨어지기 때문에 깔끔하게 표현이 가능하다.

그런데 0.99(10)과 같은 수는 ,,?

0.1111110101110000101... 이런 식으로 무한한 길이의 소수로 표현이 된다.

 

진법의 변환으로 10진법에서 표현이 가능한 소수가 2진법에선 무한소수로 표현이 되는 것이다.

이는 대부분의 컴퓨터에 소수 표현은 부동소수점 방식에서 생기는 문제점이기도 하다.

 

무튼 내가 생각한 방식은

1.변환할 소수를 전부 더해서 분수 표현방식으로 변경한다

m진수 0.99(10) 을 16진수로 변환할 때 

0.99을 분수로 바꾸면

9/10 + 9/100 = 99 / 100 이다.

여기서 알 수 있는것은 분모는 m^p (p는 소숫점 자릿수)으로 표현되고, 분자는 자릿수에 해당하는 수가 오는 것을 알 수 있다. 이런걸 잘 확인해놓으면 코드를 짤 때 수월하게 짤 수 있다.

 

2.현재 분모와 변환할 진수 n^p의 최소 공배수를 구한다.

 코드는 대부분 첫째 자리부터 변환을 수행함으로 현재 p값은 1이라고 가정한다.

현재 분모는 100이고, n은 16(16진수로 변환할 것이기 때문) p는 1이라고 가정했으니 

100과 16의 최소 공배수를 구한다. -> 400

 

3.분모와 분자에 최소 공배수 / 분모값을 곱해준다.

최소 공배수 / 분모는 = 400 / 100이다. 따라서 분모와 분자에 4를 곱해준다.

= 396 / 400

 

4.분자를 num / n^p로 나눈 몪을 구하고 이를 n진법으로 변환하여 결과 문자열에 추가한다.

n^p는 16이고 분모는 400이다. 

400 / 16이니 = 25 

이 값을 분자에 나눠준다. 396 / 25 = 15

15를 n진법으로 변환하면 F

결과 문자열에 += "F"를 해준다.

 

5.이를 구하고 싶은 자리수 까지 반복한다.(여기서 나머지가 0이라면 끝낸다.)

 

해보고 싶은 사람들은 수기로 직접 계산해 보길 바란다.

정답은 

0.FD70A3D70A3D70A3D70A

이다.

 

이제 이걸 코드로 써보자

 

메인 함수

#고려해야할 점
#1.2~36진법이 아닌경우
#소수, 혹은 정수 형태가 아닌경우 문자열의 모든 인덱스를 확인하고 알파벳도 아니고, 숫자도 아닐 경우 
#소수, 혹은 정수 형태이지만 소수와 정수를 구분하는 법(.의 유무)
def convert_base(str, m, n, p):
    if not (2 <= m <= 36 and 2 <= n <= 36):
        raise ValueError("m과 n은 2부터 36사이의 값이어야 합니.")
    # str이 소수 형태인지 검사
    pc = 0 # 소수점 개수를 저장할 변수
    for c in str:
        if c == '.': # 소수점일 경우
            pc += 1
            if pc > 1: # 소수점이 두 개 이상이면
                raise ValueError("잘못된 입력입니다.")
        elif not(c.isdigit() or (ord(c.upper())-55) < m): # 숫자도 아니고 알파벳도 아니면
            raise ValueError("잘못된 입력입니다.")
    
    if pc == 0: # 정수 형태인 경우
        return convert_base_nat(str, m, n)
    else: # 소수 형태인 경우
        tmpNum = str.split('.')
        int_part = convert_base_nat(tmpNum[0],m,n)
        if(int_part == ""): int_part = "0"
        fract_part = convert_fract_nat(tmpNum[1],m,n,p)
        if len(f"{fract_part}") > p: # p자리까지만 계산하도록 설정
            fract_part = round(fract_part, p)
        return int_part + "." + fract_part # 정수부와 소수부를 .으로 이어붙인 문자열 반환

서브 함수들

def convert_fract_nat(str, m, n,p):
    # num : 분자, den : 분모
    num, den = 1,1
    i = 1
    
    # 문자열을 반복문으로 돌며 분수 형태로 변환한다.
    for i, c in enumerate(str):
       num, den = addFrac((num, den), (digit2int(c), m ** (i + 1)))

    # 분수의 뺄셈을 이용하여 소수 부분을 계산한다.
    num -= den
    tmpStr = ""
    for i in range(1, p+1):
      #den과 변환할 진수 n ^ i 의 최소 공배수를 구하고 _lcm 에 담는다.
      _lcm = math.lcm(den, (n ** i))
      #2. 분수를 분모와 분자를 각각 _lcm과 den으로 곱한다.
      num *= _lcm // den
      den = _lcm
      #3. 분자를 num / n^i 로 나눈 몪을 구하고 이를 n진법으로 변환하여 결과 문자열에 추가한다.
      quotient = num // (den // (n ** i))
      tmpStr += int2digit(quotient)
      #4. 변환된 문자열로부터 분자를 계산하여 분모에서 뺀다.
      tup = subFrac((num,den), ((den // (n ** i)) * quotient, den)) #빼기 함수 사용. % 연산자 사용으로 대체 가능하긴 할거같다.
      num,den = tup[0],tup[1]
      if(num == 0):
        return tmpStr
    return tmpStr
    
    #필요해서 추가적으로 작성한 함수. 정수를 넣으면 그에 대응하는 문자열로도 바꿔준다. 0~9값이 들어올 경우 그대로 반환한다.
def int2digit(n):
    if not isinstance(n, int):
        return "잘못된 값 입력"
    elif n < 0 or n >= 36:
        return "잘못된 값 입력"
    elif n < 10:
        return str(n)
    else:
        return chr(n + 55)

ㄴ 사실 위의 함수가 거의 메인이다.

 

 

 

코드 테스트

#코드. 값 비교는 https://www.rapidtables.com/convert/number/base-converter.html 에서 했습니다.

#정수부는 의미가 없으므로 소수만 테스트
print(convert_base("1011.1011", 2, 10,20))#11.6875

print(convert_base("404.404", 5, 14,20))
#76.B91017D484063B4521B1 출력 값
#76.B91017D484063B4521B1 계산기 사이트 
print(convert_base("ZZ.ZZ",36,10,20) )
#1295.99922839506172839506 출력 값
#1295.99922839506172839506 계산기 사이트 
print(convert_base("91.91", 15, 36,20))
#3S.LRCYK5RCYK5RCYK5RCYK 출력 값 
#3S.LRCYK5RCYK5RC79LXKYT 계산기 사이트
#위의 수는 반복되는 소수인데 계산기 사이트보다 오히려 정확함을 보여줬습니다.

#----예외 처리
#print(convert_base("ZZ.1", 32, 10,3)) #해당 코드는 32진법에 ZZ를 넣었습니다.ValueError를 반환합니다.
#print(convert_base("#2!@.", 32, 10,3)) #말도 안되는 문자열 역시 .ValueError를 반환합니다.
#print(convert_base("#나나.나나", 32, 10,3)) #말도 안되는 문자열 역시 .ValueError를 반환합니다.

정상 작동.

 

 

 

 

 

 

 

 

 

+1번 코드를 사용해서 짜는것이 교수님이 좋아할것 같아 저런식으로 작성했지만 

def convert_fract_nat(str, m, n, p):
    num, den = 1, 1
    for i, c in enumerate(str):
        num, den = addFrac((num, den), (digit2int(c), m ** (i+1)))
    num -= den
    res_str = ""
    for i in range(1, p+1):
        lcm = math.lcm(den, n ** i)
        num *= lcm // den
        den = lcm
        res_str += int2digit(num // (den // n ** i))
        num %= den // n ** i
        if num == 0:
            break
    return res_str

다음과 같이 간략화 할 수도 있다.