반응형

이번에는 request 에 대해서 알아보겠습니다.

 

먼저 HTTP 요청 방식은 GET, POST, PUT, PATCH, DELETE 등이 있습니다.

이것은 하나의 convention 으로, 클라이언트에서 요청할 때 method 를 지정하며, 서버쪽에서는 method 에 맞게 response 를 구현해 주면 됩니다.

 

curl 을 이용해서 테스트를 해 보겠습니다. 

 

참고로 -X 옵션을 따로 지정하지 않으면 GET method 로 요청을 합니다. 

 

GET 방식으로 요청

> curl -X GET http://localhost:5000

 

GET 요청에 대한 리턴

<p>Hello World</p>

 

 

POST 방식으로 요청

> curl -X POST http://localhost:5000

 

같은 url 을 요청했는데, POST 방식에서는 다음과 같이 리턴이 왔습니다.

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<title>405 Method Not Allowed</title>
<h1>Method Not Allowed</h1>
<p>The method is not allowed for the requested URL.</p>

 

내용을 살펴보면 해당 method 를 지원하지 않는다고 합니다.

이슈를 해결하기 위해서 이전에 작성한 app.py 코드를 다음과 같이 수정해 봅니다.

from flask import Flask

app = Flask(__name__)

@app.route("/test")
def path_test():
    return '<p>test</p>'

@app.route("/", methods=['GET', 'POST'])
def hello_world():
    return '<p>Hello World</p>'

 

"/" 경로에 method 를 추가해 준 것입니다.

변경 후 재 실행 하면 POST 요청에 대한 리턴도 GET 과 같은 것을 확인 할 수 있습니다.

 

 

이번에는 method 에 따라 다른 결과를 보내주는 코드를 작성해 보겠습니다.

요청을 구분하기 위해서는 request.method 사용합니다. 

 

먼저 request 를 import 해주고, 아래처럼 분기하면 요청 method 에 따라 다른 결과가 리턴 됩니다.

from flask import Flask, request

app = Flask(__name__)

@app.route("/test")
def path_test():
    return '<p>test</p>'

@app.route("/", methods=['GET', 'POST'])
def hello_world():
    if request.method == 'GET':
        return '<p>GET: Hello World</p>'
    elif request.method == 'POST':
        return '<p>POST: Hello World</p>'

 

반응형
반응형

지난번 포스트에서는 기본적인 서비스를 시작해 보았습니다.

이번 포스팅부터는 윈도우 환경에서 실행되며, 포트는 default인 5000번을 사용한다고 가정하고 진행하겠습니다.

 

이번에는 경로를 추가해 보겠습니다.

 

app.py 파일을 열어서 아래와 같이 편집합니다.

from flask import Flask

app = Flask(__name__)

@app.route("/test")
def r_test():
    return '<p>test</p>'
    
@app.route("/")
def hello_world():
    return '<p>Hello World</p>'

 

flask 앱을 다시 실행하고, 웹브라우저에 다음과 같이 입력합니다.

 

http://localhost:5000/test

 

그러면 화면에 test라고 나옵니다.

 

 

flask 앱에 test 라는 경로가 추가되었습니다.

 

따라서 원하는 경로를 추가하려면, @app.route 에 경로를 지정하고, 바로 method 를 구현해 주면됩니다.

여기서 method 이름은 크게 중요하진 않지만, 다른 method 이름과 중복되지 않게 적어 주셔야 합니다.

 

만약 같은 경로를 중복해서 지정하면 어떻게 될까요?

 

아래와 같이, 같은 경로(/test)에 여러 개의 method를 구현하면, 제일 처음에 나오는 r_test()가 실행됩니다.

from flask import Flask

app = Flask(__name__)

@app.route("/test")
def r_test():
    return '<p>test</p>'

@app.route("/test")
def r_test2():
    return '<p>test2</p>'

