아인스트라세의 SW 블로그

나눗셈

정수 두 개를 나누었을 때, 몫과 나머지를 구할 수 있다.

//( A/B = Q\space remainder \space R //)

이때 A는 피제수(dividend)라고 부른다.

B는 제수(divisor) 라고 부른다.

Q는 몫(quotient)라고 부른다.

R는 나머지(remainder)라고 부른다.

모듈러(Modulo) 연산

나머지 연산은 modulo라고 하며 mod라고 나타낸다.

//( 7\space mod\space 2 = 1 //) 이다. 왜냐면 7을 2로 나누면 몫이 3이고 나머지가 1이므로, 이 나머지 값이 모듈러 연산의 결과값이 된다.

그렇다면 //( -5\space mod\space 3 //) 과 같은 경우는 어떻게 될까?

이러한 경우는 모듈러 연산의 특징을 이용해서 값을 구할 수 있다.

모듈러 연산은 피연산자의 값을 주기로 같은 결과값을 갖는 주기성을 띤다. 따라서 다음과 같은 관계가 성립한다.

//( -5\space mod\space 3 = -2\space mod\space 3 = 1\space mod\space 3 = 4\space mod\space3 ...//)

즉 첫번째 피연산자에 두번째 피연산자의 정수배의 값을 더해도 같은 값이 나오는 것을 이용하여 문제를 해결할 수 있다.

다시말해 -5에 3이나 6이나 9 등의 //(3*K//)의 값을 더해도(단 //(K//)는 정수) 결과값은 같다는 것이다.

모듈러 합동(Congruence Modulo)

이제 모듈러 합동(Congruence Modulo)에 대해 알아보자.

다음과 같은 수식이 있다.

//(A \equiv B(modC)//)

이를 A는 모듈러 C에 대해서 B와 합동이다 라고 읽는다. (A is congruent to B modulo C)

이는 다르게 말하면, //( A\space mod\space C = B\space mod\space C //)라는 뜻이다.

위 수식이 성립한다면, 또한 //(A-B//)는 //(C//)의 정수배라고 볼 수 있다.

모듈러 역원(Modular inverse)

역원(inverse)

역원에 대해 한번 다시 알아보자. 어떤 수와 그 수의 역원을 곱하면 1이 된다.

숫자 //(A//)의 역원은 //(1/A//)이다, 왜냐면 //(A * 1/A = 1//)이기 때문이다.

0보다 큰 실수는 역원을 갖는다.

그리고 //(A//)의 역원과 곱셈을 하는 것은 //(A//)로 나누는 것과 같다.

모듈러 역원(Modular inverse)

모듈러 역원의 활용

프로그래밍을 할 때, //(A//)를 구하는 과정에서 //(A//)가 int나 long long 범위를 벗어나서, 온전한 //(A//)값을 구할 수 없고, //( A \mod C //) 값만 구할 수 있는 경우

위의 성질을 활용하면 간편하다.

//(A//)값과 //(B^{-1}//)를 각각 구해서 모듈러를 취한 뒤, 곱한 뒤 다시 모듈러를 취하면 되기 때문이다.

그러면 //(B^{-1}//)를 어떻게 구하느냐면, 페르마의 소정리를 이용하면 된다.

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

[참고]

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/e/congruence-relation

https://www.acmicpc.net/blog/view/29

블로그에 수학 수식을 입력하는 방법은 다양합니다. 간단하게는 다른 수학 수식을 그려주는 곳에서 (e.g 한컴오피스) 수식을 그린 뒤, 해당 수식을 캡쳐해서 이미지 형태로 올릴 수도 있고, 아니면 직접 수식 모양대로 svg등으로 한땀 한땀 그릴 수도 있습니다. 아니면 흔히 다른 사람들이 많이 쓰는 라이브러리인 MathJax 등을 사용할 수도 있습니다. 저는 이번에 KaTeX라고 하는 라이브러리를 이용해서 블로그에 수식을 입력해보도록 하겠습니다.

https://khan.github.io/KaTeX/

KaTeX의 공식 홈페이지입니다. MathJax 보다 랜더링 속도가 빠르다는 것을 강점으로 홍보하고 있습니다.

참고로 LaTeX는 TeX라고 하는 조판 프로그램을 쉽게 사용하기 위해 만든 매크로입니다. LaTeX라는 것을 이용해서 특정한 의미를 갖는 메타캐릭터들과 텍스트들을 조합해서 PDF나 다른 문서들을 만들어낼 수 있습니다. 그 LaTeX에서 사용하는 매크로 중에서 수식을 그리는 매크로도 있는데, 이 KaTeX는 LaTeX의 이름을 바꾸어서 네이밍을 한 것 같습니다.

LaTeX는 자바스크립트 API를 지원하며, 다양한 방식으로 수식을 입력할 수 있는데, 여기서는 자바스크립트 API를 최대한 호출하지 않도록 간단하게 입력할 수 있는 Auto-Render Extension을 이용하겠습니다.

티스토리 관리자 페이지에서 '스킨 편집' - 'html 편집'을 누릅니다. 그리고 </head> 바로 윗 부분에 아래와 같이 코드 스니펫을 입력해줍니다.

아래 사진에는 Auto-Render Extension을 위한 값을 입력하지 않고 기본 katex라이브러리만 불러오는 방식으로 되어있지만, Auto-Render Exntension을 위해서는 아래 코드스니펫을 복사 밑 붙여넣기 해 줍니다.

