개발일지

개념 그래프 G에서 정접들의 집합을 S라고 할 때 S의 부분 집합 'S를 골랐을 때 서로 인접하지 않으면 독립 집합이라 하고 이중에서 'S의 크기가 가장 큰 독립집합을 최대 독립집합이라고 한다. Maximum Independent Set의 특징은 Maximum Independent Set의 여집합은 Minimum Vertex Cover이다. => 최대 집합 - Minimum Vertex Cover = 최대 독립 집합 => 최대 집합 - 최대 이분 매칭 = 최대 독립 집합이다 시간복잡도 이분매칭 할 때 : O(V^(1/2) * E) 문제 11014 컨닝2 www.acmicpc.net/problem/11014 11014번: 컨닝 2 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목..