@app.route("/")
def hello_world():
    return '<p>Hello World</p>'

 

반응형
반응형

Python Flask를 이용해서 REST 서비스를 구현해 보겠습니다.

 

먼저 Python 3.x가 설치되어 있다고 가정하고 진행해 보겠습니다.

 

Python 의 가상환경을 이용할 예정이며, 테스트 환경은 Windows 10 이지만, OS 의 영향이 거의 없을 듯 합니다.

 

Python 의 가상환경은 가상으로 isolated 된 실행 환경을 생성해 주며, 각 환경 별로 다른 모듈을 설치하여 실행할 수 있게 해줍니다.

 

 

프로젝트 실행 위치를 myApp 폴더라고 가정하겠습니다.

 

명령프롬프트를 사용해서 해당 위치로 이동후에 아래 명령어로 가상환경을 생성합니다.

 

> python3 -m venv venv

마지막의 venv는 가상환경이 생성되는 경로이기 때문에 원하시는 폴더로 변경해서 지정할 수 있습니다.

 

 

가상환경을 실행합니다. (윈도우)

> venv\Scripts\activate

맥OS나 리눅스에서는 다음과 같이 실행합니다.

$ source venv/bin/activate

 

참고로 가상환경을 종료할 때는 deactivate 명령어를 입력하면 됩니다.

 

 

실행후에는 명령프롬프트 앞쪽에 가상환경에 대한 정보가 나타납니다.

(venv) >

 

Flask 모듈을 설치합니다.

(venv) > pip3 install flask

 

 

간단한 Flask 앱을 만들어 보겠습니다.

 

먼저 app.py 파일을 생성해서 편집기로 열고 다음과 같이 입력합니다.

from flask import Flask

app = Flask(__name__)

@app.route("/")
def hello_world():
    return '<p>Hello World</p>'

 

그리고 가상환경의 명령프롬프트에서 다음과 같이 입력합니다. (윈도우)

> set FLASK_APP=app
> flask run

 

맥OS나 리눅스라면 다음과 같이 입력합니다.

$ export FLASK_APP=app
$ flask run

 

실행시키면 어떤 포트에서 실행 중인지에 대한 정보가 화면에 나타납니다.  참고로 default 는 5000포트인데, 맥에서는 AirPlay Receiver 서비스가 해당 포트를 사용중이기 때문에, 서비스를 중지시키거나 다른 포트를 사용해야 합니다.

 

Monterey 에서 서비스 중지시키는 방법:

System Preferences > Sharing > AirPlay Receiver 체크 해제

 

포트 지정은 -p 옵션을 사용합니다.

$ flask run -p 4999

 

웹 브라우저를 열어 아래 주소를 입력해서 결과를 확인해 봅니다.

 

http://localhost:5000 

 

브라우저에 Hello World 라고 나오면 성공입니다.

 

 

 

 

 

반응형
반응형

이번에는 LIS 에 대해서 알아보겠습니다.

 

LIS는 원소가 증가하는 순서대로 배치 했을 때, 가장 긴 배열의 길이를 구하는 문제입니다.

 

예를 들어 [1, 5, 2, 3, 10] 이라는 배열이 있다면,

 

증가 순서대로 배치 했을 때, 가장 길게 나오는 경우는 [1, 2, 3, 10]이 되므로, 이 경우의 답은 4가 됩니다.

 

 

기본적인 접근법은, 자신보다 작은 수의 원소를 카운트할 수 있는 버퍼(dp)를 생성하고, 중첩루프를 돌며 자신보다 작은 수의 원소에 대해서 현재 카운트와 작은 수의 원소의 카운트 + 1을 비교해서 큰 값을 취하고, 최종결과에서 최대값을 리턴하면 됩니다.

 

위의 예시에 대해서 과정을 살펴보면,

 

먼저 자기 자신은 모두 1로 세팅합니다.

[1, 1, 1, 1, 1]

 

