-
PS 20220220-20220223
목차 1. BOJ8217 유성 2. BOJ16074 Mountaineers 3. BOJ5542 JOI 국가의 행사 4. BOJ13361 최고의 대장장이 토르비욘 5. BOJ16977 히스토그램에서 가장 큰 직사각형과 쿼리 6. BOJ13208 승현이와 승현이 BOJ8217 유성 PBS 문제이다. $x$ 일에 목표를 달성했다면 $x<y$인 임의의 $y$에 대해 $y$일에도 목표가 달성된 상태임이 보장된다. 따라서 매일의 운석 수를 빠르게 online으로 관리해주며 이분탐색 해주면 시간복잡도를 줄일 수 있다. 이때 매일의 운석 수를 빠르게 관리하는 것은 세그먼트 트리 혹은 펜윅 트리를 활용할 수 있는데, PBS 자체가...
yubin.choi's profile image최유빈(yubin.choi)
2022-02-23 20:00
-
[BOJ14437] 준오는 심술쟁이!!
BOJ14437 DP 연습용 문제입니다. 출력은 문자열을 구성하는 문자 자체에는 관계 없이, 오직 문자열의 길이에 영향 받습니다. 본 문제는 앞에서부터 $i$번째 문자를 바꾼 횟수가 $a_i$일 때 $\displaystyle\sum_{i=1}^{l}a_i = s$를 만족하는 0 이상 25 이하의 정수 $a_1,a_2,a_3,\cdots,a_l$의 경우의 수를 구하는 것과 같습니다. 따라서, 길이가 $l$인 문자열을 바꾼 수의 합이 $s$가 되도록 하는 경우의 수를 1,000,000,007로 나눈 나머지를 $DP(l,s)$라 하면 다음의 식이 성립합니다. \[DP(l,s) = \sum_{k=0}^{\min(25,s)} DP(l-1,s-k)\] 또한 위 식을 만족하도록 $DP(0,k)$를 정의하면 $k=0$일 때 1, 그렇지 않을...
yubin.choi's profile image최유빈(yubin.choi)
2021-12-28 23:00
-
CryptoHack - Elliptic Curves : Double And Broken Writeup
LOCKED PAGE
yubin.choi's profile image최유빈(yubin.choi)
2021-12-21 00:00
-
Extension of FLT to Matrix base
Extension of FLT to Matrix base / 페르마 소정리의 행렬로의 확장 1. 다항식의 곱셈과 행렬 다항식은 수 사이의 관계를 표현하며, 다항식의 계수만을 적어 다항식을 벡터로 표현할 수 있습니다. 다항식을 곱하면 새로운 다항식으로 전이되며 벡터에 행렬을 곱하면 새로운 벡터로 전이된다는 사실을 생각해보면 다항식의 곱셈을 행렬로 표현하는 것이 새로운 관찰을 제공할 수 있을 듯 합니다. 우선 다음과 같이 다항식 $f$와 벡터 $v$를 대응시켜봅시다. \[f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0 \\ v =...
yubin.choi's profile image최유빈(yubin.choi)
2021-12-18 12:00
-
Efficient Calculation of Linear Homogeneous recurrence with Matrix power
1. 선형 동차 점화식이란 What’s the Linear Homogeneous recurrence 수열의 점화식이 아래와 같이 표현될 때 $g(n)=0$이면 선형 동차점화식, $g(n)\ne0$이면 선형 비동차점화식이라고 한다. \(a_{n+k} = g(n)+\sum_{i=0}^{k} c_ia_{n+i}\) 이때 $k$를 점화식의 차수(order)라고 한다. 2. 간단한 경우의 계산 Calculation for a simple case 간단하게 $a_{n+2}=\alpha a_{n+1}+\beta a_n$인 경우를 생각해보자. $a_{n+3} = a_{n+2} = \alpha^2a_{n+1}+(\alpha\beta+\beta)$이라고 표현할 수 있고, 다시 이때의 계수를 $\gamma$와 $\delta$로 정의하면 $a_{n+3}=\gamma a_{n+1}+\delta a_{n}$으로 표현할 수 있다. 즉, 계수가 달라졌을 뿐 수학적으로 근본적인 상황은 계산하고자 하는...
yubin.choi's profile image최유빈(yubin.choi)
2021-12-09 00:00
-
비밀글 기능을 추가했습니다! (비밀번호:1234)
LOCKED PAGE
yubin.choi's profile image최유빈(yubin.choi)
2021-11-16 00:00
-
How JWT RS256 works
서론 Json Web Token(이하 JWT)은 전자 서명을 통해 json의 변조를 방지하는 Claim 기반의 토큰입니다. 이번 글에서는 제가 RS256을 다루면서 한참을 헤맸던 부분을 조금 정리해보고자 합니다. 본 글에서는 Google Colab에서 Python 3.7.12 PyJWT 2.3.0을 사용하여 테스트하였습니다. 결과값이 다르다면 동일한 환경에서 시도해주세요. ### RS256이란 JWT는 크게 header, payload, signature의 세 부분으로 구성됩니다. header은 해당 json이 JWT이며 어떤 알고리즘으로 서명하였는지, payload는 JWT에 담고자 한 내용이, signature은 header와 payload의 정보를 서명한 결과가 URLsafe base64 인코딩되어 담겨있습니다. (마지막의 패딩인 =는...
yubin.choi's profile image최유빈(yubin.choi)
2021-11-01 12:00
-
CakeCTF Cryptography Probs Write-Up
서론 굉장한 버스를 탔던 대회이다. 그럼에도 뉴비 키워준다는 느낌으로 가이딩을 많이 해주셔서 혼자서라면 꽤 많이 삽질했을 법한 부분도 수월하게 넘길 수 있던 것 같다. 물론 내가 참가한 부분은 crypto이므로, 이에 해당하는 5가지 문제를 업솔빙하며 풀이를 적어보려고 한다. discrete-log 문제에서 주어진 코드와 실행 결과는 다음과 같다. from Crypto.Util.number import getPrime, isPrime, getRandomRange def getSafePrime(bits): while True: p = getPrime(bits - 1) q = 2*p + 1 if isPrime(q): return q with open("flag.txt", "rb") as f: flag...
yubin.choi's profile image최유빈(yubin.choi)
2021-09-16 21:00
-
Introduction and Proof of Baby-step Giant-step Algorithm
서론 시작하기에 앞서 이산 로그 문제(Discrete Logarithm Problem, 이하 DLP)가 무엇인지 알아봅시다. 소수 $p$와 $\mathbb{Z}/p\mathbb{Z}$의 원소 $b$, $n$이 주어질 때 다음 식을 만족하는 $0$ 이상 $p-1$ 미만의 정수 $x$를 찾는 문제가 DLP입니다. \(b^x\equiv n \text{ (mod }p\text{)}\) Baby-step Giant-step 알고리즘은 DLP을 $O(\sqrt{p}\lg{p})$에 해결할 수 있는 알고리즘입니다. 다양한 DLP 알고리즘 중 완전탐색을 제외한 가장 간단한 알고리즘에 해당합니다. 이 글에서는 Baby-step Giant-step 알고리즘이 DLP를 어떻게 해결하는지, 왜 $O(\sqrt{p}\lg{p})$라는 시간복잡도가 보장되는지에 관해 알아보겠습니다. Baby-step Giant-step Algorithm 이 알고리즘은다음과...
yubin.choi's profile image최유빈(yubin.choi)
2021-09-14 14:00
-
Introduction and Proof of Tonelli-Shanks Algorithm
서론 이 글은 이전에 작성한 Tonelli-Shanks 구현 포스팅에 Tonelli-Shanks에 대한 이론적 내용을 덧붙여 작성한 글입니다. 배우며 작성한 글이므로 틀린 내용이 있을 수 있으니, 발견하시면 댓글로 알려주시길 바랍니다. 본 글은 https://rkm0959.tistory.com/20를 토대로 학습하며 작성한 글입니다. 암호학을 공부하다 보면 $\mathbb{Z}/p\mathbb{Z}$에서 이차방정식을 풀어야 할 필요가 있다. CTF에서 RSA 문제를 풀 때 $m^2\mod p$를 구했다거나, Diffie-Hellman 프로토콜 문제를 풀며 $g^2 \mod p$로부터 $g$를 찾아야 한다거나… 여러 상황에서 이차방정식을 해결할 수 있다면 편리할 것이다. 우선 $\mathbb{Z}/p\mathbb{Z}$가 아니라 $\mathbb{R}$에서 이차방정식을 풀...
yubin.choi's profile image최유빈(yubin.choi)
2021-08-30 20:00
-
ANUSEC 2021 후기
2021년 8월 21일 진행된 전국 고등학생 사이버 보안 경진대회(ANUSEC 2021)에 Hyp3rFlow 팀으로 참가했습니다. 고등학생 3인 대회이므로, Hyp3rFlow에 마침 있던 고등학생 팀원 두 명(cgiosy, junseo)과 함께 참가하게 되었습니다. 실력이 많이 미약한 편이지만, Crypto 파트를 담당하여 풀기로 계획했습니다. cgiosy는 Web, junseo는 reversing이 없는 관계로 pwn을 보고 있었습니다. 대회 결과 총 37팀 중 7등을 하여 아쉽게 수상권에 들지 못했습니다. 아무래도 Crypto 파트에서의 시간 낭비와 알파벳을 의도한대로 읽지 못한 불운이 겹쳤고, pwn 파트에 익숙한 팀원이 없어 점수를 따지 못한...
yubin.choi's profile image최유빈(yubin.choi)
2021-08-27 00:00
-
20210502~20210508 BOJ 연습
1. BOJ4641 Doubles 리스트에서 각 숫자의 순서가 아닌 개수만이 중요하므로, 리스트를 순회하여 개수를 기록하고, 모든 숫자를 set에 삽입한다. set을 순회하면서 $cnt[x]\times !!cnt[2\times x]$를 모두 합하면 끝. 2. BOJ18004 From A to B 얼핏 우박수와도 비슷해보이지만, 결정적인 차이점은 숫자가 줄어들거나 늘어나려면 한 가지 선택지밖에 없다는 것이다. A>B라면 A가 짝수인지를 고려해서 A:=A/2를 가능한 한 시행하고, A<=B라면 A+=1을 B-A번 시행하여 두 수를 같게 만들 수 있다. 3. BOJ20500 Ezreal 여눈부터 가네 ㅈㅈ 상당히 당황스러운 디스크립션의 문제지만(…), 아무튼 어렵지...
yubin.choi's profile image최유빈(yubin.choi)
2021-05-08 00:00
-
[BOJ1987] 알파벳
BOJ1987 방문했던 알파벳을 다시 방문하면 안 되므로 backtracking을 하면서 이를 저장해줘야 하는데, 비트마스킹을 사용하면 깔끔하게 처리할 수 있다. 굳이 사용하지는 않아도 되나, 비트마스킹 기초 연습으로 풀기에 좋은 문제인 듯 하다. #include<bits/stdc++.h> using namespace std; #define ORD(x) (x-'A') const int dx[] = { 0, 0,-1, 1}; const int dy[] = {-1, 1, 0, 0}; int R,C; string arr[20]; int vpos(int x,int y){ return x>=0&&x<R&&y>=0&&y<C; } int mx=0; void f(int x,int y,int vis){ mx = max(mx,__builtin_popcount(vis)); for(int...
yubin.choi's profile image최유빈(yubin.choi)
2021-04-11 00:00
-
RSA Puzzles (1)
이전 글 - RSA 원리와 구현 이전 글에서는 RSA의 원리와 그 구현에 대해 간단히 소개하였으며, 이번 글에서는 ctf의 RSA Puzzle들에 적용할 수 있는 방법들을 몇가지 소개할 예정이다. (RSA Puzzle이라는 용어를 사용하는 이유에 관해서는 secmem - RSA Puzzles를 참고) Weak N RSA의 여러 인자 중 N은 RSA의 원리와 안전성 보장에 직결되어있는 요소이다. 이러한 N이 특정한 취약점을 지녀 쉽게 인수분해되거나 phi(N)이 쉽게 계산되어, RSA 암호화 전체를 파훼할 수 있게 되어버린다. 다음은 N에 발생할 수 있는 취약점 중...
yubin.choi's profile image최유빈(yubin.choi)
2021-02-01 00:00
-
POSTECH 온라인 해킹캠프 후기
지난 1월 18일부터 22일까지 5일에 걸쳐 POSTECH 해킹동아리 PLUS에서 주최한 온라인 해킹 캠프에 참여하게 되었다. 과학고 및 영재고에 재학 중인 학생을 대상으로 해킹 전반에 관한 기초를 다지는 캠프였다. 그 이전에 팀 단위 ctf에서 아무것도 못하는게 비참해서 이것저것 배운 후 뭐라도 할 수 있는 사람이 되자는 생각에 지원하였고, 6개 조 중 F팀으로 참가하게 되었다. 개인적인 소감을 말하자면, 기초를 다지기에는 정말 좋은 기회였다. 실습용 리눅스 서버를 개인마다 계정 하나씩 제공해주고, 디스코드로 수업 중에 질문 등에 대한 피드백과...
yubin.choi's profile image최유빈(yubin.choi)
2021-01-24 00:00
-
RSA 원리와 구현
RSA란? 고전 암호와는 달리, RSA, ECC 등은 ‘어려운 문제’에 기반하여 암호화를 진행합니다. 이러한 ‘어려운 문제’는 컴퓨터를 이용하여도 정답(혹은 해)를 구하기 어려운 문제를 말하며, 소인수분해 문제, 이산 로그 문제 등이 대표적인 예시입니다. RSA는 그 중 소인수분해가 어려운 문제라는 점을 활용하는 암호화방식입니다. GNFS 등 빠른 소인수분해 알고리즘이 등장하였으나, 비트수에 대한 다항 시간 알고리즘은 알려져 있지 않아 큰 수를 소인수분해하는 것은 여전히 어려운 문제입니다. RSA는 1978년 로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)의 연구에 의해 체계화되어,...
yubin.choi's profile image최유빈(yubin.choi)
2021-01-18 00:00
-
Tonelli-Shanks 알고리즘 구현
Tonelli-Shanks 알고리즘은 mod p에서 Quadratic Residue에 대해 그 제곱근을 구하는 알고리즘이다. def tonelli_shanks(n,p): def isQR(x,p): return pow(x,(p-1)//2,p)==1 if not isQR(n,p): return -1 Q,S=p-1,0 while Q%2==0: S+=1 Q//=2 z=None for x in range(2,p): if not isQR(x,p): z=x break M,c,t,R=S,pow(z,Q,p),pow(n,Q,p),pow(n,(Q+1)//2,p) while True: if t==0: return 0 elif t==1: return R k=t*t%p ii=None for i in range(1,M): if k==1: ii=i break k*=k k%=p b=pow(c,2**(M-i-1),p)%p M=ii%p c=b*b%p t=t*c%p R=R*b%p if __name__=='__main__': n,p=map(int,input().split()) print("STARTED") print(tonelli_shanks(n,p))
yubin.choi's profile image최유빈(yubin.choi)
2020-11-20 00:00
-
Caesar Cipher(시저 암호)
Caesar Cipher은 고대 로마 황제였던 카이사르(시저)가 사용했던 간단한 암호로써, 알파벳을 특정한 개수만큼 shift하는 것으로 decode할 수 있다. shift된 문자열이 encode되기 전의 원본인지 판별하는 것을 자동화하는 것은 쉽지 않으며, decode 결과로 가능한 문자열의 수는 많지 않으므로(26개) 다음은 가능한 모든 결과를 출력하는 함수의 구현이다. def decode_caesar(t): def nxtAlpha(x): if x=='z': return 'a' elif x=='Z': return 'A' else: return chr(ord(x)+1) import copy s=copy.deepcopy(t) res=[] for x in range(26): res.append(copy.deepcopy(s)) for y in range(len(s)): if s[y].isalpha(): s=s[:y]+nxtAlpha(s[y])+s[y+1:] return tuple(res)...
yubin.choi's profile image최유빈(yubin.choi)
2020-11-20 00:00
-
KOI 2020 1차대회 고등부 2교시 풀이
문제 링크 KOI 제공 PDF BOJ - 박 터트리기 BOJ - 햄버거 분배 BOJ - 조명등 1번 - 박 터트리기 BOJ - 박 터트리기 단순 수학입니다. $N < \frac{K(K+1)}{2}$라면 불가능하고, 아닐 경우에는 N%K의 값을 확인하여 적당히 처리해주면 됩니다. #include<bits/stdc++.h> using namespace std; int main(void){ ios::sync_with_stdio(0);cin.tie(0); int N,K; cin>>N>>K; if(K*(K+1)/2>N){ cout<<-1; return 0; } N-=K*(K+1)/2; cout<<K+(N%K?1:0)-1; } 2번 - 햄버거 분배 BOJ - 햄버거 분배 그리디입니다. 가능한 한 왼쪽에 있는 햄버거를 먹게끔 짜면 됩니다. 전체 시간복잡도는...
yubin.choi's profile image최유빈(yubin.choi)
2020-09-27 00:00
-
제 4회 생각하는 프로그래밍 대회 Open Contest 후기
딱히 열심히 할 생각이 없었는데 4등한 기념으로 리뷰글 씁니다. 우선, 난이도 배분이 상당히 적절하게 되어있었습니다. 간단한 입출력 문제부터, 어느 정도 심화적인 개념이 필요한 문제까지 고루 분포해있었다고 생각합니다. 다이아 이상의 문제들도 익숙하신 분이라면 아니겠지만, 플레티넘 정도의 문제를 연습하고 계신 분들까지라면 풀어보시는 것도 좋을 듯한 문제셋입니다. A. 고무오리 디버깅 문제의 컨셉과 풀이 모두 굉장히 아기자기한 문제입니다. 문제를 풀며 단 한 가지 걱정이 되었던 것은 한글 입출력인데, 영문자를 취급하듯 코드를 짜도 AC를 받을 수 있었습니다. 변수에 남은 문제의...
yubin.choi's profile image최유빈(yubin.choi)
2020-09-26 00:00
-
[BOJ] 이진 탐색 트리
BOJ2957 이진 탐색 트리 이진 탐색 트리를 그냥 구현하면 당연히 TLE를 받습니다. 플래티넘 5에 이렇게 단순한 구현을 시킬 일은 없습니다. 이진 탐색 트리를 만들었다고 가정하고, 이를 아래로 눌러 일렬로 만들어봅시다. 이 그림에서 잘 살펴보다 보면, 각 노드의 부모는 일렬로 만든 상태에서 각 노드에 인접해있고, 인접한 노드 중 깊이가 깊은 노드임을 알 수 있습니다. 따라서 배열을 항상 정렬된 상태로 유지하고 노드를 삽입할 때 인접한 칸의 깊이를 빠르게 알 수 있다면, 문제를 해결할 수 있는 것입니다. 문제는,...
yubin.choi's profile image최유빈(yubin.choi)
2020-09-23 00:00
-
[BOJ] 소가 길을 건너간 이유 9
BOJ14463 소가 길을 건너간 이유 9 다음과 같은 관찰만 할 수 있다면 아이디어는 간단합니다. A<B를 만족하는 네 정수 A, B, C, D와 A, B를 잇는 선분 X와 C, D를 잇는 선분 Y에 대해 다음과 같은 명제가 성립합니다. Lemma 1. X와 Y가 교차함은 A<C<B<D와 동치이다. 이 두 명제는, 몇가지 케이스를 나눠 살펴봄으로써 관찰할 수 있습니다. Lemma 1에 의해 같은 소가 지나는 점을 잇는 선분을 번호가 작은 점을 기준으로 정렬한다면, 어떤 선분 K에 대해 K와 교차하며 K보다...
yubin.choi's profile image최유빈(yubin.choi)
2020-08-24 00:00
-
[BOJ] 등산
BOJ1486 등산 그래프의 간선 가중치에 대해 조금만 생각해보면 핵심적인 아이디어를 떠올릴 수 있습니다. 간선의 존재여부 및 그 가중치를 인접행렬이나 인접리스트로 저장하는 대신, 인접한 두 위치와 그 높이를 갖고 간선 존재여부 및 가중치를 O(1)에 계산할 수 있습니다. 이 격자 그래프에서 노드의 개수는 최대 625개이고, 간선의 수도 이에 선형비례하므로 다익스트라 알고리즘을 사용해 준다면 시작점에서 모든 노드로 가는 최단시간을 파악할 수 있습니다. 한 가지 문제점은 우리가 고려할 경로는 가는 경로뿐만 아니라 오는 경로도 있다는 것이지만, 이는 간선 가중치를...
yubin.choi's profile image최유빈(yubin.choi)
2020-08-21 00:00
-
20210709 BOJ 연습
서론 그냥 심심해서 몇 문제 풀었는데 좀 괜찮은 문제 얻어간거 같아서 괜찮은 하루였던 듯. 1. BOJ1043 거짓말 만약 두 파티에 공통된 인원이 있다면, 그 두 파티에서 거짓말을 할 수 있는지는 서로 동일하다. 따라서 두 파티 중 하나에라도 속하는 인원들은 두 파티짜리의 한 덩어리(=독립집합) 인원으로 볼 수 있고, 이 점에서 Union-Find를 쓰면 각각의 독립집합을 형성할 수 있다. 약간의 Union-Find 기술을 쓸 수 있는데, 각 독립집합이 하나의 음 아닌 정수로 표현할 수 있는 특정을 갖는다면 -1배하여 독립집합의...
yubin.choi's profile image최유빈(yubin.choi)
2020-07-09 00:00
-
[LEETCODE] LeetCoding Challenge - Find All Anagrams in a String
LeetCoding Challenge - Find All Anagrams in a String 문자열 S와 P가 주어지는데, S의 연속 부분 문자열 중 P와 애너그램 관계인 문자열의 시작 인덱스를 모두 담은 벡터를 반환하는 문제입니다. 길이가 N인 문자열의 애너그램 개수는 N! 개이므로 모든 애너그램에 대해 판별하는 것은 조금 무리가 있어보입니다. 그렇다면 애너그램 전부에 대해 값이 같은 방식의 해싱을 사용해서 비교하면 어떨까요? 이런 해싱 중 가장 쉽게 떠올릴 수 있는 건 연속한 len(P)개의 문자의 아스키코드 값을 모두 곱하면 문자의 배치 순서와는 무관하고,...
yubin.choi's profile image최유빈(yubin.choi)
2020-05-18 00:00
-
[BOJ] 왕들의 외나무다리 돌게임
BOJ18937 왕들의 외나무다리 돌게임 어제 종료된 Semi-Game Cup의 제일 첫 문제입니다. 열심히 노느라 참가를 하지는 못했지만, 문제가 공개된 후에 풀어보니 A번인 이 문제만큼은 난이도가 평이하고 재밌더군요. 문제에서 제시된 게임은 각 플레이어가 다음과 같은 행동을 취할 수 있는 님게임과 일치합니다. 돌을 임의의 개수만큼 가져온다. 해당 무더기에서 가져온 돌 중 일부를 다시 쌓는다. 이 때, 먼저 모든 무더기의 돌의 개수를 xor한 값이 0이 되게 한 플레이어는 상대방이 돌을 쌓던 돌을 가져가던 다시금 돌의 개수를 xor한 값이 0이...
yubin.choi's profile image최유빈(yubin.choi)
2020-05-18 00:00
-
LCS 정복하기 4
BOJ18438 LCS 5 이전에 풀이를 작성한 LCS 1/2/3에 비해 갑자기 난이도가 수직 상승한 문제입니다. (LCS 4는 특수한 케이스니 제외합니다. LCS 4의 풀이는 나중에 다른 글에서 소개하도록 하겠습니다.) 최대 길이 7000의 문자열 두 개의 LCS를 TL 1s, ML 7MB에 구해야합니다. TL은 그럭저럭 평범한 것 같은데, ML이 심상치 않다. 이 ML이 난이도를 D2까지 올려놓은 원인인 셈이죠. LCS 2 문제에서 한 대로 공간복잡도 $O(NM)$에 역추적하려고 하면 최대한 크기가 작은 short형을 사용하더라도 MLE는 피할 수 없습니다. 만약 길이만을 구하는...
yubin.choi's profile image최유빈(yubin.choi)
2020-05-15 00:00
-
LCS 정복하기 3
BOJ1958 LCS 3 단순히 생각해서 LCS(A,B,C) = LCS(LCS(A,B),C)라고 생각할 수 있으나 두 문자열의 LCS가 하나가 아닐 수 있다는 점에서 무수히 많은 반례를 만들 수 있습니다. 2166번과 같은 근본적인 접근으로 다음과 같은 점화식을 세울 수 있습니다. DP [i] [j] [k] = DP [i-1] [j-1] [k-1] + 1 when A [i] == B [j] and B[j] == C[k] DP [i] [j] [k] = max(DP [i-1] [j] [k], DP [i] [j-1] [k], DP [i] [j] [k-1]) otherwise 점화식만...
yubin.choi's profile image최유빈(yubin.choi)
2020-05-09 00:00
-
LCS 정복하기 2
BOJ9252 LCS 2 NM lcs backtracking 문제입니다. 2166번에서 구한 대로 dp table을 작성한 후 점화식의 특징을 이용하여 backtrack할 수 있습니다. 길이 a,b인 문자열 A,B에 대해 (a,b)에서 시작해 (0,t) 또는 (t,0) 꼴의 좌표에 도달할 때까지 다음의 세 행동 중 하나를 취하며 추적하여 LCS로 가능한 문자열을 추출할 수 있습니다. (x,y)=>(x-1,y) when dp [x] [y] == dp [x-1] [y] (x,y)=>(x,y-1) when dp [x] [y] == dp [x] [y-1] (x,y)=>(x-1,y-1) when a [x] == b [y] dp 점화식에 의해...
yubin.choi's profile image최유빈(yubin.choi)
2020-05-09 00:00
-
LCS 정복하기 1
BOJ9251 LCS LCS 정복하기, 그 첫 번째. 가장 기초적인 $O(NM)$ dp로 LCS 길이 구하기입니다. LCS란 Longest Common Subsequence의 약자로, 두 수열의 공통된 부분수열을 의미합니다. 이때 부분수열은 연속하지 않아도 됩니다. 예를 들어 IHATEPIZZA와 ILOVEPIZZA의 LCS는 길이 7인 IEPIZZA라고 할 수 있겠죠. 같은 두 문자열이라고 해도, LCS는 여러 개일 수도 있습니다. IEATCHICKEN과 IAETCHICKEN이 그 예시인데요, 길이 7의 IECHICKEN과 IACHICKEN 모두 LCS임을 알 수 있습니다. 그렇다면 LCS의 길이는 어떻게 구할까요? DP로 생각해봅시다. DP [i] [j] = (A[1..i]와 B[1..j]의...
yubin.choi's profile image최유빈(yubin.choi)
2020-05-01 00:00
-
[BOJ] 다각형의 면적
BOJ2166 다각형의 면적 꼭짓점 중 하나를 기준점으로 잡고, 모든 연속한 점쌍에 대해 외적을 구한 후 합하면 됩니다. 외적의 총합이 음수일 수도 있기 때문에 절댓값을 반드시 취해줘야합니다. #include<bits/stdc++.h> using namespace std; using ll=long long; using dot=pair<ll,ll>; dot operator-(dot a,dot b){ return {a.first-b.first,a.second-b.second}; } ll ccw(dot a,dot b,dot c){ dot x=b-a,y=c-a; return x.first*y.second-x.second*y.first; } int main(void){ ios::sync_with_stdio(0);cin.tie(0); int n; cin>>n; vector<dot> v(n); dot f; ll sum=0; for(int i=0;i<n;i++){ cin>>v[i].first>>v[i].second; if(i){ sum+=ccw(f,v[i-1],v[i]); } else{ f=v[i]; } } sum=abs(sum);...
yubin.choi's profile image최유빈(yubin.choi)
2020-05-01 00:00
-
[BOJ] 복도 뚫기
BOJ9373 복도 뚫기 센서와 벽을 노드 취급하고, 간선은 두 노드 사이에 들어갈 수 있는 원의 최대 지름으로 합시다. $O(N^2)$번의 연산이 요구되므로 N<=1,000인 이 문제에서는 무리없이 해결 가능합니다. 이 때, 경로가 존재하지 않을 때까지 두 노드 사이를 차단한다고 생각해봅시다. 경로가 하나라도 존재할 때 차단되지 않은 간선의 가중치 최솟값이 그 때 존재하는 경로만을 고려할 때의 답이라고 할 수 있습니다. 그렇다면 이런 가중치의 최솟값을 최대화하면 되는데, 이는 간선을 가중치 기준으로 정렬하고 가중치가 작은 것부터 차단해가며 완전히 모든 경로가...
yubin.choi's profile image최유빈(yubin.choi)
2020-04-30 00:00
-
[BOJ] 풍선
BOJ4716 풍선 그리디라는 깔끔하고 우아한 풀이가 있으나 실상은 팀노트가 있는 MCMF를 활용하여 짜는 것이 정신적 스트레스를 덜 받습니다. MCMF로 푸는 경우 노드는 SOURCE / SINK 각 팀 방 A, B 로 설정하고 간선의 가중치와 용량을 적절히 설정해주면 됩니다. 단, MCMF로 풀 때에는 일반적으로 사용하는 느린 MCMF로는 TLE를 받게 되며 커팅을 추가하거나 헬조선 MCMF를 사용하여야 AC를 받을 수 있습니다. #include<bits/stdc++.h> using namespace std; using pi=pair<int,int>; const int MAXN=1010; //Hell-Joseon MCMF struct edg{ int pos, cap, rev,...
yubin.choi's profile image최유빈(yubin.choi)
2020-04-24 00:00
-
[BOJ] A+B
BOJ1000 A+B 가장 기초적인 문제입니다. //C #include<stdio.h> int main(void){ int a,b; scanf("%d%d",&a,&b); printf("%d",a+b); } #Python a,b=map(int,input()) print(a+b)
yubin.choi's profile image최유빈(yubin.choi)
2020-04-22 00:00