노력하는 공대생의 공부일지

https://physicsmathcoumputer.tistory.com/82 이런 식의 구간 쿼리의 문제들은 차이를 살펴보면 풀린다. arr[x]를 x-1번째 호떡과 x번째 호떡이 다르다면 1, 같다면 0으로 두자. 즉 arr[x]=v[x]^v[x-1] 2번 쿼리는 다음과 같이 해석된다. 1.arr[x]=0인 (x>=2)를 고른다. 만약 arr[1]+arr[2]+...+arr[x]가 2로 나누어 떨어진다면 arr[1]과 arr[x]에 1을 xor한다. 만약 arr[1]+arr[2]+...+arr[x]가 2로 나누어 떨어지지 않는다면 arr[x]에 1을 xor한다. 이걸 이용해 새로운 문제로 치환하면 쉽게(?) 풀린다. 힌트는 arr[1]을 고를 수 없다는게 포인트이다. (즉 arr[1]을 어떻게 목표에..

이 문제를 그래프로 해석해서 풀어보자. 각 학생은 다음 두 집합중에 하나에 속하게 된다. A = {우승가능성이 있는 학생} B = {어떻게 해도 항상 패배하는 학생} 우리의 목표는 A에 속한 학생들을 모두 구하는 것이 목적이다. 천적관계에 대해서 간선을 만든다고 생각해보자. 즉 x가 항상 y를 이긴다면 x->y인 모든 간선을 추가한다고 생각해보자. 첫번째 아이디어는 다음과 같다. A에 속해있는 임의의 정점을 a, B에 속해있는 임의의 정점을 b라고 해보자. 우선 연결그래프가 아닐 경우는 무조건 모든 정점이 되므로 넘어가자. (이건 쉬우니 생략하겠다...) 1. b에서 a로 가는 간선은 존재할 수 없다. 쉬운 증명: a는 이길 가능성이 있는데, a를 b가 이긴다는 것은 b도 이길 가능성이 있다는 뜻. 직관..

https://cce.cstec.kr/ 생애 최초로 ctf대회를 나갔다. 참가 확정이 최근에 나서 해킹 공부를 1주일정도 전부터 시작했는데 재밌더라 근데 개어렵다 ㅋㅋ ps보다 시작하는 난이도가 높은 것 같다. 1학년때 해본다고 까불다가 접었었는데 그때보다 전공지식이나 사고가 깊어져서 그래도 할만한 것 같다. 공공부문으로 출전했다. 선임 + 주무관님 포함 4인팀으로 했다 dreamhack.io로 pwnable만 공부하고 갔는데 난이도 어렵더라 ㅜ 그래도 한문제 나랑 팀원이랑 같이 상의해서 해결하고 나머지 한 문제 다른 팀원분이 풀어서 적당히 2솔해서 1솔이상 팀들중에 절반이상은 한 것 같아서 좋았다. 오랜만에 팀대회나가니까 재밌긴 하더라. 첫 ctf대회로서 느낀점은... 문제는 20문제인데 본선컷이 3~..

입대하고 2달 정도 지났다.뽑기 운이 좋아서 육군사관학교 근무지원단 정보통신대 소속 정보보호병으로 일하게 되었다. 군대와서 좋은 점이라는 제목으로 글을 작성하려다 장/단점으로 구분하는 것보다 나의 변화와 나의 생각에 초점에 두는 것이 더 나을거 같아 제목을 고쳤다. 1. 긍정적인 생각 군대는 극한으로 부정적인 환경이다. 나의 의지와는 전혀 상관없이 18개월이라는 시간을 지내야 한다. 나는 훈련에서 오는 육체적인 고통보다는 단체생활을 하며 지내며, 통제된 삶을 살아가는 모습에 대한 스트레스가 배는 컸다. 하지만 어차피 벗어날 수 없는 환경이고, 내가 군대에서 얻을 수 있는 것들과 얻어가야 할 것들에 대해 초점을 맞추고 살아가기로 했다. 그러니 조금 나아졌다 ㅋㅋ... 부정적으로 살아봐야 나만 힘들듯. 열심..