1에 대해서 나머지 모든 원소들이 1보다 크기 때문에 dp[i] (= 1) 과 dp[0] + 1 (= 2)를  비교해서 더 큰 값인 2를 취합니다.

[1, 2, 2, 2, 2]

 

5에 대해서 같은 방법을 적용하면, 5보다 큰 10에 대해서만 dp[1] + 1 (= 3) 으로 바뀝니다.

[1, 2, 2, 2, 3]

 

2에 대해서 같은 방법을 적용하면, 10의 경우 이미 3이었는데, dp[2] + 1 (= 3) 이기 때문에 변화가 없습니다.

[1, 2, 2, 3, 3]

 

3에 대해서 같은 방법을 적용하면,

[1, 2, 2, 3, 4]

 

dp 의 최대 값은 4이기 때문에, 가장 긴 증가 순서의 길이는 4가 됨을 알 수 있습니다.

 

위의 알고리즘을 코드로 구현하면 다음과 같습니다.

def lengthOfLIS(nums):
    arrLen = len(nums)
    dp = [1] * arrLen
    ret = 0
    for i in range(arrLen):
        for j in range(i+1, arrLen):
            if (nums[i] < nums[j]):     
                dp[j] = max(dp[j], dp[i] + 1)
                if (dp[j] > ret):
                    ret = dp[j]
    return ret

이 경우 시간 복잡도는 O(n^2) 이 됩니다.

 

 

조금 더 효율적인 방법으로는 배열을 순회하며, 값이 증가하는 경우에는 그대로 값을 추가해주고, 값이 감소하면 그 값을 기존에 찾아둔 배열에서 해당 값보다 큰 수들 중에 가장 작은 값의 위치에 대입해주면서 추가된 개수를 리턴하면 됩니다.

 

위의 예시에 대해서 과정을 살펴보면,

 

배열의 첫번째 원소를 추가합니다.

[1]

 

다음 원소를 체크해 보면, 이전에 추가한 원소(1) 보다 크기 때문에 증가 순서에 추가 합니다.

[1, 5]

 

다음 원소는 2 인데, 2는 이전에 추가한 원소(5) 보다 작기 때문에, 리스트에 추가하지 않고, 기존 리스트에서 2보다 큰 수들 중에서 가장 작은 값(5)를 2로 대체합니다.

[1,2]

 

다음 부터 나오는 숫자들 (3, 10) 은 순서대로 증가하기 때문에 하나씩 추가해 주면 됩니다.

[1,2,3]
[1,2,3,10]

 

최종적으로 총 4번 추가했기 때문에, 길이는 4가 됩니다.

 

이 알고리즘은 길이를 구하기 위해서 최적화 된 알고리즘 이기 때문에, 배열에 들어가 있는 값은 실제 순서와는 다를 수 있습니다.

 

예를 들어, [1, 5, 6, 7, 8, 2, 3, 4] 라는 배열로 적용해 보면, 최종 수행 결과는 [1, 2, 3, 4, 8]가 되는데, 실제로 가장 긴 배열은 [1, 5, 6, 7, 8] 이기 때문입니다. 

 

위의 알고리즘을 코드로 구현하면 다음과 같습니다.

def lengthOfLIS(nums):
    arrLen = len(nums)
    dp = [nums[0]]
    dpLen = 1
    for i in range(1, arrLen):
        if (dp[-1] == nums[i]):
            pass
        elif (dp[-1] == nums[i]):
            dp.append(nums[i])
            dpLen += 1
        else:
            l = 0
            r = dpLen - 1
            while(l < r):
                mid = l + (r - l) // 2
                if (dp[mid] < nums[i]):
                    l = mid + 1
                else:
                    r = mid
            dp[l] = nums[i]
    return dpLen

 

이 알고리즘의 시간 복잡도는 O(n log n) 이 됩니다.

 

 

