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

더보기 이 문제는 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. 이분 탐색하는 거..

10000제출 달성. 백준 하지 마세요

이렇게 쉬운걸 왜 본대회 때는 못 풀었지 ㅡㅡ... 아마 긴장해서 그런가 보다. 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)이기 ..

scpc 166으로 망했다. 1번에 1시간을 썼다. 풀이는 보자마자 나왔는데 맞왜틀을 꽤 오래했다. 나머지는 그냥 골드만 긁었다 ㅎㅎ... 어제 결과가 나왔고 당연하게도 수상하지 못했다. 억울하다기 보다는 나 스스로에게 실망했고 화난다. 더 잘하고 싶다. suapc는 1등했다. sos dp를 내가 공부를 안 했었고, 우리 팀원들 중에 아는 사람이 없기도 했기에 이론상 맞출 수 있는 문제를 전부 맞춘 것 같다. lcp를 6개월 만에 짰는데 맞춘게 스스로 대견했다. 재밌게 풀었다. 자세한 후기는 Rebro님이 써주실 것으로 알고 있다 ㅎㅎ... 최근 1달동안 동기부여가 좀 덜 됐었는데, scpc를 망치고 나니까 갑자기 의욕이 막 생긴다. 더 잘하고 싶다. 화난다. 스스로에게 화나고 더 더 잘하고 싶다... ..

재밌고 교육적인 문제 ioi practice의 그래프 문제였다. 사실 함수구현이긴 하지만, interactive문제라고 보는 것이 더 정확할 것이다. 코포에 E번 정도에 나올법한 문제였다. i번 정점의 outdegree를 cnt[i]라고 하자. 우리는 모든 정점에 대해서, cnt[i]가 2이상인지를 확인해야 한다. 어떤 쿼리 query(x,y)를 날리게 되면, cnt[x]가 1 증가하던지, cnt[y]가 1 증가한다. 그렇다면 우리는 어떤 정점이 이미 cnt[i]가 2라면 굳이 이 정점을 이용한 쿼리를 날릴 필요가 없다는 점에 유의하자. interactor 가 adaptive이기 때문에 query(i,j)를 날리게 되면, cnt[i]를 interactor가 올리게 되면 확정적으로 아무 정보도 얻지 못한 ..

까먹기 전에 작성한다... 풀이를 안 보고 푼 문제가 거의 없다 ㅋㅋ. IOI는 진짜 너무 좋은 셋이다. 1. Antennas https://www.acmicpc.net/problem/25061 더보기 이 문제는 연습셋 도중에 풀이가 나왔었고, 정확히 정해랑 일치했는데, 시간이 없어서 셋 도중에 구현 못하기도 했고, 내 풀이에 자신이 없었다. 그냥 맞을거 같은데.. 까지는 나왔었는데, O(log n)번 이하로 작업이 이루어진다는 것을 증명하는 방법이 멋지니 꼭 알아두도록 하자. 증명 빼고는 나름? 웰노운 문제 2. 메기 농장 https://www.acmicpc.net/problem/25438 더보기 이 문제는 거의 접근 했고 풀이도 나왔는데, 핵심적인 관찰을 하지 못하면 구현이 매우 매우 더러워진다. 구..

교내 청정수컵 진행하다가 화났던 일인데 까먹었다가 방금 생각이 나서 다시 까먹지 않기 위해 적어봄 우리는 대회를 다산관에서 진행하기로 되어있었다. 한 3주전 부터 얘기를 해 놓은 상태고 학회원 한테 그렇게 공지해놓은 상태였는데 갑자기 사용불가능 하다는 연락이 왔다. 갑자기 거기서 다른 기업 코테를 친다네? ㅋㅋ 그래놓고 우리한테 변명으로 대회 자체가 서강대 전원 대상이 아니라 학회원 대상이기 때문에 안된다는 말도 안되는 변명을 자꾸 한다. 선약이 되어 있었으면 인간대 인간으로 이거는 우리한테 할당해야 하는게 당연히 맞지 않는가... 적게 참여하는 것도 아니고 100명 가까이 참여한 건데... 그냥 학교 차원에서 학생들 개무시하는게 느껴진다. 뭐 어쩌겠는가 우리가 을인데 학교에서 학회관련 일처리도 진짜 인..