돌이 코딩하는 방

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

원래는 codejam 후기를 잘 작성하지는 않지만, 요즘 블로그 글을 잘 안쓰기도 했고,코포를 안한지는 거의 반년이 되어간다. 그래서 cp의 감을 되살리고자 codejam 1A를 했던 후기를 간단하게 작성하려고 한다. 2라운드로 가기 위해서는 3번의 기회 중 한번 만 1500등 안에 들면 된다. 사실 한동안 codeforces도 안치고 cf에 대한 자신감이 많이 하락한 상태여서 보기가 B나 C로 미루려고 했지만, 시험기간이 씨게 겹칠것 같아서 어쩔 수 없이 A에서 통과를 하려고 마음먹었다. 1번 문제를 봤다. 문제를 읽으면서 거의 바로 만점 풀이가 떠올랐고, 그리디 + 구현으로 풀 수 있는 문제라고 생각했다. 근데 구현이 string을 써야 했고, 케이스도 많이 나누고 예외 처리도 해야될 것 같았다. 1..

오프라인 다이나믹 커넥티비티 (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 중 다음글자가 무엇인지..

최근에 바키라님의 이 글을 보게 되었는데 정말 많이 공감이 되었습니다. 많이 경험해 보고, 고민하고 있던 부분을 잘 짚어주셨습니다. 그래서 이 기회에 저도 제 블로그를 찾아주시는 고마운 방문객들께 2가지 부탁을 해보고자 합니다. 첫번째, 피드백 글에 대한 피드백을 남겨주세요. 이 부분이 읽기 힘들었다. 이 부분에 그림등을 첨부해 설명이 있었으면 좋겠다. 이 부분의 내용이 틀린 것 같다. 등의 피드백은 언제나 감사히 받겠습니다. 작년에 질문한 친구에게 블로그를 보여주면서 코사라주 알고리즘이 어떤 식으로 진행이 되는 건지 설명했는데, 조금 이따 그 친구가 뭔가 이상하다면서 다시 질문했습니다. 알고보니까 스택에 노드를 넣는 시점을 방문 완료가 아닌 노드에 방문한 즉시 넣는 것으로 설명이 되어있었습니다. 바로 ..

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

서론 내 지인 중 더 지니어스를 굉장히 좋아하고 굉장히 머리 좋은 분이 한 분 있다. 내가 다니는 동안 그 형이 학교 내부 더 지니어스를 3번이나 개최했고, 퀄리티도 굉장히 훌륭했다. 나도 거의 모든 회차를 외운 애청자로서 참가를 했고, 2번 준우승과 1번 우승을 하였다. 이번에는 그 형이 다른 사람들과 함께 좀 큰 규모의 지니어스인 "Fanatic Genius"를 개최하고 있다. 그 중 5회전에서는 딜러들의 지인들이 게스트로 참여하게 되었고, 그렇게 나는 기회를 잡을 수 있었다. 후기를 그렇게 잘 작성하는 것도 아니고, 기억력이 그렇게 좋은지도 모르겠고, 플레이어도 처음 봤기 때문에 굉장히 헷갈렸다. 쓰고 싶어서 기억에 의존해서 쓰기는 하지만 정확하지 않을 수도 있다는 점 미리 양해를 구합니다. 규칙 ..

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