-
Shortest Even Length Cycle in Digraphs
Introduction 문제 해결을 하다 보면 종종 몇 가지 조건들을 더하고 빼며 문제를 확장시키거나, 더 포괄적인 문제를 해결합니다. 지난 글 에서는 추상화를 통해 문제를 확장하는 일련의 과정을 느낄 수 있었습니다. 이번에는 반대로 원하는 답에 몇 가지 추가적인 조건을 덧붙여 구체화된 문제를 어떻게 해결하는지 들여다보도록 합시다. “단순 무방향 그래프 $G$에 사이클이 존재하느냐?” 라는 기초적인 질문에서 출발합니다. DFS를 이용하여 해결할 수 있는 문제죠. 이 문제만 해도 몇 가지 방향으로 확장할 수 있습니다. 최소 길이: “$G$에 길이가 $k$ 이하인...
-
IOI 2022
IOI 2022 IOI 2022 대회가 종료되었다. 올해 대회의 개최지는 인도네시아에서 진행하며, 온라인 대회 역시 병행한다. 한국 팀은 온라인 참가를 결정하였기 때문에, 현재 서울에서 모여서 감독 하에 대회를 진행하고 있다. 이 글에서는 해당 대회에 출제된 문제들을 하나 하나 풀어보고, 그 풀이를 소개한다. IOI에는 다양한 문제가 나오기 때문에 모든 풀이를 하나의 주제로 요약할 수는 없다. 고로 각 풀이의 핵심 키워드를 아래에 정리하였다. 구현한 풀이는 모두 https://github.com/koosaga/olympiad/tree/master/IOI 에서 찾을 수 있다. 문제 풀이 한 줄 요약 fish: 문제...
-
PBFT Consensus Algorithm
합의 알고리즘 합의 알고리즘이란, 즉 몇 개의 노드로 이루어진 네트워크가 있을 때, 이들을 합의에 이르게 할 수 있는 알고리즘을 말한다. 이는 블록체인이 세상에 등장하기 전부터도 분산 컴퓨팅 시스템에 대해 연구되었던 주제이지만, 블록체인이라는 개념의 등장과 함께 새로운 국면을 맞이하기 시작한다. 실제로 블록체인 또한 잘 정의된 연산을 실행한 결과가 무엇인지에 대한 의견을 모으는 과정의 반복이다. 의견을 제출하는 모든 컴퓨터(노드)가 충분히 빠른 시간 안에 올바른 결과를 내는 것이 이상적이지만, 현실에서는 그렇지 않기 때문에 합의 프로토콜이 필요하다. 프로토콜을 평가하는...
-
MLIR 소개
들어가기 전에 MLIR, 즉 Multi-Level Intermediate Representation은 하드웨어에 따른 연산들을 지원하는, 중간 언어(Intermediate Representation)에 대한 library라고 보면 됩니다. 아마 꽤 생소할 것 같습니다. 이 글에서는 MLIR에 대한 배경, 구성 요소 등에 대해 간단히 소개하고자 합니다. BackGround 본격적으로 MLIR에 대해 설명을 하기 전에, 이 글을 이해하는 데 있어서 알고 있으면 편한 개념들에 대해서 먼저 설명하도록 하겠습니다. IR 위에서도 언급한 IR은 Intermidate Representation의 약자로, 중간언어 집합을 말합니다. 어떤 source code가 있다고 할 때, compiler는 그것을 target machine에...
-
알고리즘 문제 접근 과정 10
알고리즘 문제 접근 과정 10 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. Musical Notes - USACO December 2009 Contest Silver 2번 문제가 영어로 되어있어서, 동일한 문제 상황의 번역을 첨부하겠습니다. 문제 카이홀에서는 한창 카이스트 합창 동아리 ‘코러스’의 콘서트가 진행되고 있다. 이번 콘서트에는 총 N개의 곡이 1번부터...