본문 바로가기

CSE

 (15)
2022 ICPC Seoul Regional 본선 후기 Links Problem Scoreboard 대회 후기 예선 때와 마찬가지로 정말 준비를 못하고 대회를 쳤다. 고작 대회 직전에 팀 연습 2번이 다였다. 작년보다 더 잘하고 싶은 마음은 있었지만 사실 힘들다는 것은 어느 정도 알고 있었다. 그래도 정말 운이 좋게 작년과 같은 상인 동상을 수상할 수 있었고, 충분히 만족한다. 스코어보드는 아래와 같고 간단히 문제를 복기해보려 한다. ------------------------------------------------------------- I: 쉬운 문제였고, 우리 팀이 제일 먼저 푼 문제이다. (12 min.) J: Tree의 Euler Tour가 주어져 있을 때, leaf node들의 깊이의 합을 출력하는 문제인데, 역시 쉬운 문제였지만 long lo..
2022 ICPC Seoul Regional 예선 후기 Links Problem Scoreboard 대회 후기 작년 ICPC 이후, 우리 팀은 내년에는 좀 더 잘해보자 라는 마인드로 1년을 다시 준비했다. 그런데 대회 시즌이 됐을 때, 다들 각자 바빠서 대회 준비를 잘하지 못했다. 비록 UCPC에서 수상을 하긴 했지만 서울대 쿼터를 뚫기는 정말 쉽지 않기 때문에 전날까지도 긴장을 했다. 대회 중에도 계속 걱정을 했는데 정말 다행히도 운 좋게 턱걸이로 교내 6등을 하며 본선에 진출했다. 대회가 끝나고도 계속 바빠서 후기 작성을 못했는데, 본선 전에는 복기를 하고 싶어 간단히라도 남긴다. 아래는 스코어보드이다. 우선, 올해 대회 문제 셋은 너무 평이했다. 9솔이면 9솔, 8솔이면 8솔, 모든 팀들이 푼 문제가 다 똑같다. 그 말은 문제들의 난이도 배열이 너무나 ..
SNUPC 2022 (Div. 1) 후기 Links Problem Scoreboard Solutions 대회 후기 SNUPC는 서울대학교 교내 PS 대회로, 상당한 실력자들이 많이 등장하는 대회이다. 그렇기에 2020년부터 참여했지만 한 번도 수상권에 들지 못했다. 작년엔 호기롭게 Div. 1에 도전했다가 보기 좋게 망했다. 그래서 올해 대회를 신청할 때는 Div. 2로 나가볼까 생각도 했었는데, 그래도 "가오가 있지" 하면서 다시 도전했다. 결론은 아래 스코어보드대로 15등을 했고, 15등까지 수상권이어서 운 좋게 턱걸이로 5등상을 받을 수 있었다. 대회에 참여한 지 시간이 꽤나 흘렀지만 더 늦어지면 대회 때의 기억이 사라질 것 같아 간략히 후기를 적어보려 한다. (각 문제의 정확한 풀이가 궁금하다면 맨 위 링크를 참조바란다.) 대회 당일, ..
[Automata Theory] DFA = NFA DFA = NFA 우선, DFA가 만들 수 있는 언어는 모두 NFA로도 만들 수 있다. 이는 정의에 의해 자명하다. 그렇다면 여기서 당연히 NFA가 만들 수 있는 언어는 모두 DFA로도 만들 수 있는지에 대한 궁금증이 생긴다. 결론부터 말하면 맞다. 이를 증명하기 전에, 앞서 보았던 NFA 하나를 DFA로 바꿔보자. 위 NFA를 $M$이라고 하면 $M=(\{q_0, q_1, q_2\}, \{0, 1\}, \Delta, q_0, \{q_2\})$이다. $\Delta$의 함숫값을 구하면 $\Delta^*(q_0, 0) = \{q_0\}$ $\Delta^*(q_0, 1) = E(\Delta(q_0, 1)) = \{q_0, q_1, q_2\}$ $\Delta^*(q_1, 0) = \Delta^*(q_1, 1) ..
Type System of TypeScript What is TypeScript? TypeScript는 JavaScript에 타입 추론 기능을 추가한 언어로, MS에서 개발되었고 많은 분야에서 사용되고 있다. 기존의 JavaScript언어는 타입을 엄격하게 관리하지 않아 타입 관련 이슈들이 많았다 (프로그래머가 실수로 잘못 작성한 코드가 멀쩡히 실행되는 경우가 많아 디버깅이 어렵다). 이를 해결하기 위해 'typeof'함수를 이용해 방어적으로 프로그래밍을 해야 했는데, 코드가 굉장히 길어진다는 단점이 있었다. 그래서 이를 해결하고자 TypeScript가 등장했고, JavaScript의 모든 기능을 수행할 수 있으면서 TypeSystem을 도입해 compile time에 타입을 추론해 예상치 못한 에러를 잡아냈다. Soundness 모든 언어에는 각자..
[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\}$이다. 모..

티스토리툴바