마지막으로 LIS의 길이가 아닌, 해당 원소들을 찾는 방법에 대해서 살펴보면, 기존 코드에서 dp에 값 대신 해당 원소의 인덱스를 저장하고, 값이 추가될 때, 해당 원소의 바로 앞이 어떤 값인지를 저장하는 버퍼(prevIdx)를 추가해서 처리하면 됩니다.

def lengthOfLISEx(nums):
    arrLen = len(nums)
    prevIdx = [-1] * arrLen
    dp = [0]
    dpLen = 1
    for i in range(1, arrLen):
        if (nums[dp[-1]] == nums[i]):
            pass
        elif (dp[-1] < nums[i]):
            prevIdx[i] = dp[dpLen - 1]
            dp.append(i)
            dpLen += 1
        else:
            l = 0
            r = dpLen - 1
            while(l < r):
                mid = l + (r - l) // 2
                if (nums[dp[mid]] < nums[i]):
                    l = mid + 1
                else:
                    r = mid
            prevIdx[i] = dp[l - 1]
            dp[l] = i

    currIdx = dp[-1]
    ans = [nums[currIdx]]
    while prevIdx[currIdx] != -1:
        ans.append(nums[prevIdx[currIdx]])
        currIdx = prevIdx[currIdx]
    return ans[::-1]

 

반응형
반응형

프로젝트 Jupyter는 오픈 소스 소프트웨어, 개방형 표준, 그리고 여러개의 프로그래밍 언어에 걸친 인터랙티브 컴퓨팅을 위한 서비스 개발을 위해서 설립된 비영리 단체입니다. 현재 Jupyter Notebook , Jupyter Hub, Jupyter Lab을 개발, 지원하고 있습니다.

 

https://jupyter.org/

 

Project Jupyter

The Jupyter Notebook is a web-based interactive computing platform. The notebook combines live code, equations, narrative text, visualizations, interactive dashboards and other media.

jupyter.org

 

M1 Mac에서 Jupyter를 실행하기 위해서는 몇 가지 프로그램 설치가 필요합니다.

 

먼저 Brew 를 설치합니다.

https://brew.sh/

 

Homebrew

The Missing Package Manager for macOS (or Linux).

brew.sh

 

 설치는 Terminal 에서 아래 명령어를 입력하면 됩니다.

/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"

 

설치 이후에는, 다음의 명령어로 업데이트를 해줍니다.

brew update && brew doctor

 

그리고 python 버전을 관리해주는 pyenv를 설치합니다.

brew install pyenv

 

pyenv를 이용해서 python 3.9.x 를 설치합니다. (2021.11월 기준 3.9.7이 pyenv에서 지원하는 최신 버전이네요..) 아래 명령을 이용하면 pyenv에서 지원하는 3.9.x 중에서 가장 최신 버전을 설치 할 수 있습니다.

pyenv install --list | grep 3.9 | grep -v miniconda | tail -1 | xargs pyenv install

 

아니면 아래 명령어로 원하는 버전을 지정해서 설치하면 됩니다.

pyenv install 3.9.7

 

설치가 끝나면 다음 명령으로 환경변수에 pyenv path를 초기화 해주는 명령어를 추가해 줍니다.

echo 'eval "$(pyenv init --path)"' >> ~/.zprofile

 

pyenv 에서 사용할 python 버전을 설정합니다. (여기서는 3.9.7을 선택)

pyenv global 3.9.7

 

다음은 pip3를 이용해서 jupyter를 설치합니다.

pip3 install jupyter

 

아래 명령으로 jupyter notebook을 실행합니다.

jupyter notebook

 

기본 세팅은 8888 포트로 서비스 됩니다. 브라우저를 열고 http://localhost:8888 을 입력하면 jupyter notebook 을 사용할 수 있습니다.

 

혹시 포트를 변경하고 싶다면 아래처럼 --port 옵션으로 원하는 포트 번호를 지정합니다.

