4개의 댓글이 있습니다.
-
-
Signin -
1024 = 2^10 이므로 0이상 1024미만 짝수의 개수는 2^9개입니다.
또한 {1,2, ..., 9} 는 원소를 9개 가진 집합이므로
이 집합의 부분집합 개수는 2^9개입니다.
둘의 개수가 일치하므로 1:1 대응을 시킬 수 있습니다.10개 비트로는 0~1023 까지 표현이 가능합니다.
그런데 여기서는 9개의 비트로 짝수만 표현하므로,
쉽게 대응시켜 보면 이진수 값에 2를 곱한 결과가 실제 숫자라고
생각하시면 편할 듯 합니다.ex1) {1} = 1(이진수) = 실제 값은 1 x 2 = 2
ex2) {1,2} = 0011(이진수) = 실제 값은 3 x 2 = 6
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
cjkis
정수 변수를 이용해 정수의 집합을 표현하기로 합시다. 해당 집합에 숫자 i가 들어 있다면 i번째 비트가 켜져있는 것이죠. 그러면 1024 미만의 짝수와{1,2,...,9}의 부분 집합 간에 1:1 대응이 성립합니다.
라고 되어있는데요..
이게 어떻게 가능하죠?
제가 생각했을 때는
1024 미만의 짝수를 몇개 구해보면
이렇게 홀수인 3({1,2}), 5({1,3})와 같은 부분집합은 빠지게 되는게 이게 어떻게 {1,2,...,9}의 부분 집합과 1:1 대응이 되는거죠?
10년 전