돌이 코딩하는 방

오프라인 다이나믹 커넥티비티 (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..

문제 링크 : www.acmicpc.net/problem/14636 문제 풀이 호드를 위한 돈. 이 문제를 처음보면 꽤나 직관적이라는 것을 알 수 있다. A그룹에서 숫자 쌍 하나, B그룹에서 숫자 쌍 하나를 꺼내 수 차이의 곱을 최대화 시키는 것이다. 여기서 가장 쉽게 생각할 수 있는 것은 A그룹에서는 숫자쌍이 작을 수록 이득이라는 것과 B그룹에서는 숫자쌍이 클수록 이득이라는 것. 즉 A그룹에 (1,3),(2,5)가 있으면 (1,3)이 상위호환이기 때문에 (2,5)는 절때 답을 만들 수 없으며, B그룹에서도 똑같은 방법으로 답이 될 수 없는 숫자 쌍 들을 고를 수 있다. 이렇게 숫자 쌍으로 묶고 나니까 좌표평면이 생각나게 되었다. 숫자 쌍을 좌표평면 상의 점으로 대입해서 생각하게 되면, 문제를 좀 더 직..

문제 링크 : www.acmicpc.net/problem/13361 문제 풀이 이 문제를 풀기 위해서는 아주 간단하지만 핵심적인 관점 바꾸기를 하나 해야한다. '뒤집어서 생각하기' 우리가 구하고자 하는 것은 가장 긴 세로의 길이의 합이다. 근데 이는 전체에서 가장 짧은 가로 길이의 합을 뺀 것과 같다. 만약 이 문제가 같은 길이로도 이어 붙일 수 있었으면 어땠을까? 굉장히 쉬운 문제가 되었을 것이다. 그냥 모든 판을 길이가 짧은 쪽을 가로로 돌린다. 임의의 정수 집합은 같거나 작아지는 순서대로 배치 할 수 있기 때문에 항상 작은 쪽을 가로로 선택해도 조건에 맞게 해결을 할 수 있게 된다. 하지만 본 문제에서는 같은 길이도 선택을 할 수 가 없다. 이 부분이 핵심이고, 따라서 판들을 같은 길이가 존재하는 ..