그래프를 응용해서 그래프 위에서 할 수 있는 게임 이론적인 몇몇 아이디어에 대해 배웠다. 조합론이나 게임 이론, 문제 해결 프로그래밍 쪽에는 어느 정도 잘 알려져 있는 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...

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

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일차의 ...

7월 19일에 진행한 선린인터넷고 제 7회 천하제일 코딩대회 오픈 대회의 일지입니다. 8문제를 풀었습니다. 사실 한시간 좀 넘게 풀고 놀러 갔습니다. 0:00~0:01 A번 10!을 잡았습니다. 수학이었습니다. 57초 걸렸습니다. 3등이었던 것으로 기억합니다. 0:01~0:06 B번 고양이 카페를 잡았습니다. 덱을 만들...

2023년 7월 15일에 진행한 한국정보올림피아드 고등부 2차대회 일지입니다. 잘 본 것 같기는 한데 뭔가 아쉬운 느낌은 항상 드는 것 같습니다. 0:00~0:05 고1번 스케이트 연습을 잡았습니다. 작년 고1번이 P5였는데 의외로 쉬운 문제가 나와서 당황했습니다. 저는 S4를 기여했습니다. 입부시험 때 냈던 보디빌딩 문제와 비슷하다 생...