XOR연산(⊕로 많이 표기 된다.)은 논리 이항 연산자이고, 두 입력이 다를 때만 참을 반환하는 연산자이다. 다음 그림은 XOR연산의 진리표이다.

그리고 이 연산은 Z2(Z/2Z라고도 표기한다)와 깊은 관련이 있다. Z2란, 어떤 정수를 2로 나눈 나머지인 0과 1에만 관심을 가지는 체계를 말한다. 예를 들면, 우리는 X와 Y가 어떤 수이든 관계 없이, X가 짝수이고, Y가 짝수이면 X+Y도 짝수임을 알 수 있다. 이 XOR연산은 Z2에서의 덧셈과 일치한다. 즉 홀짝성이 다른 두 수를 더해야만 홀수가 나온다.

이 xor을 비트단위로 나눠서 확장한게 bitwise-xor 이고(C, C++, Python 등에서 ^ 연산자로 많이 표기된다.), 이진법으로 표현했을 때의 각 자리마다 비트를 표기한다. 예를들면 1100(2)⊕1010(2)=0110(2) 같이, 1(2)의 자리가 00 = 0이므로 0이고, 10(2)의 자리가 0⊕1=1 인 등등.. 으로 계산한 결과이다. 이 비트단위 xor은 각 자리마다 연산이 보존 되기 때문에 우리는 각 자리를 따로 생각할 수 있고, 결론적으로 bitwise-xor 연산은 Z2n에서의 덧셈이 된다. 그리고 이것을 우리는 스칼라가 Z2이고, 각 벡터가 Z2n인, 벡터 공간으로 생각할 수 있다.


그래서 우리는 다양한 xor이 연관된 문제들을 벡터 공간으로 바꾸어서 해결 할 수 있다. 예를들면, 숫자들이 여러개 있는데 몇 개를 xor해서 최대가 되게하라는 문제를, 벡터 공간에서 최댓값을 찾아라 같은 문제들로 적당히 바꿀 수 있고, 벡터 공간은 여러가지 좋은 성질들이 많기 때문에 유용하게 사용될 수 있다. 그리고, Row space를 벡터 공간으로 가지는 행렬을 생각할 때 가장 먼저 고려되는 연산인 Reduced Row Echelon Form을 구할 때, 숫자들을 비트단위로 관리할 수 있어, 상수를 크게 줄이는데(32~64배 정도 계산량을 줄일 수 있다.) 도움을 줄 수 있다.


이 사실로 풀 수 있는 문제를 몇 개 남기려고 한다. 대부분의 문제가 어렵기 때문에, 문제를 해결 할 수 있다면 자신감을 가져도 좋다고 생각한다. 질문이 있으면 덧글로 남겨주면 된다.



스포일러 주의






'수학' 카테고리의 다른 글

XOR과 Vector Space에 대해서  (2) 2017.11.23
  1. 좋은문제 2017.11.24 00:38

    http://codeforces.com/contest/724/problem/G

    스팸아님

https://github.com/koosaga/DeobureoMinkyuParty


나는 내 코드나 내 자료들을 퍼블릭하게 올리는게 이롭다고 생각해서 자료들을 계속 업로드 하자고 제안을 했었다.


팀노트를 깃헙에 올리는게 어떻냐고 물어봤고 팀원들이 동의를 했다. 그래서 대전 리저널이 끝난 이후에 올리자는 얘기가 있었고 결국 사과가 팀노트를 업로드 했다. 사실 내가 좀 주도적으로 하는 일이여야 하는게 맞지 않았나 싶다. MolaMola 팀이나 Please Open Testdata 같은 팀도 팀노트를 열었기 때문에, 다른 팀노트의 좋은 점을 받아들이고 개선할 부분을 서로 개선하고 보완하는 방향으로 서로 팀노트를 잘 만들어 갔으면 좋겠다.


사실 지금 팀노트가 굉장히 난해하고 PS에서 사용하는 지식들의 끝단을 다루는 것 같다. 그래서 더 다양한 코드들을 추가하고, 입맛에 맞게 팀노트를 조절해가면서 쓸 수 있게 다양한 레퍼런스 코드들을 써 보려고 한다. 예를들면 기본적인 알고리즘인 Dijkstra나 Extended Euclidean Algorithm 같은 것들은 팀원이 다 짤 줄 안다고 작성을 안했고... 팀원이 알지만 디버깅할 때 버그가 많이 생기는 알고리즘이나, 상수가 매우 작은 (Locality to the rescue!) 알고리즘들이 들어있다. 혹은 공식들을 그냥 블랙박스로 사용하는 정도이다.