jupyter-notebook --port=5000

 

jupyter를 실행하면 브라우저가 자동으로 열리는데, 그걸 막으려면 아래와 같이 입력합니다.

jupyter notebook --no-browser

 

다음 명령으로 비밀번호를 설정할 수 있습니다.

jupyter notebook password

 

참고로 터미널이 열려 있는 것이 싫다면 아래 명령어를 이용하면 됩니다.

nohup jupyter notebook --no-browser >/dev/null 2>&1 &

 

나중에 주피터 프로세스를 종료할 때는 아래 명령어를 이용합니다.

ps | grep jupyter | grep -v grep | awk {'print $1'} | xargs kill -9

 

 

참고자료

 

pyenv 설치시 다음과 같은 에러가 나오면, brew를 리셋해 줍니다.

No available formula with the name "pyenv".

 

리셋 방법은 다음 명령어를 입력하면 됩니다.

brew update-reset

 

커널 스톱 이슈

M1 Mac에서 Jupyter 실행시 커널이 멈추는 이슈가 발생하는 경우 아래의 방법으로 조치가 가능합니다.

 

George Hotz의 유튜브 영상에서 해결하는 과정을 볼 수 있습니다.

https://www.youtube.com/watch?v=mwmke957ki4&feature=youtu.be&t=2740 

 

먼저 문제를 일으키는 eventloops.py 스크립트를 검색합니다.

find / -name eventloops.py

 

저는 아래 위치에서 해당 코드를 찾았습니다. 위치는 다를 수 있으며, 비슷하게 나오면 아래 [USER NAME] 부분만 사용자 이름으로 변경하면 될 거 같습니다.

vi /System/Volumes/Data/Users/[USER NAME]/.pyenv/versions/3.9.7/lib/python3.9/site-packages/ipykernel/eventloops.py

 

코드에서 아래 부분을 수정해 줍니다.  return 부분에 조건을 하나 추가합니다.

 

변경 전

def _use_appnope():
    """Should we use appnope for dealing with OS X app nap?

    Checks if we are on OS X 10.9 or greater.
    """
    return sys.platform == 'darwin' and V(platform.mac_ver()[0]) >= V('10.9')

 

변경 후

def _use_appnope():
    """Should we use appnope for dealing with OS X app nap?

    Checks if we are on OS X 10.9 or greater.
    """
    return sys.platform == 'darwin' and V(platform.mac_ver()[0]) >= V('10.9') and platform.mac_ver()[2] != 'arm64'

 

 

 

반응형
반응형

소괄호만 사용되었다는 가정하에 가장 긴 완성된 괄호를 세는 문제 입니다.

 

먼저 스택을 사용하는 방법입니다.

스택에는 지금까지 읽은 열린 괄호의 위치를 저장하며, 추가로 이전까지 완성된 소괄호 정보도 필요합니다.

def longestValidParentheses(s):
    strLen = len(s)
    dp = [0] * (strLen + 1)
    stack = []
    ans = 0
    for i in range(strLen):
        c = s[i]
        if (c == '('):
            stack.append(i)
        else:
            if len(stack) > 0:
                pos = stack.pop()
                cnt = i - pos + 1
                if pos > 0:
                    cnt += dp[pos - 1]
                if (cnt > ans):
                    ans = cnt
                dp[i] = cnt
    return ans

이 방법은 루프를 한번 돌면서 처리가 된다는 장점이 있지만, 이전 값을 저장하는 dp와 괄호의 시작을 stack에 담아두어야 하기 때문에 메모리 공간을 많이 차지합니다.

 

이를 개선한 방법은 다음과 같습니다.

루프를 돌며, 열린 괄호와 닫힌 괄호의 수를 카운트 합니다. 

왼쪽에서 오른쪽으로 진행할 때는 닫힌 괄호의 수가 더 많으면 모든 괄호의 카운트를 0으로 두고 새로 카운트 합니다.

