-
General Matching and applications
General Matching and applications 유량(flow) 관련 알고리즘을 공부했다면 이분 그래프의 최대 매칭에 대해서는 익숙할 것이다. 이분 그래프에서 최대 매칭을 구하는 것은 크게 두 가지 의미에서 중요하다. 첫 번째는 문제 그 자체 에 대한 관심이다. 예를 들어, 택시 애플리케이션이 승객과 기사를 매칭하는 방법이나 결혼 중개업체가 남자와 여자를 짝짓는 방법 모두 이분 그래프의 매칭으로 표현할 수 있다. 두 번째는 이 문제가 다른 문제를 푸는데 어떻게 응용 될 수 있는지이다. 예를 들어, Konig’s theorem을 사용하면 이분 그래프의 최대...
-
Bixby Studio
Bixby Studio Contents 빅스비 스튜디오란? 내가 만든 예제 발전 방향 참고 빅스비 스튜디오란? 우선 빅스비는 삼성전자에서 개발된 음성인식 기반 개인 비서 어플리케이션으로 현재 스마트폰 외에도 여러가지 기기(대부분의 삼성 디바이스)에서 사용되고 있다. 보통 빅스비는 현재 삼성 페이와 연결되어 쇼핑으로 자주 활용된다. 빅스비는 어떤 발화가 주어지면, 그 발화를 해결할 수 있는 캡슐을 검색하게 된다. 예를들어 어떤 장소에 대해 질문을 하는 발화가 주어졌다면, 장소를 찾는 캡슐을 검색하고 그 캡슐안으로 이동해서, 여러 지정된 액션들을 수행하게 된다. 예전에 빅스비가 나왔던...
-
UCPC 2020 출제 후기
국내에서 가장 불꽃 튀는 알고리즘 대회 중 하나인 UCPC 2020 예선이 지난 7월 25일에, 본선이 8월 1일에 진행되었습니다. 저는 예선의 E번 감자 농장, H번 사과나무 그리고 본선의 G번 그건 망고가 아니라 고양이예요를 출제할 기회를 얻었습니다. 이 포스팅에서는 UCPC에서 문제를 제출한 순간부터 대회가 끝날 때까지 문제 개발이 어떻게 이루어졌는지를 다루어보고자 합니다. 테스트 케이스 제작에 초점을 두지만, 일반적인 검수 과정에 있어서도 길라잡이가 될 수 있으리라 생각합니다. 제가 만든 문제들을 해부하듯이 설명하기 때문에, 풀이도 서술되어 있음에 유의해주시길 바랍니다....
-
Constructive 문제를 어떻게 풀 것인가
Constructive 문제를 어떻게 풀 것인가 들어가며 알고리즘 대회에서 Constructive Algorithm(구성적 알고리즘)은, 말뜻 그대로 답을 증명할 수 있는 실제 예시를 구성하는 것이다. 이 용어는 수학의 Constructive Proof(구성적 증명, 존재성의 증명 등에서 귀류법이나 귀납법을 쓰지 않고 직접 조건을 만족하는 예시를 만들어 증명하는 방법)에서 왔다고 할 수 있다. Constructive 문제에서 구성해야 하는 대상은 대개 Sequence나 Graph이다. 무에서 유를 창조해내야 하는 문제의 특성상, 많은 배경 지식을 필요로 하기도 하며, 특정 문제에서의 테크닉을 일반화하기 어렵다는 Ad-hoc의 특징도 가지고 있다. 그렇다고...
-
Lucas–Lehmer primality test
안녕하세요? 오늘은 $2^p - 1$꼴의 수(메르센 수)에 대해 소수 여부를 빠르게 판정할 수 있는 Lucas–Lehmer primality test에 대해 설명해보고자 합니다. 일반적인 소수 판정법은 시간이 굉장히 오래 소요됩니다. 가장 자명한 방법으로는 해당 숫자의 제곱근 이하의 소수들로 모두 나누어보는 방법이 있지만, 수가 어느 정도 커지면 사용하기 힘들어지게 됩니다. 더 큰 수에 대해 사용할 수 있는 알고리즘으로는 밀러-라빈 소수판정법이 있는데, 비결정론적인, 즉 확률에 의존한다는 단점이 있습니다. 하지만 특정 형태의 수에 대해서는, 굉장히 큰 숫자여도 해당 숫자가 소수인지를 결정론적으로...