-
Hello, Regex!
정규 표현식이란? 정규 표현식(Regular Expression, Regex)는 일정한 규칙을 가진 문자열의 집합을 표현하는데 사용합니다. 정규 표현식은 문자열의 검색과 치환을 위해 종종 쓰입니다. 프로그래밍 코드나 그 산출물에서 규칙이 드러나는 문자열은 무궁무진합니다. 날짜, 도메인 주소 형식, 이메일 형식, 수많은 유틸리티의 출력 형식이 대표적인 예이며, 그 외에도 두 글자 이상의 공백 등 규칙이 있는 문자열을 처리해야 할 때가 있습니다. 정규 표현식을 이용하면 이들을 보다 편하게 탐색하고 감지할 수 있습니다. 정규 표현식은 특히 Perl에서 그 확장성이 뛰어나며, 그외 수많은 언어들과...
-
Impartial Games
목차 $Impartial$ $game$ $Nim$ $game$ $Grundy$ $number$ 1. Impartial game $Impratial$ $game$ 이란 직역하면 공정한 게임이란 의미로, 게임 내에서 모든 플레이어가 동일한 조건으로 게임을 하는 것을 의미하는데, 이와 반대로 동일한 조건이 아닌 게임을 하는 것을 $Partisan$ $game$이라고 합니다. $Impartial$ $game$ 의 예로 우리가 흔히하는 베스킨라빈스 31이라는 게임이 있는데, 이 게임은 모든 플레이어가 동일하게 현재 숫자에서 1 ~ 3 사이의 수만큼 증가시키고 31이 될 경우 지게되는 게임이다. 이러한 $Impartial$ $game$에서 두 명의 플레이어가 있을 때 서로...
-
Mo's Algorithm
개요 Mo’s algorithm은 평방 분할 (sqrt decomposition)의 일종의 활용 기법으로, 오프라인으로 구간 쿼리 문제를 해결할 때 사용할 수 있습니다. 어떤 구간에 대한 정보를 빠르게 얻기 어려워 그 구간에 속한 $O(N)$개의 원소를 매번 모두 확인해야 하는 경우, $Q$개의 쿼리를 나이브하게 처리하려면 $O(QN)$의 시간이 소요될 것을 $O((N+Q)sqrt(N))$ 시간에 해결할 수 있게 해주는 마법의(?) 알고리즘입니다. 평방 분할 (sqrt decomposition) 우선 평방 분할에 대해 간단하게 소개하겠습니다. 평방 분할은 길이 $N$인 전체 구간을 $\sqrt N$개의 같은 크기의 블록으로 쪼개는 기법입니다....
-
랜덤 올바르게 사용하기
서론 프로그램을 작성할 때 랜덤한 요소는 많이 들어갑니다. 어떤 공간을 탐색할 때 무작위로 탐색을 하기도 하고, 프로그램의 비밀 키를 만들거나 게임을 만들 때 카드 덱을 섞을 때 등, 랜덤이 프로그램에 사용되는 곳은 굉장히 많습니다. 하지만 이 랜덤은 자주 잘못 사용되고는 합니다. 랜덤을 올바르게 사용하는 방법에 대해 알아보려고 합니다. 랜덤이란? 랜덤이란 특정한 패턴이 없다는 것을 말합니다. 즉, 어떤 규칙에 의해 생성되지 않고 다른 변수와 독립적으로 만들어진 결과를 랜덤한 결과라고 합니다. 과연 완벽한 좋은 랜덤을 만들 수...
-
현대 암호 1 : 블록 암호
저번 포스팅에서는 고전 암호를 다루었습니다. 이번 포스팅에서는 현대 암호 중에서도 DES, AES와 같은 블록 암호를 다루도록 하겠습니다. 블록 암호란? 블록 암호(Block Cipher)란 평문을 블록 단위로 암호화하는 대칭키 암호 시스템입니다. 대칭키 암호 시스템은 암호화와 복호화를 할 때 동일한 키가 사용되는 암호 시스템입니다. 반대로 암호화와 복호화를 할 때 동일하지 않은 키가 사용되지 않는 공개키 암호 시스템도 존재하는데, 공개키 암호 시스템 보다는 대칭키 암호 시스템이 우리의 직관과 조금 더 맞는 시스템일 것입니다. 참고로 저번 포스팅에서 다룬 고전 암호는...