열린 괄호와 닫힌 괄호의 수가 같으면 완성된 괄호의 숫자가 나옵니다.

여기서 문제는 처음에 열린 괄호가 더 많이 나와서 닫힌 괄호 수와 일치 하지 않고 끝나면 완성된 괄호의 수가 0으로 됩니다.

따라서 문제를 해결하기 위해서 반대방향으로 한번 더 진행합니다.

이번에는 열린 괄호가 더 많으면 모든 괄호의 카운트를 0으로 두고 새로 카운트 합니다.

두 번째 루프에서는 처음에 닫힌 괄호가 더 많이 나오는 경우 카운트가 되지 않지만, 첫 번째 루프에서 이미 카운트가 되었기 때문에 두 번의 결과의 최대값을 선택하면 됩니다.

def longestValidParentheses(s):
    max = 0
    l, r = 0, 0
    for c in s:
        if c == '(':
            l += 1
        else:
            r += 1
        if (r > l):
            l, r = 0, 0
        elif (r == l and r > max):
            max = r
            
    for c in s[::-1]:
        if c == '(':
            l += 1
        else:
            r += 1
        if (r < l):
            l, r = 0, 0
        elif (r == l and l > max):
            max = l

    return max * 2

 

변수를 추가하면 루프 한번으로 처리도 가능합니다.

def longestValidParentheses(s):
    max = 0
    l1, r1, l2, r2 = 0, 0, 0, 0
    strLen = len(s)
    for i in range(strLen):
        if s[i] == '(':
            l1 += 1
        else:
            r1 += 1
        if (r1 > l1):
            l1, r1 = 0, 0
        elif (r1 == l1 and l1 > max):
            max = r1
        
        if s[strLen - 1 - i] == '(':
            l2 += 1
        else:
            r2 += 1
        if (r2 < l2):
            l2, r2 = 0, 0
        elif (r2 == l2 and l2 > max):
            max = l2
    return max * 2

 

반응형
반응형

배열 혹은 리스트 등에서 과반수가 넘는 원소를 찾는 알고리즘입니다.

 

 

가장 기본적인 접근법은 각 원소별로 리스트를 모두 체크해서 해당 원소가 나오는 숫자를 세고, 과반수가 넘는지 체크하는 방법이 있습니다.

def find(nums):
    minCnt = len(nums) // 2
    for num in nums:
        cnt = sum(1 for elem in nums if elem == num)
        if cnt > minCnt:
            return num

 

시간 복잡도는 O(n^2) 이며, 공간 복잡도는 O(1) 입니다.

 

 

수행시간을 줄이기 위해서는 Dictionary 를 사용하는 방법이 있습니다.

def find(nums):
    dict = collections.Counter(nums)
    return max(dict.keys(), key=dict.get)

시간 복잡도는 O(n) 이며, 공간 복잡도는 O(n) 입니다.

 

 

그리고 데이터를 정렬해서 가운데 있는 원소를 뽑아내는 방법도 있습니다.

과반수 이상 존재하는 원소는 정렬시 반드시 중간 인덱스에 존재하기 때문입니다.

