본문 바로가기

분류 전체보기

 (78)
Random Problem Solving 2 10650 Marathon 다음과 같은 두 배열을 관리하자. $\text{next}[i]$ : $i$번째 좌표에서 $i+1$번째 좌표로 이동하는 거리 $\text{save}[i]$ : $i$번째 좌표를 달리기 중 생략하기로 결정했을 때 절약하는 거리 그러면 쿼리 $Q$는 다음과 같이 해결할 수 있다. $s$에서 $e$까지 이동해야 하면, $\displaystyle \sum_{i=s}^{e-1} \text{next}[i] - \max_{s + 1 \le i \le e - 1} \text{save}[i] $ 가 답이 된다. 따라서 $\text{next}$는 부분 합 세그먼트 트리, $\text{save}$는 부분 최대 세그먼트 트리를 이용해서 관리해주면 $O(\log N)$에 찾을 수 있다. 쿼리 $U$는 ..
[BOJ] 20093 Coins 문제 설명 $8 \times 8$ 크기의 체스보드가 있습니다. $A$와 $B$가 이 위에서 게임을 합니다. 각 체스보드에는 동전이 하나씩 올려져 있고, 처음 상태는 무작위입니다. $A$는 동전을 최대 한 개 뒤집어서, $0$ 이상 $63$ 이하의 정수 하나를 체스보드만 보고 $B$가 알 수 있게끔 해야 합니다. $A$와 $B$의 전략을 직접 구현해 제출하는 투 스텝 문제입니다. 문제 관찰 서브태스크 1 동전을 하나 뒤집을 수 있다는 건, 원하는 위치의 동전을 위 또는 아래로 정확히 맞출 수 있다는 것과 동치입니다. 따라서 0번 위치의 동전을 잘 뒤집어 주면 됩니다. 서브태스크 4 서브태스크 1과 비슷한 느낌으로 접근합시다. $A$가 $B$에게 전달해야 하는 정보는 정확히 6비트어치입니다. 따라서 6개의 ..
[BOJ] 19677 Holy cow, Vim! (Hard) 문제 설명 생략한다. 문제 접근 이 문제를 풀기 위해서는 굉장히 많은 시행착오를 거쳐야 한다. 아래는 그 시행착오를 줄이기 위한 접근들을 단계별로 서술해놓았다. 그러나 이를 보지 않고 많은 시행착오를 겪는 것이 거의 모든 측면에서 도움이 될 것으로 보인다. 일단 lexicographical하게 정렬했을 때 명령어의 순서는 '*', '+', '-', '/', 'dup', 'input', 'jump', 'pop', 'print', 'push' 순서이다. 문제는 이 중 사칙연산과 dup은 우선순위도 빠르면서 스택에 필수적으로 하나 이상의 원소를 요구하기에, 두 명령어 ..
Newbie Cryptography Cheatsheet (작업 중) $$ \newcommand{\Mod}[1]{\ (\mathrm{mod}\ #1)} $$ Intro CTF 도중에 꺼내서 보고 싶은 내용들이 적혀있는 치트시트가 있었으면 좋겠다고 생각했는데, 크립토를 접었음에도 쓰면서 공부하면 괜찮을 것 같아서 매우 바쁜 와중에도 짬짬히 적고 있다. 내 생각엔 그냥 rkm0959 블로그를 열심히 베끼고 있는 것 같다 ㅋㅋ(본인이시라면 뒤로 가기를 눌러 주세요). 이 내용을 실제 공부용이나 CTF용으로 사용하는 것을 강력히 추천하지 않는다. RSA Introduction 크기가 비슷한 큰 소수 $p, q$가 있을 때, $N=pq$라 하자. 이때 공개된 $e$에 대해 $ed \equiv 1 \Mod{\phi(N)}$인 $d$가 존재하도록 하면 오일러 정리에 의거하여 $C \e..
UTCTF - Writeups I participated in UTCTF as a team Hyp3rFlow and achieved 18th place. Usually, I felt like I was always get along with hard-working team members, but this time - I think I solved enough, so I'm going to post a write-up of problems that I solved. Please understand that grammar can be awkward because it's my first time writing in English. 이번 UTCTF에 팀 Hyp3rFlow로 참가해서 18등을 했습니다. 일반적으로는 팀원들이 잘 해 주어서 좀..
지옥에서 돌아온 참깨라면 레시피 1. 물 500ml 정량보다 조금 더(약 50ml) 맞춘다(짠 걸 싫어하면 50ml를 더 추가한다). 분말스프 전부와 소고기 다시다 한 티스푼 가득 넣고 끓인다. 다시다를 안 넣어도 맛에 큰 차이가 없긴 하다만 넣는게 더 낫다. 넣지 않는다면 물 500ml 정량을 넣는다. 2. 물이 완전히 끓으면 면을 넣고 정확히 2분 10초 끓인다. (꼬들한 걸 좋아하면 10초정도 덜 끓인다.) 3. 면을 그릇에 덜고, 불을 끈다. 그리고 계란 하나와 계란 블럭을 넣는다(계란 블럭은 면 끓을 때 미리 넣어도 무방하다). 다시 불을 켜고 2분 10초 끓인다. 이때 계란은 풀면 안 되고, 계란 블럭은 푼다. 반숙이 좋거나 싫으면 그만큼 시간을 조절한다. (반숙 기준 2분 10초, 완숙 기준 2분 50초 넘게 끓여야 한다...
정보올림피아드 / 알고리즘 과외 안 구합니다. 알고리즘 과외 안 합니다 현재 고려대학교 컴퓨터학과 재학 중인 김준겸입니다. 알고리즘 사이트에서는 ryute라는 닉네임을 사용 중입니다. 약 8년 정도의 알고리즘 문제 해결 경력이 있습니다. 알고리즘, 그 중에서도 특히 정보올림피아드 분야 과외를 하고자 합니다. Zoom과 Visual Studio Live를 통한 화상 과외를 주로 받습니다. 모든 세부사항은 상담을 통해 조정이 가능하니, 부담 갖지 마시고 연락 주시길 바랍니다. 코딩 테스트 수준의 과외는 별도의 특이사항이 없는 한 당분간 받지 않으려고 합니다. 연락을 많이 주시는데 받지 못해 죄송합니다. 새로 이메일 주시면 과외 다시 진행하게 될 때 먼저 연락드리겠습니다. 당분간 과외를 받지 않습니다. 어떤 일이 있어도 과외를 해야겠다 싶은 경우에만 연락..
[Crypto] 해시 함수와 취약점 (Basic) Intro 이 글에서는 비교적 간단한 해시 함수에 대해서 다루고, Crypto 분야 CTF를 기준으로 할 때 이러한 해시 함수에서 나타날 수 있는 초보적인 취약점에 대해 서술한다. 구체적으로, 이 글에서는 MD5와 SHA 계열 해시에 대해서 다룬다. What is Hash? 해시 함수는 임의의 입력을 받아, 이를 고정된 크기의 출력으로 매핑하는 함수이다. 해시 함수는 일반적으로 같은 입력에 대해서 항상 같은 출력을 내기 때문에 두 데이터가 같은지를 빠르게 비교하거나 데이터를 저장하여 검색하기 위해 색인할 때 유용하게 활용할 수 있다. 그러나 해시 함수의 값이 같다고 해서 실제 데이터가 같다고 간주할 수는 없다. 이는 비둘기집의 원리 때문으로, 입력의 크기는 무한하지만 출력의 크기는 유한하기 때문에 동일한..

티스토리툴바