돌이 코딩하는 방

이번에는 생일도 지났겠다... 그리고 워낙 바쁘기 때문에 천천히 준비하려고 한다. 그래도 준비 과정을 다 기록을 해야 추후에 추억도 되고, 나중에 도움도 되기 때문에 준비과정을 기록해 보려고 한다. 5.18 그래도 뭔가를 해보기 위해서 semi-game cup 슬랙을 팠다. 지난번에 해본 결과 슬랙속의 하나의 채널을 운영하는 것보다 따로 슬랙을 파서 진행하는 것이 좋은 것 같다. slack에 운영진 blackking26과 karuna를 초대했다. 그리고 idt 검수진에 참여해 본 결과 notion이 대회 준비에도 굉장히 쓸만하다는 사실을 알게 되었다. 5.19 내가 미리 구상했던 미스터리 게임을 말했고 변화를 주려고 생각했다. 미스터리 게임은 번외문제로 많은 사람의 관심과 참여를 유발하려고 만들었다. 원..

문제 링크 : https://www.acmicpc.net/problem/18721 문제 태그 더보기 세그먼트 트리 문제 풀이 와... 미친 아이디어 문제이다. 솔직히 자력으로는 정말 풀기 힘든 문제라고 생각한다. 어쩌면 수올러들이 생각할 확률이 더 높을 수 있다. 그런 느낌의 풀이이다. 왠만하면 오래 고민해보고 이 글을 읽는 것을 추천드리며, 이 글을 읽을 때도 풀이의 일부씩만 보고 다음 직접 풀이를 완성하면 훨씬 좋을 것 같다. 처음에 1주일동안 생각했다가 도저히 떠오르지 않아서 풀이의 첫줄을 보았다. "한 호를 잡아 정답이 되는 세트의 가장 작은 호라고 생각해보자" 이 문장에 대해서 곰곰히 생각해 보니까 풀이가 서서히 확장되기 시작했다. 이 글과 같이 분석을 해보면 지정한 호와 다른 호들의 관계를 분..

