문제 링크 두 수의 XOR 연산이 가장 크기 위해선, 두 수를 각각 이진법으로 표현했을 때 같은 위치에 있는 숫자들은 한 쪽이 0이면 다른 쪽은 1, 한 쪽이 1이면 다른 쪽은 0이 되어야 한다. 예를 들어보자. 이진법으로 표현했을 때 101001 과 같은 숫자가 있고, 주어지는 숫자들은 모두 111111보다 작거나 같다는 보장이 있다면, 101001과 XOR 연산을 했을 때 가장 큰 숫자는 010110과 가장 차이가 적은 숫자가 된다. 이 가장 차이가 적은 숫자를 찾는 방법은 두 방법이 있다. 먼저, 첫 번째 방법을 알아보자. (wwiiiii님 풀이.) 숫자 k에 대해 k에 NOT 연산을 하여, k와 XOR을 했을 때, 최대값이 되는 숫자 k`을 구한다.(int의 경우는 2진법 표현해서 첫번째 자리가 ..
문제 링크 스터디를 하게 되면서 매주 정해진 BOJ 문제를 풀고, 풀이를 작성하게 되었다. 문제에는 철로, 사람의 집, 사람의 사무실이라고 되어있지만, 사실 간단하게 생각해보면 다음과 같은 내용이다. f(x) = [a_i, b_i] ⊆ [x, x+d] 인 i의 갯수 (단, a_i ≤ b_i) 이 f의 최대값은 얼마인가? 라고 물어보는 문제다. 그럼 문제의 이슈는 크게 두 가지로 좁혀진다. 1. 어떠한 x에 대해서 해 볼 것인가? 임의의 x를 골라보자. [a_i, b_i] ⊆ [x, x+d]를 만족하는 i가 존재한다면 그 i들 중, a_i가 가장 작은 i가 존재한다. 그 i를 k라 하자. 이제 f(a_k) ≥ f(x) 임을 보이자. [a_i, b_i] ⊆ [x, x+d]를 만족하는 i들에 대해 a_i ≥ ..