분류 전체보기 118

군대에서의 생각과 느낀 점.

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

Codeforces Round #838 (Div. 2) D.GCD Queries

어제 있었던 라운드의 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명 뽑힌다. 근데 정보 보안에 대해 진짜 아무것도 몰라서 너무 걱정이다... 망할 기술 면접. 꼬리 질문 나오면 대답..

자유/계획 2022.12.07

재미있는 과제 복습

더보기 이 문제는 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 어쩌구 였는데... 기억이 안나서 모..

최근 푼 문제 어려운 것들 정리

https://atcoder.jp/contests/abc278/tasks/abc278_g game 문제 누가 봐도 그런디를 쓰면 될 것 같다. 실제로 정해도 그런디 + 최적화 풀이를 언급. 하지만 실상은 애드혹 문제. 후공이 선공의 선택을 따라 할 수 있다는 것이 중요 포인트. https://codeforces.com/contest/1747/problem/E 그냥 dp 문제인데 중요한 점은 1차원에서 움직이는 걸 잘 합쳐서 2차원짜리 정답을 구하자. https://www.acmicpc.net/problem/22023 미친 문제. 최대 최소가 특정 값을 넘어가는 구간을 잘 찾으면 문제가 해결된다. 갓 문제. https://www.acmicpc.net/problem/25442 미친 문제2. 이분 탐색하는 거..

Codeforces Global Round 22 #F. Connectivity Addicts

이렇게 쉬운걸 왜 본대회 때는 못 풀었지 ㅡㅡ... 아마 긴장해서 그런가 보다. E번 같은 유형은 내가 잘 못하는 유형이었는데 빠르게 F로 넘어갔다면 조금 더 침착해서 풀 지 않았을까... 일단 $s_c \leq n_c^2$ 라는 조건을 잘 해석해야 한다. 그런데 degree가 큰 정점 부터 살펴본다고 했을 때, x라는 정점에 degree(x)번 쿼리를 날린다고 하면, 우리는 (degree(x)+1)개의 정점으로 이루어진 connected component를 알게된다. 이들을 모두 같은 색으로 색칠하면 항상 조건을 만족한다. 왜나면, degree가 가장 큰 정점을 뽑았기 때문에 $s_c$는 degree(x)(degree(x)+1)이하이고, $n_c$는 (degree(x)+1)(degree(x)+1)이기 ..