공개할 용도의 팀노트를 정비하는 일도 결국에는 해야 할 일인데, 언제부터 해야할 지 모르겠다. 일단 다양한 예제들을 추가하는 것으로 부터 시작해야겠다.

고등학교때 부터 시작해서 4년 8개월동안 기숙사 생활을 했다. 2013년 3월 부터 시작해서, 2017년 11월 이 글을 쓰는 시점까지 그리고 이제 자취라는 것을 시작해 보려고 한다. 아마 12월쯤이면 자취를 시작하지 않을 까 싶다. 방 정리하기가 귀찮아서 그렇지 끝나면 거의 들어가지 않을까 싶다.



자취를 시작하게 된 원인에는 여러가지가 있다. 기숙사 생활에 질린것이 가장 클 것이다. 그리고 여러가지 내가 가지고 있는 욕구들을 해소하기 위해서 일 것이다. 예를들면 "개인 공간이 필요하다." 라든가 "요리가 하고 싶다" 같은... 몇가지를 정리 해 봐야 할 것 같다.




개인 공간이 필요하다


이게 아마 내가 가장 절실하게 자취를 하고 싶다고 생각한 이유가 아닐까 싶다. 개인 공간이 없다는 것이, 내성적인 성격 탓에 혼자 있을 시간에 나를 혼자 있게 놔두지 못하는 것도 꽤나 스트레스를 받는다. 사람 만나는 것이 내부의 에너지를 소모하면서 외로움을 없애는 것이라면, 다른 사람 없이 혼자 있는 것은 내부의 에너지를 회복하는 쪽에 가까울 것이다. 내성적인 성격의 가장 큰 장점이 "모든걸 포기하고 아무것도 안하고 오래 누워있으면 에너지가 회복이 되는 것" 이라고 생각하는데, 나는 기숙사에서 이걸 하기가 힘들었다. 사실 학기 중에 이걸 하기 힘든것도 없진 않았다. 뭐 어쨌든 방학때든 학기 중이든 혼자서 누워서 회복 할 수 있을때가 정말 필요하다고 생각했다. 내가 무얼 해도 아무도 뭐라고 하지 않는 것도 중요하다. 설령 내가 무언가를 하지 않더라도 그런 안정감을 느끼는것은 굉장히 중요하다고 생각했다.




요리가 하고 싶다


이건 사실 안 해봐서 잘 모르겠지만... 뭔가 만들고 싶다는 욕구가 있고 이상하게 요리쪽으로 그런게 있다. 먹는걸 워낙 좋아하는 것도 있을 것 같고, 여러가지 요리 레시피를 보고 좋다고 생각한것도 있는것 같다. 그리고 학교에서 먹을게 없다고 느낀것도 제일 크다. 학교에서 배달을 시켜먹거나 학식을 가서 먹으면 만날 뻔한 메뉴의 음식들을 계속 먹게 되는데 너무 질렸다.




부동산이 필요하다


뭔가 집을 가지고 사고 판다는 의미가 아니라, 내가 원하는 것들을 하려면 나만 건드릴 수 있는 공간이 있어야 한다. 예를들면 서버를 배치한다거나, 피규어를 놓는다거나, 개인 공간이 필요한다는 것과 비슷한 맥락인것 같기도 하지만, 조금 다른 느낌의 장소가 필요하다. 사실 피규어를 안 모으는 이유에는 놓을 곳이 없다는 것도 있다.





학교에 들어와서 동아리방에서 잔 적이 기숙사에서 잔 적보다 많은 것 같다. 어차피 기숙사가 개인 공간이 아니고, 동아리방은 외로움도 해결할 수 있고 바로 옆에 컴퓨터도 있기 때문에 이런 것 같다. 동아리방에서 자면 건강도 안 좋아지고, 이런데 자취가 뭔가 내가 바뀔수 있는 계기를 제공하지 않을까 하고 생각한다.

'생각들' 카테고리의 다른 글

동아리 하제  (0) 2018.08.27
교수님과 상담을 하고 왔습니다  (1) 2018.07.11
2018년 가을 5학기 수강신청  (0) 2018.07.09
자기비하에 내가 느낀 점에 대해  (2) 2017.12.16
기말고사 안 갔다.  (0) 2017.12.12
자취에 대해서  (0) 2017.11.22

+ Recent posts