CDN을 사용하지 않고, js파일과 css파일을 직접 본인의 서버에 올려서 사용하려고 한다면, prism.js 적용하는 것과 유사하게 파일업로드 후 상대경로를 지정해주면 됩니다.

 

	<!-- KaTex Start -->
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.css" integrity="sha384-TEMocfGvRuD1rIAacqrknm5BQZ7W7uWitoih+jMNFXQIbNl16bO8OZmylH/Vi/Ei" crossorigin="anonymous">
<script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.js" integrity="sha384-jmxIlussZWB7qCuB+PgKG1uLjjxbVVIayPJwi6cG6Zb4YKq0JIw+OMnkkEC7kYCq" crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/contrib/auto-render.min.js" integrity="sha384-IiI65aU9ZYub2MY9zhtKd1H2ps7xxf+eb2YFG9lX6uRqpXCvBTOidPRCXCrQ++Uc" crossorigin="anonymous"></script>
<script>
	document.addEventListener("DOMContentLoaded", function() {
    renderMathInElement(document.body, {
			delimiters: [
				{left: "$$", right: "$$", display: true},
				{left: "//[", right: "//]", display: true},
				{left: "//(", right: "//)", display: false}
			]
		});
	});
</script>
	<!-- KaTex End -->

스니펫은 다음 링크에서도 확인할 수 있습니다.

https://github.com/Khan/KaTeX/blob/master/contrib/auto-render/README.md

그리고 테스트용 글을 한번 써 봅니다. 해당 API 문서를 참조해보면, 기본값으로 수식을 나타내는 구분자(delimiter)는 기본 설정 값으로 3개가 주어진다고 합니다.

$$ 수식 $$

\\[ 수식 \\]

\\( 수식 \\)

이러한 구분자의 값은 renderMathInElement 함수의 두번째 인자의 옵션에 설정하여 원하는 값으로 바꿀 수 있다고 합니다.

그리고 처음 첫번재 두번재 구분자는 display가 true값으로, 해당 구분자로 입력을 하면 해당 수식이 줄의 가운대 정렬이 되어서 displayMode로 크게 보여집니다. 하지만 마지막 구분자를 이용하면 displayMode가 false이므로 inline 모드로 입력이 되어 수식이 본문과 어우러지게 입력됩니다.

그리고 한글 자판을 사용하는 시스템에서 백슬래시 값을 입력하면 Won 기호로 인식되어서 두번째 세번째 구분자가 제대로 인식되지 않는 경우가 많습니다. 따라서 저 같은 경우에는 이 기본값의 구분자를 \ 대신 /으로 치환해서 사용합니다.

아래 그림은 $$ 구분자로 수식을 입력한 모습입니다.

원하는 수식으로 잘 랜더링 되었습니다.

$$A \equiv B(modC)$$

그리고 KaTeX에서 지원하는 구문들에 대한 레퍼런스 문서의 링크는 다음과 같습니다.

https://khan.github.io/KaTeX/function-support.html

KaTeX를 이용해서 구문을 작성할 시 참조하면 좋습니다.

백준저지 1013번 문제 Contact과 2671번 문제 잠수함 식별은 문제가 똑같다.

특정한 문자열 패턴에 일치하는지 확인하는 문제이다. 문자열 패턴이 정규표현식(Regular Expression) 형태이므로 DFA(Deterministic Finite Automata)를 그려서 O(n)에 문제를 해결할 수 있다.

주어진 패턴이 (100+1+|01)+인데, DFA를 바로 그리기에는 어려우므로 NFA(Non-deterministic Finite Automata)를 먼저 그린다. 이후 DFA로 변환해보도록 한다.

아래 그림은 NFA를 그린 것이다. Initial State는 a이고, Final State는 e, g이다.

이후 DFA로 변환하면 다음과 같다. 똑같이 Initial state는 a이고 Final State는 g, e, {b,e} 이다.

state를 빨간샛 숫자에 맞추어 번호를 부여한 뒤 구현하면 다음과 같은 코드가 나타난다.

1013번 Contact 문제 풀이 코드이다.

 

#include <bits/stdc++.h>
using namespace std;

#define FAIL 9
const int tr[10][2] = {
    {5, 1}, //0
    {2, FAIL}, //1
    {3, FAIL}, //2
    {3, 4}, //3
    {5, 7}, //4
    {FAIL, 6},//5
    {5, 1},//6
    {8, 7},//7
    {3, 6},//8
    {FAIL, FAIL}//9
};

bool chk(string &seq) {
    int state = 0;
    for (size_t i=0; i < seq.size(); i++) {
        char ch = seq[i] - '0';
        state = tr[state][ch];
    }
    return state == 4 or state == 6 or state == 7;
}
int main() {
    int t;
    cin >> t;
    while(t--) {
        string seq;
        cin >> seq;
        bool ans = chk(seq);
        cout << (ans ? "YES" : "NO") << '\n';
        
    }
	return 0;
}

잠수함 식별 문제도 거의 동일한 코드로 풀이가 가능하다. 하지만 2671번 잠수함 문제는 C++에서 제공하는 정규표현식 라이브러리를 이용해서 풀이해보겠다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    regex re("(100+1+|01)+");    
    cmatch m;
    string seq;
    cin >> seq;
    bool ans = regex_match(seq.c_str(), m, re);
    cout << (ans ? "SUBMARINE" : "NOISE") << '\n';

	return 0;
}

위와 같은 간단한 코드로 쉽게 정규표현식에 일치하는지 확인할 수 있다.

정규표현식이 정확한지는 다음 사이트에서 쉽게 태스트 해 볼 수 있다.

https://regexr.com/