본문 바로가기

분류 전체보기

(20)
[Automata Theory] Nondeterministic Finite Automata What is Nondeterministic Finite Automata? 비결정 유한 오토마타(Nondeterministic Finite Automata, 일명 NFA)는 DFA의 확장 버전이다. 결정과 비결정이 말하는 것은 상태인데, DFA는 특정 상태에서 특정 알파벳을 읽었을 때 다음 상태가 '결정'되는 반면, NFA는 다음 상태가 하나 이상일 수도 있고, 알파벳을 읽지 않고도 상태가 전이될 수 있다 ($\epsilon$에 의한 전이). 이제 NFA 역시 엄밀하게 정의해보자. Definition NFA $M$은 5가지의 구성 요소가 있어 $\boldsymbol{M=(Q, \Sigma, \Delta, q_0, F)}$이다. 이때 각 요소들은 $Q$ : 상태 집합 (유한집합) $\Sigma$ : 알파벳..
[Automata Theory] Deterministic Finite Automata What is Deterministic Finite Automata? 결정 유한 오토마타(Deterministic Finite Automata, 일명 DFA)는 가장 간단한 버전의 컴퓨터라고 할 수 있다. 비록 메모리가 없어 값들을 기억하진 못하지만 기계 내부에 상태가 있고, 값을 읽을 수 있으며, 상태 또한 전이가 가능하다. 실제 이런 기계는 존재하지는 않지만 존재한다면 아래의 그림과 비슷할 것이다. 기계는 테이프에 적혀있는 알파벳을 읽게 되는데, 가장 왼쪽부터 읽어가며 한칸씩 오른쪽으로 움직인다. 동시에 기계의 상태는 계속 바뀐다. 실제 컴퓨터도 instruction을 차례로 읽으면서 수행하고, 내부의 상태(register, memory, etc.)를 바꿔간다는 것을 생각해볼 때, 정말 컴퓨터와 비슷..
[Automata Theory] Regular Expression What is Regular Expression? 정규식(Regular Expression, 일명 Regex)은 웹개발을 해보았거나 코딩을 어느정도 해보았다면 익숙한 개념일 것이다. 이번에는 가장 기초적인 정규식을 정의해보고, 이로 인해 만들어지는 정규언어에 대해 알아보자. 엄밀히, 정규식은 언어를 식으로 표현하는 방법이다. $\Sigma$상의 정규식 $r$이 표현하는 언어를 $L(r)$이라고 하면 정규식은 다음과 같이 귀납적(inductive)하게 정의할 수 있다. $\boldsymbol{\phi}$는 정규식이고 $L(\boldsymbol{\phi})=\phi$이다. $\boldsymbol{\epsilon}$은 정규식이고, $L(\boldsymbol{\epsilon})=\{\epsilon\}$이다. 모..
[Automata Theory] Language 언어(Language)라는 개념은 우리에게도 굉장히 친숙한 개념이다. 늘 사용하는 것이 언어이고 이 글도 언어의 한 종류인 한국어와 영어로 쓰여진 무언가 이다. 그렇다면 언어의 정의는 무엇일까? 우선, 언어를 정의하기 위해서는 '알파벳'과 '스트링'이라는 것이 필요하기에 이들을 먼저 알아보자. 1. 알파벳 $\Sigma$는 문자들의 Finite Set이다. 예를 들어, 영어의 경우 $\Sigma=\{a, b,\cdots,z\}$이고, 이진수의 경우 $\Sigma=\{0,1\}$이다. 2. 스트링은 알파벳 $\Sigma$에 속해있는 문자들의 유한한 나열이다. 예를 들어, "abcd"는 $\Sigma=\{a, b,\cdots,z\}$상의 스트링이다. 3. $\Sigma$상의 모든 스트링의 집합은 $\Sigm..
[Automata Theory] Introduction What is Automata? 오토마타는 그리스어 'αὐτόματα'에서 유래한 말로 한국어로 번역하면 "자동 기계"라는 뜻을 가지고 있다. 정확히는 오토마타는 복수형이고, 단수형은 오토마톤(Automaton)이다. 이 자동 기계는 상태를 가지고 있고, 입력을 받을 수 있고, 특정 규칙에 따라 작동하며 메모리를 가질 수도 있다. 무언가 현재의 컴퓨터와 유사한 부분이 많다는 생각이 들지 않는가? 정확하다. 오토마타는 이론적으로 추상화된 컴퓨터라고 할 수 있다. (사실 컴퓨터가 오토마타 이론에서부터 출발한 것이므로 오토마타를 구현한 것이 컴퓨터라고 해야 맞다.) Why Automata Theory? 오토마타 이론(Automata Theory)은 말 그대로 오토마타와 그로부터 유도되는 문제 등을 연구하는 학..
Regex Quantifier 사용시 주의할 점 보통 문자열이나 HTML 코드 등을 파싱 할 때 Regex(Regular Expression, 정규표현식)를 많이 사용한다. Regex를 이용하면 모든 문자열을 효율적으로 표현할 수 있기에 잘 다루면 큰 도움이 된다. 이런 Regex에는 Quantifier라는 수를 표현할 수 있는 문법이 있는데, 주로 다음을 일컫는다. ? : 0번 또는 1번 * : 0번 이상 + : 1번 이상 {N,} : N번 이상 {N,M} : N번 이상 M번 이하 예를 들어, a+은 a가 1번 이상 반복되는 'a', 'aa', 'aaa' 등을 말한다. 이때 주의해야 할 Quantifier는 제일 마지막에 있는 {N,M}이다. 바로 띄어쓰기를 조심해야 하는데, {N, M}과 {N,M}은 엄연히 다른 것으로 후자가 Quantifier의..
새로고침이 안된다면? 웹 개발을 할 때 분명 코드를 바꿨고 새로고침도 했는데도 반영이 안 될 때가 있다. 그럴 때는 우선 컴파일이 잘 되었는지, 코드를 저장했는지 먼저 확인해보자. 그런데도 반영이 안 된다면 Ctrl+Shift+R을 눌러보자. 해결이 될 것이다.
BOJ 19585. 전설 문제링크 이 문제는 solved.ac Class 6++을 따기 위해 푼 문제였는데, 상당히 나를 귀찮게 했다. 그리고 맞고도 무언가 찝찝해 나와 같은 어려움을 겪고 있는 분들께 도움이 되고자 풀이를 작성해본다. Problem 더보기 $C(1\leq C \leq 4000)$개의 색깔을 나타내는 문자열과 $N(1\leq N \leq 4000)$개의 닉네임을 나타내는 문자열이 주어져있다. 이때 $Q(1 \leq Q \leq 20000)$개의 문자열에 대해 해당 문자열이 색깔 문자열 + 닉네임 문자열 꼴인지 판별하는 문제이다. 색깔, 닉네임 문자열의 길이 : 1000 이하, 판별 문자열의 길이: 2000 이하 Discussion 문제를 읽고 처음 든 생각은 "참 제한이 애매하다"였다. 제한시간이 3초이긴 하지만..