8월 24일에 진행한 코드포스 894번 대회 일지입니다. 1600+에서 제대로 참여한 사람이 저밖에 없기도 하고, 잘한 건지는 모르겠는데 아무튼 버츄얼 퍼포는 블루입니다. ㅠㅠ 0:00~0:06 A번을 잡았습니다. 무슨 더러운 구현 문제였습니다. 3A 치고는 조금 오래 걸렸습니다. 0:06~0:10 B번을 잡았습니다. 전의 ...

2023년 8월 17일에 진행한 에듀케이셔널 코드포스 153번 대회 일지입니다. 0:00~0:05 A번을 잡았습니다. 괄호 문제열을 가지고 노는 문제였습니다. 주어지는 문자열이 ‘()’이면 불가능하다는 것은 자명히 생각했습니다. ((..()..))나 ()()..()() 둘 중 하나로 채우면 될 것 같았고, 구분 기준을 찾으려고 했습니...

8월 18일 진행한 한과영 알고리즘 연구회 오토마타 하계대회 참가 일지입니다. 이렇게 낼 문제가 많은 한과영 부럽습니다. 그동안 놀고먹는 우리 나코더 2학년은 뭐하는 걸까요? (약) 1:10~1:19 기숙사에서 귀가 이슈로 늦게 시작했습니다. 바로 A번을 잡았습니다. A번을 잡았습니다. 그냥 $10^9$를 분모로 갖는 분수를 출력하면 됩니다...

8월 12일에 진행한 코드포스 892번 대회 일지입니다. 결론적으로 다시 퍼플이 되긴 했습니다. 이 굴레에서 언제쯤 빠져나갈 수 있을까요? 0:00~0:04 A번 United We Stand을 잡았습니다. (가장 작은 수; 여러 개일 경우 모두)와 (나머지 수)로 나누면 됩니다. 나눌 수 없는 경우, 즉 (나머지 수)가 없는 경우 -1을...

Hackenbush Game: 그래프 위에서 진행되는 게임 중 아마 가장 복잡하면서도 연구가 많이 진행되어 있는 하켄부시 게임이라는 것에 대해 배우고, 그런디 수와 비슷하게 하켄부시 게임에서의 position을 수로 나타낼 수 있는지 알아보았다. 하켄부시라는 주제의 존재에 대해서는 잘 알고 있었는데, 하켄부시 게임이 아무래도 수학 ...

그래프를 응용해서 그래프 위에서 할 수 있는 게임 이론적인 몇몇 아이디어에 대해 배웠다. 조합론이나 게임 이론, 문제 해결 프로그래밍 쪽에는 어느 정도 잘 알려져 있는 Nim 게임과 ‘Sprague-Grundy Theorem’ 등에 대해 배우고 cutthroat 게임의 각 상태를 Grundy 수로 표현하여 어떤 플레이어가 게임에서 이기는지를 확인하는 ...

유향 그래프에 대해서 배웠다. 각 간선에 대해 방향성을 부여할 때 이러한 그래프를 유향 그래프라고 하며, 그 중에서도 유향 cycle이 없도록 무향 그래프의 간선에 방향을 부여해 유향 그래프를 만들 수 있다. 이때의 간선 방향 정보를 Acyclic orientation이라고 한다. 이때, 그래프 채색에 관한 경우의 수를 구하는 ch...

Graph coloring: Coloring of vertices with minimum colors where any adjacent vertices has a different color Chromatic number: Fewest colors needed to color a graph Independence number: Order of ...

Chordal graph: A graph where every cycle has a chord Interval graph: A graph where vertices are intervals and two vertices are adjacent if and only if the 2 intervals intersect Graph Decomposit...

Hamiltonian Path : Path where all vertex is passed exactly once Bipartite Graph : A graph is bipartite if the vertices are partitioned into 2 independent sets Complete bipartite graph : Bi...