def find(nums):
    nums.sort()
    return nums[len(nums)//2]

이 경우 시간 복잡도는 O(n log n) 이며, 공간 복잡도는 O(1) 입니다.

 

그 외에 분할정복 방법으로도 찾을 수가 있습니다.

분할정복은 분할을 통해서 선택된 양쪽의 값이 같은 경우 해당 값을 선택하고,

다를 경우 분할된 셋에 각각 선택된 값의 숫자를 카운트하여 많은 쪽을 택하면 됩니다.

이 경우 시간 복잡도는 O(n log n) 이며, 공간 복잡도는 O(log n) 입니다.

 

마지막으로 Boyer-Moore 과반수 투표 알고리즘을 소개합니다.

알고리즘은 다음과 같습니다.

가장 많이 나올 후보 원소를 선택하고,

원소들을 순회하며 후보와 같은 값일 경우 카운트를 올리고,

다른 값일 경우 카운트를 차감합니다. 

카운트가 0이 되면 새로 후보를 선택하고, 순회하며 카운트를 반복합니다.

과반수가 넘는 원소는 카운트가 0보다 크거나, 최종적으로 선택되게 됩니다.

def find(nums):
    cnt = 0
    candidate = None
    
    for num in nums:
        if cnt == 0:
            candidate = num
        cnt += (1 if num == candidate else -1)

    return candidate

시간 복잡도는 O(n) 이며, 공간 복잡도는 O(1) 입니다.

반응형
반응형

모듈로 연산에서 역수는 다음과 같습니다.

 

두 정수 a와 m 에 대해서, a의 m에 대한 모듈러 역수 x는 a에 x를 곱해서 m으로 나눈 나머지가 1이 되는 값을 찾으면 됩니다. 이 때 x는 m보다 작은 양의 정수 입니다.

 a * x ~= 1 (mod m)

x는 a와 m이 서로 소인 경우 반드시 존재합니다.

 

예를 들어, a = 3, m = 11 이라면, x는 4가 됩니다.

(3 * 4) % 11 = 1

 

위의 예제에서 x = 4라는 값을 찾기 위해서는 x 에 순차적으로 1부터 대입해 보면 구할 수 있지만, 시간이 많이 걸리기 때문에 다음의 방법으로 더 효율적으로 구할 수 있습니다. 

 

개선을 위해서 a와 m이 서로 소인 경우, 유클리드 호제법을 이용한 방법을 소개합니다.

 

정수 a와 b가 주어졌을 때, 각각 x, y를 곱해서 최대공약수와 x, y를 찾습니다.

a * x + b * y = gcd(a, b)

 

a의 m에 대한 모듈러 역수를 찾기 위해서, b를 m이라 놓고, a와 m은 서로 소이기 때문에 최대공약수를 1로 설정합니다.

a * x + m * y = 1

 

양변을 m으로 나눈 나머지를 취하면,

a * x + m * y ~= 1 (mod m)
a * x ~= 1 (mod m)

 

x는 a의 m에 대한 모듈러 역수가 됩니다.

 

유클리드 호제법을 이용하여 모듈러 역수를 구하는 것을 python으로 구현한 코드는 다음과 같습니다.

def modInverse(a, m):
    m0 = m
    y = 0
    x = 1
    
    if (m == 1):
        return 0
    
    while (a > 1):
        q = a // m
        
        t = m
        
        m = a % m
        a = t
        t = y
        
        y = x - q * y
        x = t
        
    if (x < 0):
        x = x + m0
    
    return x

 

만약 m이 소수라면, 페르마의 소정리를 이용할 수 도 있습니다.

a ^ (m-1) ~= 1 (mod m)
a ^ (-1) ~= a ^ (m-2) (mod m)

페르마의 소정리 양변에 a ^ (-1) 을 곱하고, 좌변과 우변을 바꾸면, 우리가 찾는 모듈러 역수는 a ^ (m-2) 를 m으로 나눈 나머지가 됩니다.

 

기존에 사용했던 gcd 코드를 재활용해서 구현한 python 코드 입니다.

def modInverse(a, m):
    g = gdc(a, m)
    if (g != 1):
        # Inverse doesn't exist
        return -1
    else:
        return pow(a, m - 2, m)

def gcd(x, y):   
    while(y): 
        x, y = y, x % y   
    return x

 

정리를 해보면, a와 m이 서로 소이고, m이 소수라면 페르마의 소정리를 이용해서, 아래식으로 구하는 것이 가장 효율적이고,

a ^ (m-2) % m

 

m이 소수는 아니지만, a와 m이 서로 소라면 유클리드 호제법을 이용

반응형

+ Recent posts