국방부 취업 성공 23등으로 정보보호병 들어갔네요 원래 면접/합격 후기 같은 걸 쓰려고 했는데 이제 더는 안뽑는 직군이라서 안쓰려고요 2월 13일 군 입대... 화이팅

어제 있었던 라운드의 D번을 한번 풀어 보겠다. 어제는 셋이 매우 어려웠다. A,B,C,D모두 애드혹으로 발상이 힘들었다. 하지만 퀄리티 자체는 좋은듯... 어렵긴 해도... 풀이의 핵심은 절대 0이 될 수 없는 ai를 배제하자는 것에서 나온다. a,b,c 세 수가 있다고 하자. 그리고 gcd(a,b),gcd(a,c),gcd(b,c)를 알 때, 0이 될 수 없는 수를 어떻게 찾을까? 어떤 변수 x에 대해서 gcd(0,x)=x라는 사실을 이용하자. val[a]=gcd(a,b)+gcd(a,c) val[b]=gcd(b,a)+gcd(b,c) val[c]=gcd(c,a)+gcd(c,b) 라고 정의하자. 세 수 a,b,c중에 0이 존재한다면, val이 가장 큰 것이 0이된다. 그것도 strictly 하게 크다. 이..

2022년 12월 8일 오후 1시 즉 내일 1시가 육군 정보 보호병 면접이다. 인터넷 보안 전문가 2급 + 2학년 수료로 1차 서류 테스트는 4등이였다. (아마 예전 같으면 더 빡셌겠지만, 지금 BOB / 수상 실적 추가 점수가 다 사라졌다... 난 있는게 더 공평할 거 같지만 뭐 나는 둘 다 없으니 개꿀.. ㅎㅎ) 60명 중에서 30명을 뽑는다. 근데 진짜 정보 보호에 대해 아는게 거의 없는데... 어떻게 붙을지 모르겠지만 서도... 벼락치기 공부중이다. 1차 서류 점수 + 내일 필기 테스트 10 문제 (20점) + 인성 면접 (10점) + 기술 면접(10점) 이렇게 해서 선착순으로 30명 뽑힌다. 근데 정보 보안에 대해 진짜 아무것도 몰라서 너무 걱정이다... 망할 기술 면접. 꼬리 질문 나오면 대답..

더보기 이 문제는 3-coloring 문제와 연관시켜 푸는게 좋다. 즉 3-coloring보다 1-in-3 sat이 더 어렵다는 것을 보이면 (즉 1-in-3-sat을 풀 수 있다면 3-coloring 을 풀 수 있다는 것을 보이면 된다.) 3-coloring이 np complete임을 아므로, 자연스럽게 증명이 된다. 3-coloring문제를 다음과 같이 해석해보자. 각 정점 v에 대해서 v의 색깔 red,blue,green에 대한 세 변수 Rv,Bv,Gv를 만든다. 이 변수는 v가 red라면 Rv만 true이고, 나머지는 false이다. 모든 색에 대해 동일하게 적용된다. 그렇다면 (Rv or Bv or Gv)라는 clause를 각 v에 대해 만든다. 그 후 모든 edge (a,b)에 대해 다음과 같..

퀴즈가 2문제가 나왔는데 증명까지 써서 제출해야 하는데 문제당 4분을 줬다; 족보가 없으면 불가능하다고 개인적으로 생각 ㅜㅜ. 둘 다 못 풀었다. 1. 그래프가 주어졌을 때, k개 이하의 clique들로 그래프를 분할 할 수 있는지 판단하는 것은 np complete임을 증명하라. 더보기 complement graph를 생각한다. 즉 간선들의 연결관계를 뒤집는다. 그렇다면 originial graph에서의 clique는 complement graph에서 independent 하다. 즉 complement graph에서 k-coloring 문제와 정확히 동치임을 알 수 있다. k-coloring은 k>=3에서 np-complete임을 아므로 끝. 2번 문제는 3-sat 어쩌구 였는데... 기억이 안나서 모..

자동장치 이론 기말고사 범위 책이다. 알고리즘 관련 내용이라 시간이 되면 교과서에 있는 예제를 풀어볼 생각이다..