가우스 소거법 (2) 썸네일형 리스트형 [Python] 32233번 토러스 게임 조작하기 https://www.acmicpc.net/problem/32233 24/09/12 오일러 지표 + 스프라그 그런디 + 가우스 소거법의 세 가지 태그가 잘 맞물리는 좋은 문제이다. 맷코컵 검수했을 때의 기억을 되살려서 꼼꼼하게 해설을 적어보고자 한다. 문제 접근 방식: 이 문제를 해결하기 위해서는 다음과 같은 세가지 지식을 알고 있어야 한다. 1. 오일러 지표에 대한 지식 2. 스프라그-그런디 정리에 대한 지식 3. 가우스 소거법, 특히, 2진법 위에서의 가우스 소거법에 대한 지식. 먼저, 하나의 토러스 또는 구 위에서 간선을 교차하지 않도록 잇는 게임을 하나의 님 게임으로 치환할 수 있다는 사실을 알아야 한다. 이는 스프라그-그런디 정리 관련 문제를 많이 푼 사람이라면 쉽게 파악할 수 있을 것이다.. [Python] 9066번 금고 https://www.acmicpc.net/problem/9066 9066번: 금고 어떤 금고가 N × N 개의 격자에 모두 한 개씩의 손잡이를 가지고 있다. 모든 손잡이는 수직(|), 또는 수평(-), 이 두 가지 상태밖에 없으며 이 손잡이를 돌려서 수직, 수평으로 만들 수 있다. 각 손 www.acmicpc.net 23/03/20 체감 상 플레티넘 5보다 어려웠다고 느껴졌던 문제이다. 나는 선형대수학적 지식을 이용하여 문제를 해결했다. 시간복잡도 상으로 더 짧게 걸리는 풀이도 있긴 하나, 결국 이 풀이 또한 내가 풀었던 방법과 본질적으로는 같은 방법으로, 이를 증명하기 위해서는 선형대수학적 지식이 수반되어야 한다. 때문에 이 글은 선형 대수학의 내용 중 '체'와 '벡터공간'에 대한 지식과, 연립 일차.. 이전 1 다음