문제를 풀다가 문제에서 쓰이는 구현의 좋은 아이디어가 떠올라서 글을 쓰려고 한다. 엄청나게 대단한 것은 아니지만, 이 아이디어를 쓰지 않고 구현을 하면 구현을 포기할 정도로 역겨워지며, 꼭 기억하고 싶기 때문에 글로 남기려고 한다. 원에 호가 두 개 있다. 그 두 개의 호에 대한 위치관계를 알아내는 것이 목표이다. 원에 n개의 지점이 있고, 두 개의 지점 번호를 통해서 호를 표기한다. (a,b)에서 bb.ss가 되며, 나머지는 보이는 그대로 대소 관계에 따라서 경우가 나온다. 코드는 아래와 같이 나온다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ll mat(pii a,pii b){ ll p=a.ff; a.ff=(a.ff+nn-p)%nn; a.ss=(a.s..

문제 링크 : www.acmicpc.net/problem/12876 문제 태그 더보기 Offline dynamic Connectivity , Lichao Tree 문제 풀이 보통 반평면 땅따먹기 1은 풀고 올 것이니 이에 대한 풀이는 알고 있다고 가정하려고 한다. 반평면 땅따먹기 1은 그냥 일반적인 cht optimization이 아니라 직선의 기울기의 단조성이 없기 때문에 lichao tree를 써야하는 문제였다. 반평면 땅따먹기 2에서는 이제 선분이 중간에 없어진다. 선분에 life가 존재하게 되었다 이러한 문제는 offline dynamic connectivity로 풀 수 있다. lichao tree에서 선분이 추가될 때, 노드를 내려가면서 여러개의 노드를 업데이트 하게 된다. 그 과정에서 노드의 ..

오프라인 다이나믹 커넥티비티 (offline dynamic connectivity) 1년전에 배우고 최근에 복습한 알고리즘. 이번 글에서는 오프라인 다이나믹 커넥티비티라는 알고리즘에 대해서 다뤄보려고 한다. 이 글에서 앞으로 odc 라고 줄여쓰기도 할 것 같다. When? 어떤 문제를 풀기 위해 쓰느냐. life가 있는 변화들과 질문들이 쿼리로 들어왔을 때 사용한다. 문제 www.acmicpc.net/problem/16911를 보자. 각 간선들은 연결을 했다가 일정 시점 이후 사라진다. 또한, 중간에 어떤 두 점의 연결성을 물어보는 쿼리들이 주어진다. 이런 형태의 변화되는 선분과 두 점간의 연결성을 물어보는 문제가 대표적인 odc를 쓰는 문제이다. 위에서 소개한 문제를 odc로 푸는 과정을 소개할 예정이..

Lev.14 sshkey.private 파일 확인. ssh -i sshkey.private bandit14@localhost를 입력하여 서버에 host권한으로 들어간다. 비밀번호의 위치를 알려주었으므로 cat과 절대 경로를 이용해서 들어가면 비밀번호 4wcYUJFw0k0XLShlDzztnTBHiqxU3b3e를 얻을 수 있다. Lev.15 nc - 네트워크를 통해 읽거나 씀 nc [host] [portnumber] echo - 응답 echo 4wcYUJFw0k0XLShlDzztnTBHiqxU3b3e | nc localhost 30000 를 입력하여 전달하면 비밀번호 BfMYroe26WYalil77FoDi9qh59eK5xNr를 얻을 수 있다, Lev.16 openssl s_client -connect loc..

방학 때 했었는데 뇌가 썩었는지 많이 까먹어버렸다. bandit을 해야할 명분이 생겨서 다시 하는김에 다시 까먹지 않고, 깔끔하게 정리하기 위해서 글을 쓰려고 한다. 어떤식으로 쓰는(이 글은 지속적으로 업데이트 됩니다.) Before start Bandit은 명령어를 활용하여 다음 단계 서버의 비밀번호를 계속해서 알아내는 퍼즐이다. 다양한 명령어를 사용하여 비밀번호를 알아내고, 그 번호를 바탕으로 다음 서버에 들어간다. 이를 통해서 다양한 명령어를 학습할 수 있어 ctf 를 시작할 때 명령어를 모른다면 거의 필수적으로 한다. Lev.0 man - manual - 정말 중요하다! 명령어에 대한 정보를 알 수 있다. man 명령어 - 명령어에 대한 정보 검색 ssh - Secure Shell - 서버에 접속..

문제 링크 : www.acmicpc.net/problem/20060 문제 여담 : 3년전에 뉴비 시절때 보자마자 무서워서 도망갔다. 쉬운 문제라는데 이런 함수 구현 형태를 접해본적도 없고, 너무 어렵게 느껴졌다. 슬펐었다. 문제 풀이 제일 먼저 생각할 수 있는 것은 첫 글자를 빠르게 찾아야 한다는 것이다. 총 글자의 수는 4가지 이기 때문에 AB,AX를 묶어서 2번 탐색하는 것으로 첫번째 글자를 찾을 수 있다. 일반성을 잃지 않고 A였다고 하자. 이제 우리는 N번의 탐색을 통해 N-1개의 글자를 찾아야 하며, 한번 탐색때 부를 수 있는 단어의 길이는 4N이다. 길이와 횟수가 비슷하기 때문에 1번에 1개의 글자를 알아내는 것을 목표로 해야 한다. 한번의 질문의 대한 답으로 B,X,Y 중 다음글자가 무엇인지..

문제 링크 : www.acmicpc.net/problem/11738 문제 설명 다각형이 삼각분할 되어있다. 모든 선분의 길이는 1이다. 쿼리로 두 점이 주어졌을 때 두 점 사이의 거리를 출력하는 문제이다. 문제 태그 더보기 bfs, dnc, offline query, 재귀 문제 풀이 이 문제를 보면 가장 먼저 $O(NM)$ 의 풀이를 생각할 수 있다. 본인은 n개의 점에서 모두 다익스트라를 돌려서 $O(NMlgN)$의 풀이를 생각했지만 모든 선분의 가중치가 1이기 때문에 모든 점을 시작점으로 해서 각각 bfs를 하는 것으로 $O(NM)$의 풀이가 나오게 된다. 하지만 문제에서 요구하는 시간 복잡도는 제곱 미만이다. 따라서 이 문제의 특성을 관찰해야 한다. 이 문제의 가장 큰 특성은 일반적인 그래프가 아닌..

문제 링크 : www.acmicpc.net/problem/3408 문제 힌트 1. 모든 부분 배열에 대해서 non-boring 한지 확인할 수 있을까? 2. 모든 non-boring 한 배열에는 unique한 원소가 존재한다. 더보기 3. unique 한 원소를 포함한 모든 부분 배열은 non-boring 하다. 4. 순서를 잘 바꿈으로써 시간 복잡도를 만족시킬 수 있다. 문제 풀이 -스포 주의- 더보기 우리의 목표는 모든 부분 배열에 대해서 그 부분 배열이 non-boring 한지를 알아내는 것이다. 이에 앞서 우리는 모든 원소에 대해서 그 원소와 같은 값을 가지는 바로 왼쪽 원소와 오른쪽 원소의 위치를 모든 원소에 대해서 저장하고 있을 것이다. 첫번째로 구간을 배열 전체로 설정하자. 이 배열이 non..