title: "C++ Skills" excerpt: "Skills by C++" category: Cpp-Reference tags: [ C++, , , iterator, sort, permutation, combination, dfs, bfs, brute-force, union-find, merge, set_union, set_intersection, set_difference, lower_bound, upper_bound, , ] toc: true Skills by C++ 모든 부분집합 by bit & bit & 연산으로 모든 부분집합 구하기 #include using namespace std; vector getSubsets(vector arr){ vector totalSet; // 결과 Set i..
문제 링크 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 풀이 효율성 문제라길래 해설을 보았고 union-find 알고리즘으로 푸는 문제였다. 시간 복잡도는 O(nlogN)으로 풀어야 효율성 테스트 케이스가 풀린다고 한다. // findRoom() --- 전역 변수로 map을 선언하는 대신 참조자로 매개변수로 받아서 구현하였다. if(요구하는 방번호는 배정해도 된다) map에 요구하는 방 번호는 다음 방 번호 저장한다.(다음 방 번호를 재귀로 찾을 수 있도록) 배정 안된 것의 번호를 리턴 else(이미 배정된 것이 있다) 배정 안된 것의 번호를 찾아서 저장 map에는 배정 안된 것의 다음 번호를 저장(나중에 또 물어보면 바로 찾을 수 있도록, 순차적으로X) 배정 안된 것의 번호를 리턴..