아무코딩

문제풀이 java 의 경우에는 비트마스크를 이용해서 풀어보았고, c++의 경우에는 dfs를 사용해서 풀었다. 7달 전에 작성한 방법과 다른방법으로 풀어보고자 비트마스크를 사용해보았다. 문제 풀이 방법은 구역을 다 나누어보고(완탐), 그렇게 나누었을 때 조건이 성립하는지(연결이 되는 상태인지)를 체크해준다. 조건이 만족할시에는 최솟값 업데이트를 해준다. 소스코드 java 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 ..

문제풀이 크게 문제풀이는 유일성을 확인 -> 유일성을 만족하는 것중 최소성을 만족하는것을 구하기 순으로 풀이하였습니다. 비트마스크를 이용하였고 비트마스크를 적용하니 이전보다 문제풀이가 훨씬 깔끔해졌습니다. 1. 유일성 확인방법 vector을 키로가지는 Set을 만들어 여러 경우의 키를 가지는 경우를 넣어서 set 의 사이즈가 레코드의 개수와 같을때 유일하다 판단합니다. 여기서 키로 선택된 칼럼은 비트로 1 아닌건 0으로해서 계산하는데 유일성이 만족되면 해당 값을 벡터에 저장합니다. 2. 최소성확인방법 유일성을 만족하는 벡터를 차례로 돌며 & 연산을 진행합니다. a == a&b 일때 a는 b의 부분집합입니다. 그래서 b는 최소성을 만족할수 없기때문에 제외시킵니다. 이와같은 방법으로 모두 비교하여 최소성을 ..

문제풀이 비트마스크를 사용한다 두 벡터에 & 연산을 적용한 값을 저장한 벡터를 생성한후 앞에서부터 차례로 1