개발일지

개념 탐색 범위를 반으로 줄이면서 값을 찾는 방법이다. 작동원리 1. 탐색 범위를 정렬한다. 2. l -> 탐색 범위 최소값, r -> 탐색 범위 최대값, m -> 탐색 범위 중간값 3. m에 찾으려는 위치가 있는지 확인한다. 4. m에 찾는 값보다 큰 값이 존재하면 r을 m - 1로 바꾼다. ( 정렬되어있기 때문에 m보다 큰 인덱스에 저장된 값은 m에 저장된 값보다 크기 때문에 확인할 필요가 없다.) 5. m에 찾는 값보다 작은 값이 존재하면 l을 m + 1로 바꾼다. (정렬되어있기 때문에 l보다 작은 인덱스에 저장된 값은 m에 저장된 값보다 작기 때문에 확인할 필요가 없다.) 6. l > n >> k; vector ve(n); for (auto &i : ve) { cin >> i; } long lon..

개념 그래프 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 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목..