binary search 썸네일형 리스트형 BOJ)1626 두 번째로 작은 스패닝 트리 문제: icpc.me/1626 두 번째로 작은 스패닝 트리를 구하는 문제이다. 우선 정점이 V개 간선이 E개인 그래프에서 MST를 구해준다. 그리고 MST를 구성할 때 사용하지 않은 E-V+1개의 간선에 대해서 해당 간선을 포함하는 MST를 구하여 답을 구해낸다.. 하지만 E-V+1번 크루스칼을 돌린다면 TLE를 보게 될것이다. 그렇다면 E-V+1개의 간선을 각각 포함하는 MST를 어떻게 구해낼 수 있을까? 우선 현재 보고 있는 간선이 1번 정점과 5번 정점을 연결한다고 가정해보자. 그렇다면 우리는 기존의 MST에서 1번 정점과 5번 정점을 연결해주어 N개의 간선을 가진 그래프를 생각해보자. 해당 그래프를 트리로 만드려면 하나의 간선을 제거해야한다. 이 때 제거되야 되는 간선은 1번 정점과 5번 정점을 .. 더보기 BOJ)7795 먹을 것인가 먹힐 것인가 문제: icpc.me/7795 A집합과 B집합이 주어졌을 때 A집합의 어떤 수 X가 B집합의 어떤 수 Y보다 큰 경우의 수의 합을 출력하는 문제이다. A집합과 B집합의 크기 N M은 20000까지 들어올 수 있으니 O(N*M)의 방법으로 완전탐색한다면 한번의 테스트 케이스에서도 간당간당한데 여러번의 테스트 케이스를 거친다면 TLE를 보게 될 것이다. 우리는 B집합을 정렬한 후 lower_bound를 이용하여 N개의 쿼리에서 각각 X보다 작은 수 Y의 개수를 구할 수 있다. 시간 복잡도는 O((N+M)logM)이 될 것이다. 12345678910111213141516171819202122232425262728#include #include #include using namespace std;int t, n.. 더보기 BOJ)10815 숫자 카드 문제: icpc.me/10815 N개의 카드와 M개의 카드가 있을 때 M개의 카드 들이 각각 N개에 카드에 속해 있나 확인하는 문제이다.O(NM)의 방법으로 풀 경우 TL을 받으므로 binary_search를 이용하여 O(logNM)의 방법으로 해결하면 된다. 1234567891011121314151617181920212223#include #include #include using namespace std;int n, m, x;vector vt;int main() { scanf("%d", &n); for (int i = 0; i 더보기 이전 1 다음