본문 바로가기
2019 ICPC 한국 리저널 인터넷예선 풀이 Note: 아직 미 완성인 글입니다. 20.06.03: A, B, C, D, F, H, I, J, L 풀이 수록 문제는 다음 사이트에서 일부 해결해볼 수 있다: 링크 A. All You Need is Dating $i$번째 IC 학생이 원하는 데이트의 최소 횟수를 $minIC_i$, 최대 횟수를 $maxIC_i$로 표기하자. 비슷하게 $minPC_j$와 $maxPC_j$를 정의하자. 그러면, 이 문제는 아래와 같이 간선을 지나가는 유량의 최소 제한과 최대 제한이 있는 플로우 그래프로 모델링 가능하다. 이는 전형적인 LR-flow 문제로, 해결법이 널리 알려져 있다. 일반적인 네트워크 플로우 알고리즘을 사용하여 해결하는 방법과 MCMF를 활용하는 방법이 있는데, 이 글에서는 생략한다. B. Balanced..
정규식으로 어떤 문자열이 회문인지 판별할 수 없는 이유 회사 인터뷰 등에서 정규식을 이용해서 주어진 문자열(편의상 알파벳과 숫자로만 이루어져 있다고 하자)이 회문인지 판별하는 프로그램을 작성하시오 와 같은 질문을 (오토마타나 계산이론 수업을 제대로 들었는지 확인하기 위해) 가끔 물어본다고 한다. 그런데 사실은 불가능하다. 이 글에서는 왜 불가능한지를 설명한다. 정규식을 이용하여 회문인지 판별하는게 가능하다고 가정하자. 그러면 정규식에서 accept하는 문자열은 accept하고, reject하는 문자열은 reject하는 유한 상태 기계, 즉 정규식에 대응되는 유한 상태 기계가 존재한다. $\{1^n 0 1^n \}$에 속하는 $0$, $101$, $11011$, $1110111$, ... 등의 문자열을 고려하자. 이 문자열들은 회문이므로 유한 상태 기계가 ac..
나의 zsh 및 Vim 세팅 내가 사용하는 Mac(들)에다 하는 세팅.. 어딘가 기록해두고 싶어 기록해둔다. 1) oh-my-zsh 등 설치 brew install wget vim zsh tmux git clone https://github.com/VundleVim/Vundle.vim.git ~/.vim/bundle/Vundle.vim cp .vimrc ~/ vim +PluginInstall +qall sh -c "$(wget https://raw.githubusercontent.com/robbyrussell/oh-my-zsh/master/tools/install.sh -O -)" git clone https://github.com/zdharma/fast-syntax-highlighting.git ~/.oh-my-zsh/custom..

티스토리툴바