반응형 C++93 유일한 수 두개 알고리즘 문제 전체 링크 judge.koreatech.ac.kr/problem.php?id=1074 유일한 수 문제의 응용 버전이다. 모든 수가 짝이 있으나 단 2개의 수만 짝이 없다. 유일한 수 문제대로 풀면 짝이 있는 수는 자연스럽게 제거할 수 있지만, 짝이 맞지 않는 두 수가 xor 연산되어 있어서 답을 구할 수 없게 될 것 같다. 하지만 여전히 xor 연산을 이용해서 문제를 해결할 수 있다. 먼저 두 수가 다르다는 것은, 최소 1 bit가 다르다는 뜻이 된다. 즉, 모든 N을 xor한 후, 어떤 다른 1 bit를 기준으로 1 bit가 있는 경우는 on에 xor을 1 bit가 없는 경우는 off에 xor을 하면 두 수가 분리된다. 예를 들어서 두 수가 3과 7이라고 하자. 0011(3)과 0111(.. 2021. 3. 1. C, C++ - 최하위 / 최상위 비트 구하기 (Find MSB, LSB) C, C++ 전체 링크 삼성 C형 전체 링크 참고 - 비트 단위로 출력하기 다음과 같은 비트가 있다고 가정하자. 0010 0000 1100 0010 그러면 최하위 비트(Least Significant Bit)와 최상위 비트(Most Significant Bit)는 아래와 같다. 0010 0000 1100 0010 0000 0000 0000 0010 → 2 : 최하위 비트 (LSB : Least Significant Bit) 0010 0000 0000 0000 → 8192 : 최상위 비트 (MSB : Most Significant Bit) 최하위 비트 구하기 최하위 비트 추출법은 매우 간단하다. int lsb = x & (-x); // int lsb = x & (~x + 1) 2의 보수를 구하는 방법이기도.. 2021. 3. 1. 유일한 수 알고리즘 문제 전체 링크 judge.koreatech.ac.kr/problem.php?id=1007 문제의 조건을 보면 홀수개의 숫자가 입력이 되고, 그 중 단 하나만 다르다. 따라서 bit 연산 ^(xor)을 누적하면 단 하나의 숫자만 남게 된다. 어떤 숫자 N에 숫자 M bit를 반전시키고, 다시 M bit를 반전 시키면 N이 되기 때문이다. ( N = N ^ M ^ M ) 따라서 0부터 시작해서 누적하면 짝이 있는 숫자들은 자연스레 사라지게 된다. #include int T, N; int main(void) { scanf("%d", &T); for (int tc = 0; tc < T; tc++) { int ans; scanf("%d", &N); ans = 0; for (int i = 0; i < N.. 2021. 3. 1. 이전 1 ··· 8 9 10 11 다음 반응형
