그냥 하는 노트와 메모장

* XOR 그룹 [ 분류 - DSU ] CS Academy Round #9의 Array Removal이라는 문제를 먼저 푸는 것을 권장합니다. 1. 수가 작은 것 부터 제거해나가므로, 지우는 순서는 정해져 있다. 2. k번째 수를 제거했을 때의 XOR 그룹의 합 최대값과 k+1번째 수를 제거했을 때의 XOR 그룹의 합 최대값은 서로 종속적이다. 3. 지우는 과정에서 나오는 XOR 그룹의 합 최대가 되는 값을 출력한다. 삭제하는 순서대로 답을 도출해내기란 쉽지 않다. 따라서 문제 접근 방식을 조금 다르게 해야하는데, 삭제하는 과정 자체에 의미가 없다는 것을 깨닫는 것부터 시작한다. 무슨 소리나면, 1.처럼 순서는 정해져 있으며, 2.처럼 서로 종속적이기 때문에 종속의 의미 지니게끔 접근하는 것이다. 주어진..

* CS Academy Round #9 - Array Removal[ 분류 - DSU ] 이 문제의 특성은 다음과 같다. 1. 지워야하는 순서가 정해져 있다. 2. 순서가 정해져 있는 만큼, k 번째 수를 지웠을 때 큰 수 S_k와 k+1번째 수를 지웠을 때 큰 수 S_k+1는 서로 종속적이다. 3. 수를 제거해나가며 큰 수를 출력해야 한다. 먼저 Greedy하게 접근해보자. S_k와 S_k+1를 비교해보자면 S_k >= S_k+1이 성립함을 직관적으로 알 수 있다. 또한 2.번에 의해 서로 종속적이기 때문에, "순서를 거꾸로" 생각하자. 거꾸로 생각하면, 초기에 없는 데이터에서 하나씩 생성됨을 알 수 있다. 따라서 이를 DSU로 합치는 방식을 택하며, 지금 합친 것과 지금까지의 최대값을 비교해나가며 답..