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

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

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

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

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 ...

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 Decompo...

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 :...

key: jekyll-text-theme title: MMSS 3일차 (7/25 Tue) excerpt: 쌩그래프이론 vs 그래프자료구조 tags: [travel, mmss] key: 230726 — Null graph: No vertices Complement of a graph : Same vertex as the original gr...

2일차입니다. 본격적으로 수업을 시작했습니다. 수업 Graph(그래프) : A set of elements called vertices(꼭짓점, 노드), along with a set of pairs of vertices called edges(간선). Two vertices are adjacent(인접하다, 이웃하다) if there is an...

Michigan Math & Science Scholars Program 참가를 위해, 처음으로 미국에 왔습니다. 2주간 총 8일동안 Graph Theory 수업을 듣게 되어서, 수업 내용도 정리하고 여행 블로그도 써보고 싶어서 여기에 둘 다 하기로 했습니다. 수업 내용은 제가 꼴리는 대로 쓸 거라 영어일 수도 있습니다. 아무튼, 그 1일차의 ...