나름 개발자의 IT블로그

DFA (Deterministic Finite Automata) 이제부터 전자계산기의 동작을 알아보도록 하자. DFA는 이름에서 알 수 있듯 "결정적인 유한 오토마타"이다. 상태는 유한하고 어떤 상태에서 어떤 입력이 들어오면 이동하는 상태가 정해져있다는 뜻이다. DFA 는 다음으로 이루어져있다. $ M = (Q, \Sigma, q, F, s)$ $Q$ : DFA상태들의 집합 $\Sigma$ : 입력받은 String $q$ : 초기상태 ($q \in Q$) $F$ : AC를 받는 상태들의 집합 ($F \in Q$, 여러개 가능) $s$ : Transition Function 표기법은 책, 자료마다 다르지만 의미는 같다. 지난시간에 본 Problem X1을 DFA로 나타내면 다음과 같다. 여기에서 각 노드(..

지난시간은 집합을 배우고 이젠 또 이상한걸 배우네요. 암호는 언제 배우죠? 암호랑 상관이 없어보이는 내용이 이어지는 것 같다. 하지만 이 모든 것들이 암호의 본질에 대해 필요한 내용들이니 알아보도록 하자. Language 튜링머신(컴퓨터)이 해결하는 문제를 나타낸다. 용어부터 정의하고 가자. Symbol : 단순 문자 (0,1,a,b,c, ...) String : 길이가 유한한 Symbol의 배열 (01010, ababc, 00a1b, ...) $\lambda$ : 길이가 0인 String Alphabet : 길이가 유한한 Symbol 집합이고 $\Sigma$로 나타낸다. ({0,1}, {a,b,c, ..., z}) Language : String들의 집합 ({$\lambda$, 0, 1, 01, 10,..

Lollang (롤랭) 롤랭 문법 https://github.com/riroan/lollang/wiki/lollang-Grammar GitHub - riroan/lollang: 롤 채팅으로 하는 프로그래밍 롤 채팅으로 하는 프로그래밍. Contribute to riroan/lollang development by creating an account on GitHub. github.com 롤랭 컴파일러 https://github.com/riroan/lollang GitHub - riroan/lollang: 롤 채팅으로 하는 프로그래밍 롤 채팅으로 하는 프로그래밍. Contribute to riroan/lollang development by creating an account on GitHub. githu..

Countable vs Uncountable 위 용어를 의미로 해석하면 "셀 수 있는"과 "셀 수 없는"이다. 셀 수 있다는 의미로 접근하면 Countable Set은 유한집합을 의미할 것 같다. 하지만 유한집합은 Finite Set이라는 용어가 있고 이는 Countable Set과 구분되고 심지어 위 두 용어는 모두 무한집합(Infinite Set)에서 정의한다. Countable Set은 자연수집합과 대응되는 집합이다. 자연수가 개수를 세는데 사용되니 이런 의미를 가지게 된 것 같다. 앞에서 보였듯이 $|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|$이므로 $\mathbb{N},\mathbb{Z},\mathbb{Q}$는 모두 Countable Set이 된다. 반면 $\mathbb..

원소의 개수를 세자 어떤 집합의 원소의 개수를 Cardinality라고 하고 기호는 $|A|$로 나타낸다. (앞으로 크기라고도 표현할 것이다.) Cardinality에 관해 두가지 성질이 있다. $|A| < |B| < |C|$ 이면 $|A| < |C|$이다. $|A| = |A|$이다. 당연해보이지만 일단 짚고 넘어가자. 유한집합에서 Cardinality는 그냥 원소의 개수를 세면 되기 때문에 생각하기 쉽다. 하지만 집합이 무한집합이라면 어떨까? 일반적으로 생각하기 힘들다. 자연수 집합 $\mathbb{N}$이 있다. $\mathbb{N}$는 무한함이 자명하다. 자연수에 0을 추가해 새로운 집합 $\mathbb{N}^+ = \mathbb{N} \cup \{0\} $을 정의하자. (범자연수 집합이 된다.) ..

갑자기 자연수? 수는 모든 학문의 기초가 되고 그 중 가장 생각하기 쉬운 자연수는 어디에든 나타나는 개념이다. 하지만 우리는 자연수란 무엇인가?라고 질문하면 쉽게 답하기 어렵다. 1,2,3같이 개수를 셀 수 있는 수 아닌가요? 위와 같은 답은 생각하긴 쉽지만 모호한 답이다. 자연수를 엄밀하게 정의하기 위해 보통 페아노 공리계를 말하곤 한다. https://namu.wiki/w/%EC%9E%90%EC%97%B0%EC%88%98#s-2.1 자연수 - 나무위키 이 다섯 가지 공리와 그리고 가장 간단한 형태의 덧셈, 곱셈, 그리고 대소 관계 정의를 이용하면 우리가 아는 자연수의 모든 성질들을 이끌어낼 수 있다. 자연수에서의 덧셈은 덧셈이 가지는 가 namu.wiki 수학도 그렇고 과학도 그렇고 이공계학문은 공리..

이번에 건국대학교 교내 알고리즘 대회 KUPC를 개최하게 되었다. 뭐든지 대회를 참여만 해서 개최하고 운영하는건 처음이었는데 좋은 경험을 얻은 것 같다. 운영을 하면서 배운 것과 느낀점, 뒷이야기 등이 많아 기록해두려고 한다. 이번 운영진은 UCPC팀원과 ICPC팀원의 합집합으로 구성되어있다. riroan, aru0504, kth990303, delena0702 개최하게 된 이유 UCPC가 끝나고 알고리즘 문제에 대한 아이디어가 마구마구 샘솟아서 어딘가에 문제를 출제하고 싶었다. 하지만 백준에 출제하려면 적어도 2000문제를 풀어야했는데 아마 몇백문제 남아있었던 것 같다. 그렇게 찾다가 나온 사이트가 누구나 출제할 수 있는 삼성 SW Expert. (문제는 여기) 위에 냈는데 더 많은 사람이 봤으면 하는..

Complexity Theory 세계로... Complexity Theory(계산복잡도 이론)은 암호학에 필요한 이론이라고 한다. 우리가 알고리즘때 사용하는 Big-O표기법도 Complexity Theory에서 나왔다. (알고리즘도 여기에 포함된다고 한다.) 즉 Complexity Theory란 튜링머신(컴퓨터)이 어떤 연산을 하는데 얼마나 걸리는지를 분석하는 컴퓨터 과학 분야이다. 미리 알아둬야할 컨셉이 있다. 어떤 문제가 어렵다는 것은 해당 문제를 해결하는 시간이 오래 걸린다는 뜻이다. 사실 "오래 걸린다"도 추상적이긴 하지만 "어렵다"도 마찬가지이니 의미만 이해하고 넘어가자. Halting Problem 어떤 프로그램과 인풋이 주어졌을 때 해당 프로그램이 정지하는 지(끝나는 지) 판정하시오. Hal..

암호란 무엇인가요? 위 그림은 암호를 설명하는 가장 기본적인 그림이라고 한다. 과정 Alice가 Bob에게 메시지 M을 보내려고 한다. M을 암호화하여 C로 만들어 Bob에게 전송한다. Bob은 C를 M으로 복원하여 메시지를 확인한다. 그 과정중 Eve라는 어떤 사람이 암호문 C를 가로챌 수 있다. (위/변조는 지금 생각하지 말자.) Eve가 C를 가로채더라도 M으로 복원할 수 없어야 한다. 즉, 우리의 목표는 Bob은 C $\rightarrow$ M을 할 수 있어야하고 Eve는 C $\rightarrow$ M을 할 수 없어야한다. 사람 이름을 A, B, E라고 쓰기보다 Alice, Bob으로 사용하여 재미(?)있게 표현한다고 한다. (한국으로 치면 철수와 영희) 여기서 Eve는 Evasesdropper..

Introduce. 암호학은 현재 수강하고 있는 전공과목이다. 마지막 학기이지만 전공이 3학점이 남아 암호학과 정보보안중 하나를 선택해 들으려고 했는데 정보보안수업이 졸업프로젝트와 겹쳐서 암호학을 선택하게 되었다.. 학기가 거의 끝나가는 지금 굉장한 만족감을 가지고 수강하고 있다. (매 수업마다 감탄하며 듣는다.) 그래서 블로그에 쓸지말지를 오랜기간 고민하다가 너무 좋은 내용이 많아서 리마인드하는 느낌으로 기록해놓으려고 한다. Chapter. 아마 챕터는 다음과 같을 것이다. Chapter 1. Complexity Theory (with Computation Theory) Chapter 2. Number Theory (블로그에 적어둔 포스팅 재사용 예정) Chapter 3. Cryptography Sys..