반응형 XOR2 [백준/C++] 도미노 예측 (No. 17943) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 xor 연산에 대해 잘 알고 있으면 쉽게 풀 수 있는 문제다. xor 연산은 2진법으로 표현한 뒤 두 수를 비교했을 때 같은 자리에 있는 수가 같으면 0 다르면 1로 표현하는 연산이다. 즉, A (xor) A는 같은 수 이므로 모든 자리에 있는 수가 같으므로 값이 0이 된다.또한 A (xor) 0을 연산할 경우 0과 연산했으므로 0은 모든 자리에 있는 수가 0이므로 결과 값이 0이 된다. 이를 이용하면 누적해서 xor을 계산해 둠으로써 쿼리의 연산을 빠르게 해결할 수 있다. 아래 그림을 보며 생각해보자 위 .. 2024. 11. 7. [SWEA/C++] 돌 추가 게임 (No. 20945) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 풀기 위해서 고민을 좀 많이 했다. 문제에 대해 간단히 설명하자면 Nim 게임이라 불리는 문제에서 응용된 문제다. 여기서 스프라그-그런디 정리를 Nim 게임에 적용하면 돌 무더기에 대해 xor을 계산하는 것으로 누가 이기는지 알 수 있다. 그러므로 후공인 지혜가 이기기 때문에 모든 돌 무더기를 xor값이 0이 되도록 만들기 위해 돌 무더기에 돌을 추가하는데, 이 때 추가해야하는 가장 적은 돌의 양을 계산하면 되는 문제다. 그렇다면 돌을 어떻게 추가해야 가장 적게 돌을 추가할 수 있을까? 먼저 생각해보면 xor.. 2024. 6. 20. 이전 1 다음 반응형
