티스토리

Ryute's Note

검색하기

블로그 홈

Ryute's Note

ryute.tistory.com/m

알고리즘과 Problem Solving, 기타 일상등을 다룹니다.

구독자: 41

방명록 방문하기

주요 글 목록

Sage Installation on WSL2 Disclaimer: I don't know why this works/doesn't work; it is only a result of trial and error. 0. If you didn't install a WSL2, please download and install it(https://learn.microsoft.com/en-us/windows/wsl/install). - You should be aware that you must turn on virtualization on windows and bios. 1. AFAIK installing from conda-forge is best. Download Anaconda(https://www.anaconda.com/) here or somet.. 공감수 0 댓글수 0 2023. 3. 26.
[BOJ] 24973 Up Down Subsequence 문제 요약 길이가 $N$인 수열이 주어진다. 어떤 부분수열을 앞에서부터 읽었을 때 인접한 두 수가 커지면 U, 작아지면 D를 적은 문자열이 있다고 하자. 문자열 $S$가 주어질 때 부분수열을 잘 골라서 만든 문자열과 $S$의 common prefix 길이를 최대화하여라. 문제 풀이 결론부터 말하면, 다음을 반복하면 된다. 1. 문자열을 (연속한 문자 종류, 개수)로 압축한다. 2. 맨 앞이 U면 LIS, D면 LDS를 길이가 그 문자의 개수가 될 때까지 찾는다. 3-1. 만약 찾지 못한다면 LIS나 LDS의 길이(정확히는 길이-1)만큼 추가로 문자를 처리할 수 있고 그 뒤는 불가능하다. 3-2. 만약 찾는다면 연속한 문자를 모두 처리할 수 있다. LIS/LDS의 마지막 위치가 pos라고 하자. 그러면 계.. 공감수 0 댓글수 0 2023. 2. 8.
Resume 올해 진짜 한게 뭐지? 공감수 1 댓글수 1 2023. 1. 8.
[BOJ] 23172 Equivalent Pipeline 문제 링크: [BOJ 23172](https://www.acmicpc.net/problem/23172) 문제 요약 정점이 $n$개인 가중치 있는 트리가 $d$개 있다. $vT(i,j)$를 $T$에서 $i$와 $j$를 잇는 최단경로 중 가중치의 최솟값이라고 하자. 만약 모든 $i$, $j$ 쌍에 대해 이 값이 같다면 두 트리는 동치이다. 동치 관계를 구하여라. 풀이 트리에서 가장 가중치가 작은 간선들을 생각해보자. 이 간선들을 제거하면, 트리가 여러 컴포넌트로 쪼개질 것이다. 이때 같은 컴포넌트에 있는 정점들끼리의 $vT(i,j)$ 값은 반드시 최소 가중치보다 크고, 다른 컴포넌트에 있는 정점들끼리의 값은 정확히 최소 가중치일 것이다. 따라서 두 트리가 동치이려면 최소 가중치 간선들을 기준으로 쪼갰을 때 .. 공감수 0 댓글수 0 2022. 11. 25.
[BOJ] 16711 Erasing Matrix 문제 링크: [BOJ 16711](https://www.acmicpc.net/problem/16711) 문제 요약 격자가 있다. 격자에서 인접한 두 수를 골라 임의의 수를 더할 수 있다. 격자 안의 수가 항상 음수가 되지 않게 하면서 최종적으로 모든 수가 0이 되게 하는 방법을 찾아라. 풀이 일단 가장 먼저 생각해봐야 할 점은 -1을 찍을 조건이다. 이런 식으로 격자에서 인접한 두 수를 고려하는 문제는 특성상 체스판처럼 색칠하면 이분 그래프 구조가 나오는데, 이를 활용해 볼 수 있다. 인접한 두 수에 어떤 수를 더하더라도 (흰 칸의 수 합) - (검은 칸의 수 합)은 변하지 않으므로, 이 두 값은 반드시 같아야 한다. 만약 이 값이 같다면 항상 0으로 만들 수 있을까? 가능하다. 핵심은 같은 색깔이라면 .. 공감수 1 댓글수 0 2022. 11. 25.
[BOJ] 17434 도로 청소 문제 링크: [BOJ 17434](https://www.acmicpc.net/problem/17434) 문제 요약 무방향 그래프가 있다. 교집합이 없고 방문하는 간선의 합집합이 그래프 간선 전체인 오일러 투어 2개를 구하여라. 풀이 풀이 방향을 잘못 잡으면 구데기같은 구현에 고통받게 된다. 일단 가장 먼저 생각해야 하는 건, 그래프의 홀수 차수 점 개수는 반드시 0, 2, 4중 하나여야한다는 것이다. 오일러 투어를 하나 구하고 그 간선들을 모두 제거한다고 생각해보자. 그러면 오일러 순환인 경우 홀수 차수 점 개수는 그대로고 아니라면 2개 줄어든다. 모두 지웠을 때 개수가 0이어야 하므로 이 셋 중 하나이다. 홀수점 0개 아무 오일러 순환을 하나 찾자. 그 뒤 아무데서나 적당히 끊어서 오일러 투어 2개로 .. 공감수 0 댓글수 0 2022. 11. 25.
Google SWE Intern 생존기 (1) Intro 이제 막 구글에 입사한지 2주를 채워갑니다. 첫 회사생활이라 정말 걱정 많이 했는데 시작을 이런 좋은 회사에서 할 수 있어서 매우 행운이라고 생 각합니다. 궁금해하시는 분들이 있을까봐 자세히 적지는 못하더라도 간단하게 이것저것 적어보려고 합니다. Team & Work 구글에 많은 팀들이 있는데, 구글 코리아에도 그 중 일부가 있습니다. 구글 검색을 담당하는 서치 팀, 그리고 머신러닝에 주로 사용되는 프레임워크인 텐서플로우 팀 중에서 하나를 골라야 했는데 작년에 서치 팀에서 인턴 하셨던 대학 선배님이 강력하게 추천해주셔서 서치 팀으로 팀 매칭하게 되었습니다. 업무는... 하드코어합니다. 일단 알고리즘만 하다 보니 개발에 대해서 완전 문외한이고, 심지어 그나마 조금 했던 개발도 백엔드였습니다. 그.. 공감수 13 댓글수 3 2022. 7. 8.
Google SWE Intern 지원부터 오퍼까지 Intro 이번 여름방학에, 6월 말부터 9월 중순까지 구글 코리아에서 SWE 인턴으로 근무하게 되었습니다. 첫 회사 생활이라 무섭기도 하고, 반면에 매우 기대되기도 하네요. 입사까지 약 두달 반정도 남았는데, 그동안 구글 기대하느라 학점을 망칠 것 같아서 조금 불안하기도 합니다만;; 어쨌던 간에 인터넷을 찾아보니 타 직군에 대한 인턴 후기는 꽤 많았는데 SWE 인턴 지원 후기는 거의 없어서 이것저것 짧게 적어봅니다. Main 작년에 아는 대학교 선배 분이 구글 인턴 한번 지원해보지 않겠냐고, 레퍼럴을 써주실 수 있는 분을 안다고 해서 이번 여름에는 되던 안되던 구글 인턴을 한 번 넣어봐야지 생각하고 있었습니다. 사실 그렇게 생각하고 있다가도 그냥 까먹고 있었는데, 선배님이 remind를 해 주셔서 시기.. 공감수 7 댓글수 10 2022. 4. 14.
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$는 .. 공감수 0 댓글수 0 2021. 8. 18.
[BOJ] 20093 Coins 문제 설명 $8 \times 8$ 크기의 체스보드가 있습니다. $A$와 $B$가 이 위에서 게임을 합니다. 각 체스보드에는 동전이 하나씩 올려져 있고, 처음 상태는 무작위입니다. $A$는 동전을 최대 한 개 뒤집어서, $0$ 이상 $63$ 이하의 정수 하나를 체스보드만 보고 $B$가 알 수 있게끔 해야 합니다. $A$와 $B$의 전략을 직접 구현해 제출하는 투 스텝 문제입니다. 문제 관찰 서브태스크 1 동전을 하나 뒤집을 수 있다는 건, 원하는 위치의 동전을 위 또는 아래로 정확히 맞출 수 있다는 것과 동치입니다. 따라서 0번 위치의 동전을 잘 뒤집어 주면 됩니다. 서브태스크 4 서브태스크 1과 비슷한 느낌으로 접근합시다. $A$가 $B$에게 전달해야 하는 정보는 정확히 6비트어치입니다. 따라서 6개의 .. 공감수 0 댓글수 0 2021. 5. 26.
[BOJ] 19677 Holy cow, Vim! (Hard) 문제 설명 생략한다. 문제 접근 이 문제를 풀기 위해서는 굉장히 많은 시행착오를 거쳐야 한다. 아래는 그 시행착오를 줄이기 위한 접근들을 단계별로 서술해놓았다. 그러나 이를 보지 않고 많은 시행착오를 겪는 것이 거의 모든 측면에서 도움이 될 것으로 보인다. 일단 lexicographical하게 정렬했을 때 명령어의 순서는 '*', '+', '-', '/', 'dup', 'input', 'jump', 'pop', 'print', 'push' 순서이다. 문제는 이 중 사칙연산과 dup은 우선순위도 빠르면서 스택에 필수적으로 하나 이상의 원소를 요구하기에, 두 명령어 .. 공감수 0 댓글수 0 2021. 4. 8.
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.. 공감수 1 댓글수 0 2021. 3. 17.
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등을 했습니다. 일반적으로는 팀원들이 잘 해 주어서 좀.. 공감수 0 댓글수 0 2021. 3. 15.
지옥에서 돌아온 참깨라면 레시피 1. 물 500ml 정량보다 조금 더(약 50ml) 맞춘다(짠 걸 싫어하면 50ml를 더 추가한다). 분말스프 전부와 소고기 다시다 한 티스푼 가득 넣고 끓인다. 다시다를 안 넣어도 맛에 큰 차이가 없긴 하다만 넣는게 더 낫다. 넣지 않는다면 물 500ml 정량을 넣는다. 2. 물이 완전히 끓으면 면을 넣고 정확히 2분 10초 끓인다. (꼬들한 걸 좋아하면 10초정도 덜 끓인다.) 3. 면을 그릇에 덜고, 불을 끈다. 그리고 계란 하나와 계란 블럭을 넣는다(계란 블럭은 면 끓을 때 미리 넣어도 무방하다). 다시 불을 켜고 2분 10초 끓인다. 이때 계란은 풀면 안 되고, 계란 블럭은 푼다. 반숙이 좋거나 싫으면 그만큼 시간을 조절한다. (반숙 기준 2분 10초, 완숙 기준 2분 50초 넘게 끓여야 한다... 공감수 3 댓글수 1 2021. 2. 13.
정보올림피아드 / 알고리즘 과외 안 구합니다. 알고리즘 과외 안 합니다 현재 고려대학교 컴퓨터학과 재학 중인 김준겸입니다. 알고리즘 사이트에서는 ryute라는 닉네임을 사용 중입니다. 약 8년 정도의 알고리즘 문제 해결 경력이 있습니다. 알고리즘, 그 중에서도 특히 정보올림피아드 분야 과외를 하고자 합니다. Zoom과 Visual Studio Live를 통한 화상 과외를 주로 받습니다. 모든 세부사항은 상담을 통해 조정이 가능하니, 부담 갖지 마시고 연락 주시길 바랍니다. 코딩 테스트 수준의 과외는 별도의 특이사항이 없는 한 당분간 받지 않으려고 합니다. 연락을 많이 주시는데 받지 못해 죄송합니다. 새로 이메일 주시면 과외 다시 진행하게 될 때 먼저 연락드리겠습니다. 당분간 과외를 받지 않습니다. 어떤 일이 있어도 과외를 해야겠다 싶은 경우에만 연락.. 공감수 7 댓글수 1 2021. 2. 4.
[Crypto] 해시 함수와 취약점 (Basic) Intro 이 글에서는 비교적 간단한 해시 함수에 대해서 다루고, Crypto 분야 CTF를 기준으로 할 때 이러한 해시 함수에서 나타날 수 있는 초보적인 취약점에 대해 서술한다. 구체적으로, 이 글에서는 MD5와 SHA 계열 해시에 대해서 다룬다. What is Hash? 해시 함수는 임의의 입력을 받아, 이를 고정된 크기의 출력으로 매핑하는 함수이다. 해시 함수는 일반적으로 같은 입력에 대해서 항상 같은 출력을 내기 때문에 두 데이터가 같은지를 빠르게 비교하거나 데이터를 저장하여 검색하기 위해 색인할 때 유용하게 활용할 수 있다. 그러나 해시 함수의 값이 같다고 해서 실제 데이터가 같다고 간주할 수는 없다. 이는 비둘기집의 원리 때문으로, 입력의 크기는 무한하지만 출력의 크기는 유한하기 때문에 동일한.. 공감수 4 댓글수 1 2021. 1. 20.
[*CTF Writeup] Crypto - MyEnc 문제 설명 from Crypto.Util.number import getPrime,bytes_to_long import time,urandom from flag import flag iv=bytes_to_long(urandom(256)) assert len(flag)==15 keystream=bin(int(flag.encode('hex'),16))[2:].rjust(8*len(flag),'0') p=getPrime(1024) q=getPrime(1024) n=p*q print "n:",n cnt=0 while True: try: print 'give me a number:' m=int(raw_input()) except: break ct=iv for i in r.. 공감수 1 댓글수 0 2021. 1. 18.
[*CTF Writeup] Crypto - GuessKey2 문제 설명 from random import randint import os from flag import flag N=64 key=randint(0,2**N) # print key key=bin(key)[2:].rjust(N,'0') count=0 while True: p=0 q=0 new_key='' zeros=[0] for j in range(len(key)): if key[j]=='0': zeros.append(j) p=zeros[randint(0,len(zeros))-1] q=zeros[randint(0,len(zeros))-1] try: mask=int(raw_input("mask:")) except: exit(0) mask=bin(mask)[2:] .. 공감수 0 댓글수 0 2021. 1. 18.
[Crypto] 디피 헬만 (Diffie-Hellman) 알고리즘과 취약점 Intro 디피 헬만(Diffie-Hellman) 키 교환은 이산 로그(Discrete Log) 문제의 어려움에 기반한 키 교환 방식이다. 이 글에서는 디피 헬만 키 교환의 동작 원리와, 그리고 동작 과정에서 잘못 구현될 수 있는 부분들의 후보를 간략하게 나열함으로서 디피 헬만 알고리즘의 취약점을 공격하려는 초보 크립토그래퍼에게 도움을 주려고 한다. 작동 과정과 원리 디피 헬만 키 교환은 공개된 통신 위에서, 두 사람이 다른 사람은 알지 못하고 둘만이 아는 공유된 정보(Shared Secret)을 갖도록 하는 방법이다. 이 알고리즘을 이해하기 위해서는 간단한 대수적 지식이 필요하다. 기본적으로 덧셈과 곱셈이 정의되었을 때 모듈러 $n$에 대한 수의 집합 $0, 1, 2, \dots , n-1$은 환(Ri.. 공감수 4 댓글수 0 2021. 1. 13.
USACO 2020 Open contest Gold 풀이 Intro PS를 거의 한달간 접었었는데, 올해 ICPC를 나갈 수 있다는 희망이 보여서 급하게 PS 재활 중입니다. 최대한 빨리 플래티넘을 안정적으로 해결할 수 있는 실력까지 올렸으면 좋겠네요. 가능할지는 아직 미지수입니다. 이 셋 푸는데도 두시간은 넘게 걸렸으니 미래가 어둡네요 :( 18874 Haircut 문제 링크 : https://www.acmicpc.net/problem/18874 문제를 요약하면 각 $j$에 대해 $j$보다 큰 수열의 원소들이 정확히 $j$로 바뀔 때, 수열의 inversion을 구하는 문제입니다. 이런 문제에서 흔히 나오듯이 $j$를 큰 수부터 작은 수까지 움직이면서 차례대로 구해봅시다. 수열의 inversion은 수열의 각 원소 $a_i$에 대해 인덱스가 $i$보다 작으면.. 공감수 0 댓글수 0 2021. 1. 4.
(임시) 2020 ICPC Seoul Regional 후기 * 페이스북에 올린 것을 급하게 그대로 올립니다. 14일날 있었던 Seoul Regional과, 그리고 리저널을 치기 위해서 노력했던 시간들에 대해 짧은 후기글을 올립니다. (긴 후기는 나중에 블로그에 올라올 것 같습니다.) 두서가 좀 없어도 이해해 주세요. 저희 팀은 결성된 지 상당히 오래 된 팀입니다. 올해 1월에 만들어졌고, 그때부터 팀연습을 몇 번 했던 것 보면 태생이 빡겜을 하기 위해 만들어진 팀이었던 것 같습니다. 저 또한 재수하려고 마음을 먹었다가 이 팀 구성이면 Semi-World Final에는 무조건 진출하겠다고 생각이 들어서 재수를 포기하고 PS를 계속 했습니다. 결과적으로 좋은 성적을 냈으니 옳은 선택이었다고 생각합니다. 사실 저희 팀이 객관적으로 잘하는 팀이다 말하기는 아직도 힘들다.. 공감수 0 댓글수 2 2020. 11. 17.
Random Problem Solving 1 Intro 정말 PS를 하고 싶었기 때문에, 몇 문제를 풀었다. 잘 푼 문제도 있고 그렇지 못한 문제도 있지만, 어쨌던 간에 풀었던 문제들의 기록을 간단하게나마 남길까 한다. 20045 Trading System 먼저 다음과 같은 값을 찾는다. 구간합이 $x$ 이상인 구간의 개수가 $k$ 이상인 가장 큰 $x$ 이 값을 찾아야 하는 이유는, 이 값을 찾는다면 실제 수열은 $x+1$ 이상인 구간합을 모두 set을 이용해서 찾아 준 다음 나머지를 $x$로 채우는 방식으로 역추적해낼 수 있기 때문이다. 따라서 이 값을 찾는 것이 답을 구하는 것과 동치이고, 이 정도 문제를 해결할 수준이라면 이 과정은 매우 쉬우므로 설명은 생략할 것이다. 이 값은 $x$에 대한 Parametric Search로 찾아줄 수 있다.. 공감수 1 댓글수 2 2020. 10. 16.
[BOJ] 17524 Dryer 문제 링크 : www.acmicpc.net/problem/17524 문제 풀이 가장 먼저 해야 하는 관찰은 다음과 같다. $t_i$가 같은 옷이 2개 있다면 어차피 $w_i$가 큰 쪽이 더 오래 걸릴 것이기 때문에, 같이 넣고 말려도 무방하다. 따라서 의미 있는 옷은 각 $t_i$에 대해서 유일하므로, $1\le N\le61$과 사실상 같다. 그 다음으로 해야 하는 관찰들은 다음과 같다. 어떤 옷들의 집합을 같은 건조기에 넣고 돌린다면, 그 건조기의 온도는 반드시 옷 중 $t_i$의 최솟값과 같아야 한다. 이는 매우 자명하다. 어떤 건조기가 이미 $x$초 동안 돌아간다면, $x$초 이하를 소모하는 다른 옷을 끼워 넣어도 상관없다. $k=3$일때만 해결하면 그 아래는 쉽게 해결할 수 있으므로 이 경우에 대.. 공감수 1 댓글수 0 2020. 10. 11.
[SCPC] 2020 1차 예선 풀이 Intro대충 4시간 정도 때려 박아서 1~4번에서 만점을 받았고, 5번은 문제만 읽었습니다. 예전 SCPC 기출에 비해서는 확실히 난이도가 균일해진 것 같습니다(https://newdeal123.tistory.com/61 참조 요망). 제가 예상하는 Solved.ac 티어 난이도는 다음과 같습니다.다이어트 (Silver 3)카드 게임 (Platinum 3)사다리 게임 (Platinum 3)범위 안의 숫자 (Platinum 2)우범 지역 (Diamond 2~3?)1. 다이어트다음과 같이 생각해봅시다. 일단 자명히 두 식단에서 칼로리가 낮은 순으로 K개만 먹어야 한다는 것을 알 수 있습니다. 이때 식단 A의 가장 큰 칼로리를 가지는 식사는 B의 어떤 식사랑 매칭시켜야 할까요? 당연히 B의 가장 작은 칼로리.. 공감수 0 댓글수 0 2020. 8. 22.
[ICPC] Latin America Regional 2017 일부 문제 풀이 A. Arranging Tiles BOJ 15052번: https://www.acmicpc.net/problem/15052 이 문제의 핵심은, 어떤 2개의 다각형을 얼마나 가까이 붙일 수 있는 지 빠르게 계산하는 것입니다. 다각형을 배열하는 순서를 정하고, 그 다각형들에 대해 한 다각형의 x좌표 최댓값이 바로 다음 다각형의 x좌표 최솟값과 같게 배치했다고 합시다. 그렇다면 이 때의 해는 모든 다각형의 x축 길이 합에서, 모든 인접한 다각형 쌍에 대해서 다각형을 얼마나 가까이 이동시킬 수 있는지의 합을 뺀 것이 됩니다. 따라서 우리는 다각형 쌍이 주어졌을 때 이를 서로 붙일 수 있는 최대 길이를 미리 계산해 둔 뒤 가능한 모든 배열에 대해 해 중 최소를 찾아주면 됩니다. 붙일 수 있는 최대 길이를 모두 전.. 공감수 3 댓글수 0 2020. 8. 13.
[BOJ] 15404 Divide and Conquer 문제 요약 $N$개의 정점이 있고, 이 정점을 잇는 스패닝 트리가 2개 있다. 이 두 스패닝 트리의 합집합으로 구성되는 그래프에 대해(간선은 구별된다), $K$개의 간선을 제거하면 그래프를 연결 그래프가 아니도록 할 수 있다. 이 때 $K$의 최솟값을 구하고, 그 경우의 수를 $10^9 + 7$로 나눈 나머지를 출력하면 된다. 문제 풀이 가장 먼저 해야 하는 관찰은 다음과 같다. $K=2$이거나, $K=3$. 증명은 다음과 같다. 임의의 정점에 연결된 모든 간선을 제거하면 그 정점은 다른 정점과 연결되어 있지 않기에, 그래프는 연결 그래프가 아니다. 따라서 $K$는 모든 정점의 degree 중 최솟값보다 클 수 없다. 간선 하나는 정확히 두 개의 정점의 degree를 1만큼 증가시키므로, 모든 정점의 d.. 공감수 0 댓글수 0 2020. 8. 10.
2020 숭고한 Marathon 참가 후기 Intro 원래는 Advanced Division에 참가하려고 했었는데, 팀노트를 만들기 귀찮았고 무엇보다 자신이 작성해둔 코드라도 인터넷 검색에 걸리면 표절이라는 룰이 있었기 때문에 굳이 참가할 이유를 못 찾았습니다. ALPS는 Contest나 Marathon에서 한 문제 이상 해결하면 회비를 면제해주기도 했고, thak00는 이기고 싶었기 때문에 정확히 thak00보다 한문제 더 풀려고 노력했습니다. 여담으로 이번에 domjudge를 처음 써 봤는데 CMS에 비해 매우 별로였습니다. CMS가 최고다! 마지막 두 문제 빼고는 전부 해결했습니다. M은 디버깅 코드를 안 빼고 제출한 관계로 대회 중에는 WA로 기록되어 있습니다. 각 문제를 해결하면서 느낀 점과 셋 구성, 디스크립션에 대해 잡설을 풀어보려고.. 공감수 0 댓글수 2 2020. 7. 20.
개인적인 웹툰 몇줄 감상 * 너무 유명한, PC 기준 순위 5위권 즈음에 들어가는 웹툰들은 과감히 제외하고 선정합니다. * 보는 웹툰 중에서도 이건 한번씩 볼만하다 싶은 작품들을 선정했습니다. * 글쓴이의 취향은 상당히 마이너합니다. 꿈의 기업 드림 코퍼레이션이라는 의문의 회사에 취직한 사람들과, 그들이 살았던 도시, 그리고 한 인공지능의 이야기. 물론 스릴있고 흥미롭지만 무엇보다도 생각을 많이 하게 해 주는 작품. 긴 이야기 호흡에도 지치지 않을 자신이 있다면 시도해볼 가치가 충분하다. 고삼무쌍 이세계가 아닌 현세계에서 고등학생이 깽판치는 웹툰. 빠르고, 호쾌한 B급감성 신세대 무협. 이제는 무협도 따분하게 보지 않을 수 있다. 색다른 판타지 웹툰이 필요했거나, 아니면 요즘 살기가 좀 팍팍해서 큰 웃음이 필요한 사람들에게. 닥.. 공감수 1 댓글수 0 2020. 5. 28.
[BOJ] 16910 mex와 쿼리 [문제 링크](https://www.acmicpc.net/problem/16910) 문제 요약 다음과 같은 세 쿼리를 처리해야 합니다. [l,r]에 속하는 모든 자연수를 배열 A에 추가한다. 이미 있는 수는 무시된다. [l,r]에 속하는 모든 자연수를 배열 A에서 제거한다. 없는 수는 무시된다. [l,r]에 속하는 모든 자연수에 대해 있으면 제거, 없으면 추가한다. 각 쿼리를 수행 한 뒤에 이 배열에 없는 수 중 가장 작은 자연수를 찾으면 됩니다. 문제 풀이 일단 문제에서 요구하는 좌표가 크니 좌표 압축을 시도하고 생각합시다. 그 이후 Lazy Propagation 달려 있는 세그로 연산을 처리해주며 특정 구간에 존재하는 수의 개수를 세 주면 됩니다. Lazy 연산 중에 1번 쿼리와 2번 쿼리는 서로 상.. 공감수 0 댓글수 1 2020. 3. 22.
[BOJ] 14591 KUBC League, 17165 Gosu 14591 KUBC League 문제 요약 토너먼트 그래프가 있다. 1번 정점에서 시작해서 모든 정점을 순회하는 단순 경로를 찾으면 된다. 문제 풀이 DFS 스패닝 트리에 의거하여, 그냥 DFS를 1번 정점에서부터 수행 후 마지막부터 출력해주면 된다! 코드 #include #include #include #define all(x) (x).begin(), (x).end() #define endl "\n" #define ends " " #define pb(x) push_back(x) #define fio() ios_base::sync_with_stdio(0); cin.tie(0) using namespace std; typedef long long ll; typedef pair pii; typedef pai.. 공감수 0 댓글수 0 2020. 3. 22.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.