Everything
-
코드포스 오렌지 달성
https://codeforces.com/profile/Pentagon03 UCPC 2024 직전에 달성하였습니다. 막상 원할 때는 닿을듯 말듯 하던 것이, 힘 빼고 편안하게 코딩하니 결과가 좋게 나오는 경험입니다. Div.2 2솔 하고 다시는 안 갈줄 알았던 블루도 가봤습니다. 이후 코포를 잘 못한다는걸 인정하고 계속 응시하니 신기하게도 점점 문제가 잘 풀리네요. 항상 에듀 라운드는 등수가 잘 안 나오는 경향이 있어 꺼리다가,UCPC 전 마지막 기회라 생각하고 도전한 것이 좋은 결과로 돌아와서 정말 행복했습니다. 모두 행운을 빕니다!
2024.08.06 17:33 -
[VSCode] Code Runner에서 파일 명 한글, 공백과 java class 인식 오류 해결
한글 문제는 다음 참고: https://m.blog.naver.com/rhyshan/222289477124요약: Win + R -> intl.cpl -> 관리자옵션 -> 한국어 -> UTF-8 사용 -> 확인 일단 Extensions - Code Runner - Settings - Executor Map by File Extension - Edit in settings.json 버튼을 눌러 settings.json 파일에 진입하자.1. 파일 명 공백 문제문제 원인: Powershell에서 실행할 때$dir$fileNameWithoutExt이 부분이 ""으로 묶여 있지 않아, 가령 파일명이 "test file"일 경우.\test file로 인식 되어 문제가 생긴다.이게 두 변수가 붙어 있어서 단순히 ""을..
2024.06.17 13:37 -
About Me
안녕하세요, pentagon03입니다.알고리즘 프로그래밍을 즐기며, 제가 관심 있는 것들에 대한 글을 작성합니다.프로필 링크Baekjoon Solved.Ac Codeforces Github 알고리즘 과외 또한 진행하고 있습니다. (Korean / English)C++/Python/USACO/Competitive Programming pentagon03.codes@gmail.com 혹은 Discord: pentagon03위 채널을 이용하여 문의해주시면 답변 드리겠습니다.
2024.06.16 15:10 -
문제풀이 흑마법
언제나 그렇듯이 잘 풀리면 상관 없는 것들내적 해시- 존재성만 확인하면 되는 상황이라면 굳이 복잡한 라빈카프가 아니라 랜덤 포인트 N개를 뽑아 내적해시를 사용할 수 있다. https://github.com/Pentagon03/Algorithms/blob/master/Strings/Hasher_Dot.cpp 시간제한만큼만 최선을 다하기최적해를 구해야 하는 상황에서 충분히 빠른 방법이 생각이 안 날 경우, 그냥 가능한만큼만 브루트포스로 찾아본다 ?!적당한 시간 제한을 걸어놓고, 브루트포스 / 백트래킹이 그 시간을 넘었을 경우, 그때까지 찾은 답을 출력한다.예시1 https://codeforces.com/contest/1979/submission/264506642예시2 https://www.acmicpc.ne..
2024.06.07 11:52 -
랜덤디펜스 4일차
https://master.d66dlzauezpcp.amplifyapp.com/pentagon03랜덤디펜스를 더 돌렸다. 요번에는 어려운 문제들이 대거 등장했다. ---8160Trains플2PASSED, UPSOLVED 거의 보자 말자 해싱 풀이가 나왔는데, 돌발적인 다른 이슈랑 Hasher struct를 어디서 가져와서 쓰려다가 말려서 실패했다. Rolling Hash를 구현했는데 WA를 받길래 포기하고 Dot Product를 쓴 koosaga님 구현을 가져왔다.RabinKarp(Polynomial Hash)는 이제 문자열을 Shift한다던지, reverse한다던지, 다항식 자체의 성질을 사용하는게 아니라단순히 Array를 저장하고 각 위치를 swap하는 정도의 단순한 연산만 있는 경우 Dot Pr..
2024.05.29 15:45 -
랜덤디펜스 1~3일차
https://master.d66dlzauezpcp.amplifyapp.com/pentagon031~3일차 푼 문제 정리를 해볼까 한다. 티어는 푼 시점 기준이다. 볼드체 해놓은 문제는 어려웠던거나 추하는것.1일차12581Your Rank is Pure (Small)골546분 대망의 첫 문제고 골드가 나와서 당황했다.dp로 잘 비빌 수 있을거 같지만 n이 작아서 비트마스크로 모든 가능한 경우를 다 해보는 쪽으로 방향을 선회했다.Off-by-One error의 심각성을 확연히 알 수 있었던 문제.구현하면서도 계속 헷갈려서 46분을 허비했다. 비트마스크만 나오면 요상한? 최적화를 해서 등수를 높이려는 욕심이 있는데 여기서 이걸 확실히 느꼈다. --- 23884알고리즘 수업 - 선택 정렬 4골414분 다음 문..
2024.05.27 12:12 -
Min Cut과 Max Flow와의 관계
Link to original note: [[Flow Graph]]Cut은 Flow Graph에서 정점 s에서 t까지 가는 유량이 없도록 어떤 간선들을 자를 때, 그 간선들의 집합을 의미한다. 이때 Min Cut이란 간선 용량의 합이 최소가 되는 집합을 의미한다. 세줄 요약: 1) 먼저 임의의 $cut$에 의한 간선 용량의 합($|cut|$)은 $flow$의 합($|flow|$)보다 항상 크기 때문에 모든 $|cut|$은 $max(|flow|)$ 이상이다.2) 임의의 Max Flow를 흘린 다음의 그래프에서, 유량을 조금 더 흘릴 수 있는 Residual graph에서, src로부터 도달할 수 있는 정점들의 집합을 $S$라 할 때, $S$에서 $V \setminus S$까지 가는 모든 간선을 끊는 ..
2024.04.29 02:07 -
[요약] ICPC 전략 가이드
https://people.cs.uchicago.edu/~borja/pubs/sigcse2016-programming-contests.pdf 이 글은 Aaron Bloomfield와 Borja Sotomayor의 "A Programming Contest Strategy Guide"를 읽고 한국어로 요약한 내용입니다. 핵심을 간단하게 전달하기 위해 필자의 해석이 담겨 원문과 다른 내용이 있을 수 있습니다. 세줄 요약 저자는 북미 대학 ICPC 코치들이다. 1999년 이후로 한 번도 북미 출신 대학이 우승 못하고 항상 러시아 / 중국 / 폴란드만 우승한다는 사실에 안타까움을 금치 못한다. 따라서 "어떤 팀들이 ICPC에서 활약하는가"를 자신들의 월드파이널(줄여서 월파) 코치 경험을 통해 사례 기반 연구하여 ..
2024.04.02 16:17 -
USACO US Open 2009 Gold 3 - Tower of Hay
USACO US Open 2009 Gold 3 - Tower of HayBOJ 6116 케이크1st StepFirst, we can consider a greedy approach.By the following perspective: "lower the last floor, better it is"So we greedily choose the lowest last floor possible. (e.g. the last floor consists of only one bale)ex) 9 1 2 4 7 => 9 / 1 2 4 / 7 However we can find out this is wrong.Consider "3 3 1 2".choosing only '2' at the last eventually m..
2024.02.23 17:03 -
백준 17399 트리의 외심 - 정당성 증명
https://acmicpc.net/problem/17399트리 위 노드 a,b,c의 외심을 찾는 문제.외심은 정의는 다음과 같다.1. 동일성 -> dist(a,b) = dist(b,c) = dist(c,a) 2. 최소성 a와 b의 가장 가까운 중점을 M이라 해보자. M에서 a와 b쪽이 아닌 다른 방향 (부모 혹은 자식)으로 간 것들도 모두 a와 b의 중점이 될 것이다. 거리를 d라 하자. dist(M,c) = d라면 정답은 그대로 M이된다. (다른 방향으로 옮기면 d가 증가한다.) dist(M,c) != d라면 M을 적당히 옮겨서 c와의 거리를 맞춰야 한다. 적당히 옮겨서 외심 M이 존재한다고 가정하자. 놀랍게도 이때의 M은 (a와 c의 중점) 혹은 (b와 c의 중점) 중 하나다. 만약 M이 (a,b)..
2024.02.11 22:08 -
백준 단계별로 풀어보기 완.
컨벡스헐부터 정체되어 있던 백준 단계별 풀어보기를 2024-02-05 오늘 끝냈다. PS를 제대로 하기로 다짐한 사람이라면 단계별로 풀어보기부터 강의 듣듯이 빠르게 배운 후 OI / ICPC 스타일 문제를 풀어보는 것도 하나의 가장 효율적인 방법이라고 생각한다. 하나의 Tool Box를 다 채우고 시작하는 느낌.
2024.02.05 12:08 -
Android Studio 설치 중 무한부팅 블루스크린: DRIVER_UNLOADED_WITHOUT_CANCELLING_PENDING_OPERATIONS, aehd.sys
2023/08/09 컴퓨터 관점에서 섬뜩한 일이 있었다. 아예 무한 BSOD (블루스크린) 상황에 빠진 것. 일반적인 안전모드 방법도 전혀 먹히지 않았다. -> "Startup Settings" 이 버튼이 없음. 이러한 화면 DRIVER_UNLOADED_WITHOUT_CANCELLING_PENDING_OPERATIONS aehd.sys 상황을 분석하기에는 시간이 너무 많이 들어서 사건 발생부터 해결까지 시간 순으로 설명하겠다. [문제 상황] 1. Android Studio 설치 이 과정에서 aehd 2.0이 깔림. https://developer.android.com/studio/run/emulator-acceleration?hl=ko Android Emulator의 하드웨어 가속 구성 | Android..
2023.08.09 17:12 -
[BOJ 17371] 이사 | 증명
BOJ 17317 이사의 증명 문제: 점 $P_1$, $P_2$, ... $P_N$이 주어질 때 $f(X)$를 점 $X$에 대해 $P_i$중 가장 먼 점과 가장 가까운 점의 거리의 합으로 정의하자. $min(f(X))$를 구하시오. Claim) $min(f(P_i)) = min(f(X))$ = $X$를 $P_i$ 중 하나로 정해도 그 최솟값은 전체 최솟값과 같다. Proof) $f(P_{opt}) = min(f(P_i))$ $f(X_{opt}) = min(f(X))$ $X_{opt}$에 대해 가장 가까운 점 $P_i$와 가장 먼 점 $P_j$. 삼각부등식에 의해 $\overline{X_{opt} P_i} + \overline{X_{opt} P_j} \geq \overline{P_i P_j}$ 증명은 $X..
2023.01.07 16:26 -
VS Code C/C++/Python 설정 방법 - PS를 위한
- UPD20241022: 스트레스 테스트 방법 컴퓨터를 초기화할 때마다 필자도 이 글을 켜고 설정한다.Python은 공식 홈페이지에서 설치 + Step A 만으로 완료된다. 목차A. 에디터 설정B. 컴파일러 설정C. C/C++ 버전 설정D. 실행방법 및 주의점E. 추가적으로 설치하면 좋은 것 A. 에디터 설정1. VSCode 다운로드 https://code.visualstudio.com/2. Code Runner 설치 https://marketplace.visualstudio.com/items?itemName=formulahendry.code-runner 3. Extension 설정에서 Run in Terminal 사용 가능 체크4. 파일> 새 파일로 .c 파일을 만들면 C/C++ 관련 확장 프로그램..
2022.10.22 23:57 -
Master Theorem
*The content is based on 2022 Fall EE205 MasterMethod Lecture. Master Method is a powerful black box for solving recurrences such as Divide and Conquer Method. Assumption: All subproblems have equal size. $T\left(n\right)$ is the function to analyze operation costs to solve problem size of $n$. Settings 1. Base Case: $\forall$ sufficeiently small $n$, $T\left(n\right) \le$ a constant 2. Recurren..
2022.09.14 11:35 -
Computing Fibonacci Sequence with Matrix Multiplication
Fibonacci Sequence as Recursive Formula $F_0 = 0$ $F_1 = 1$ $F_n = F_{n-1} + F_{n-2}, \quad ^\forall n \ge 2$ Fibonacci Sequence as Matrix Multiplication Form $\begin{vmatrix} F_n \\ F_{ n-1} \end{vmatrix} = \begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix}^{n-1} \cdot \begin{vmatrix} F_1 \\ F_0 \end{vmatrix}, \quad ^\forall n\ge 1$ Fast Recursive Powering for elements of Monoid Suppose we are calcul..
2022.09.06 12:49 -
Full Diamond
상위 100개 문제를 다이아 이상의 문제로 채웠다! 공부하고 연습한 기록이 이만큼 쌓여서 뿌듯하다. 이제는 사고력을 키워보자. 스스로 사고해서 문제를 풀어내는 것이 재밌어지는 그날까지 연습!
2021.06.11 14:40 -
주세혁 VS 티모 볼
정말 주세혁은 레전드다.. 9년 전 월드컵 경기. 저 때가 그들의 최정점이 아니라면 언제일까 주세혁의 수비수 플레이는 스스로 기회를 만들어나간다는 점에서 정말 멋지다고 생각한다. 저렇게 빠른 공을 여유롭게 받을 수 있을 때까지 얼마나 많은 연습을 했을까 탁구를 한 번이라도 쳐봤다면 저렇게 수비하는 게 보이는 것보다 수백배 어렵다는 사실을 깨달을 것이다. 아무 회전 없이 공을 넘기는 데만 해도 온 신경을 기울여야 하는데, 저렇게 빠른 스매시 / 상회전 걸린 드라이브 등을 자유롭게 방향까지 조절해가며 커트를 친다. 한편 티모 볼 또한 대단한 선수이다. 티모 볼은 독일 선수로, 중국이 점령하고 있던 현대 탁구에서 세계 1등까지 찍었다. 당시 유럽에서 영웅 취급을 받았다고 ㅎㅎ 잘생김 + 매너 있는 행동으로 인..
2021.05.26 15:54 -
탁구 핵심 전략 10가지
*Reference의 번역과 필자의 분석이 담긴 글입니다. 글을 인용하거나 공유할 때는 이 글의 주소를 맨 위에 표시해주시기 바랍니다. 감사합니다. 1. 공의 회전을 분석한다 임팩트 순간에 상대방의 라켓의 이동방향을 본다. (관찰자가 상대편의 라켓을 봤을 때) 아래에서 위로 => 상회전 위에서 아래로 => 하회전 왼쪽에서 오른쪽으로 => 왼쪽으로 휘어진다 오른쪽에서 왼쪽으로 => 오른쪽으로 휘어진다 손목 스냅과 사선 방향 타격은 횡회전이 섞인 상회전, 하회전 공을 만든다. 상대방이 전면으로 공을 빗겨 칠 때, 라켓이 공 오른쪽에 있을 경우는 공이 왼쪽으로 휜다. 라켓이 공 왼쪽에 있을 경우는 공이 오른쪽으로 휜다. *공의 방향는 임팩트 방향과 관련이 있다. ($\vec F = m\vec a$). 특히 서..
2021.05.19 12:53 -
Slope Trick - 함수 개형을 이용한 최적화
Special Thanks to Cgiosy Slope Trick: 함수 개형을 이용한 최적화 백준 13323 BOJ 수열 1 풀이 백준 13324 BOJ 수열 2 풀이 *20210513 수정#1 2021/05/13 정보과학세미나 시간에 보고서 및 발표자료의 내용으로 사용함. WhiteBoard Tutorial BOJ수열1 BOJ수열2
2021.05.13 14:44 -
독자들에게 가끔씩 바라는 점
나도 다른 블로그를 참 많이 읽는다.나만 그런 것인지는 모르겠지만알고리즘 글을 읽을 때 유난히"이게 무슨 개소리야" 하는 상황이 많이 닥친다.철없을 때는 다른 사람이 글 참 못 쓴다.. 생각했지만내가 블로그를 해보고 나니, 그 귀차니즘에 대해 이해해버렸다.문제 풀고 맞추는게 재밌지, 그 지식을 다른 사람에게 전달하는 것에서 재미를 느끼는 것은 또 전혀 다르다.흥미를 느끼지 않는데 글이 술술 잘 써질리 전무하다.그런데, 대부분 그 사실을 잘 모른다. 알고리즘 정리/문제 풀이 글에는 대부분 댓글이 거의 달리지 않기 때문이다. (...)내 블로그를 떠나서 PS블로그계는 정말 질문에 인색하다는 생각이 많이 든다.나부터도 글을 읽다 막혀도 대부분 혼자 고민하고, 정 안되면 다른 글로 그냥 넘어간다.다른 분들도 마..
2021.03.09 22:18 -
Centroid Decomposition - 센트로이드 분할
센트로이드 분할 1. 존재의의 센트로이드 분할 = 트리에서의 분할 정복 기법 트리에서 어떠한 문제( i.e.) 길이가 K인 경로의 개수를 구하라)를 해결해야 될 때 트리를 크기가 더 작은 서브 트리들로 분할하여 문제를 적용한다. 이때 효율적인 분할의 대표적인 기법이 센트로이드 분할이다. 2. 센트로이드란 트리의 무게중심인 정점. 트리를 어떤 정점을 기준으로 차수만큼의 서브트리들로 나눌 수 있다. 이때 모든 서브트리의 크기가 전체 트리 크기의 절반 이하일 때, 그 정점을 Centroid라 한다. Q) 센트로이드는 항상 존재하는가? A) 그렇다 증명 1) 센트로이드 탐색 알고리즘 임의의 노드를 고르자. 그 노드를 루트로 하는 트리를 생각한다. 모든 서브트리의 크기가 조건을 만족한다면 그 노드가 센트로이드다...
2021.02.28 23:16 -
(공유) 알고리즘 구현 깃헙
KACTL 프로젝트 FORK 해왔다. github.com/Pentagon03/kactl Pentagon03/kactl KTH Algorithm Competition Template Library (... eller KTHs AC-tillverkande lapp) - Pentagon03/kactl github.com 개인적으로도 만들고 있음 github.com/Pentagon03/AlgorithmTemplate Pentagon03/AlgorithmTemplate Contribute to Pentagon03/AlgorithmTemplate development by creating an account on GitHub. github.com
2021.02.23 20:44 -
Codeforces Round #704 Div.2
이정도로 망친건 꽤나 오랜만이다.애드혹, Case-Work 연습이 부족함을 절실히 느낀 라운드A 잔실수와 C 뇌절이 결정적인 악재로 작용했다.D,E를 봤을 때는 이미 시간이 30분밖에 안 남은 시점이었다.C에서 D,E로 빨리 넘어가면 라운드를 살릴 가능성이 더 높아졌을 거라 판단된다.A. x in {a,b,c}에 대해 min( (t+x-1)/x*x )를 구하여 출력하면 된다. 함수를 만들었는데 함수 인자를 int로 하는 실수를 저질렀다. 교훈: 간단한 함수는 lambda + auto 타입 인자를 사용하자. define도 좋은듯B. 쉬운 constructive. 뒤에서부터 큰 수 기준으로 배열을 자르면 된다.C. 파라메트릭, dp 뇌절로 쉬운 애드혹을 1시간 20분 가량 붙들었다. 펑파라메트릭이 성립할 ..
2021.02.23 20:31 -
Codeforces Round #703 Div.2
codeforces.com/contest/1486 총평: 전체적으로 문제 셋이 재밌었고 선방했다. 정확히 1달만에 즉흥적으로 친 코포라 걱정 반 설렘 반이였는데 오히려 더 나은 결과를 얻었다 A -> B -> C1 -> C2 -> E 순으로 풀었다. A는 직관적으로 생각하면 쉬울 것을 너무 성급하게 찍어버렸다. i -> i+1 단방향만 가능하므로 i=0->n-1까지 따라가면서 가능한지 검사하는게 중요 포인트 B는 수학. 무난히 빨리 풀었다. C1, C2는 재미있는 인터랙티브 문제이니 꼭 풀어보는 것을 추천한다. 로그를 붙이는 다양한 알고리즘에 관하여 숙고한 경험이었다. C1 구현에 오래 걸리고, C2는 자칫 못 풀 뻔 했지만 관점을 완전히 바꾸니 시간 투자 후 해결할 수 있었다. E는 다익스트라 문제인데..
2021.02.19 14:08 -
Solved.ac 경험치 시스템 개편
최근 Solved.ac 티어 계산 시스템이 바뀌었다. 1번 항목과 2번 항목은 푼 문제를 어려운 순으로 정렬해 상위 100개 문제를 합산하는 것으로 수정되었다. 솔브드 Slack에서 얻은 정보들이다. 첨언 하자면 푼 문제 수에 따른 값은 최대 175이며, 거의 증가하지 않는다. 675문제 푼 내가 169점이고, 9000문제 가량 푸신 구사과님이 175점인 것을 보면 된다! 기여 수에 따른 값은 최대 25이고 135문제 기여 -> 25, 8문제 기여 -> 14인 것을 보면 티어와 거의 무관한 수치다. 티어와 가장 유관한 것은 푼 문제들 중 가장 어려운 것과 클래스가 되시겠다. 다이아, 루비를 많이 풀자 의도
2021.02.08 21:38 -
If you are a Newbie in Competitive Programming
There was a question in Codeforces recently. Talking about "I'm such a Newbie in Codeforces.. What should I do?" This is a quite boring question since there are tons of same questions. So it got many downvotes, obviously. However, I wanted to reply him because I was once a Newbie too. My Reply If you are thinking Codeforces as a 'tutorial' site, you are in the wrong place. That's why you are get..
2021.01.21 19:22 -
Persistent Segment Tree 구현 메모
난 이 글의 마지막 부분을 보고 퍼시스턴트 세그먼트 트리를 익혔다. 일단 내 나름대로 퍼시스턴트 트리를 떠올려 보았다. 과거 기록을 모두 가지고 있는 트리. 때마침 수쿼22가 그런 컨셉의 문제였고, 나는 스스로 이 문제를 풀어보았다. 어떤 원소를 업데이트할 때 그 원소로 인해 업데이트 되는 세그먼트 트리의 노드는 최대 O(log N)개다. 그럼 각 쿼리마다 log N개의 '기록'만 추가된다는 것. 세그먼트 트리의 각 노드를 '벡터'로 만들어서 k번째 쿼리에는 이 값을 가지고 있었다는 사실을 저장하면 되지 않을까? 별도로 인덱스 배열을 만들어서 나는 'x번째 쿼리'때 이 값으로 변경되었어요~를 저장하면 추후 이분탐색으로 2번 쿼리를 처리할 수 있다. 구현 성공! 업뎃 쿼리는 O(log N), k번째 업뎃 ..
2021.01.18 22:43 -
Tree DP
www.secmem.org/blog/2019/02/10/TreeDP/ Tree DP 문제 해결 목차 1. 개요 2. 기본 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 알고리즘 공부를 하면서 오랫동안 다이나믹 프로그래밍을 그것도 트리에서 해결하는 문제를 꽤 안풀었음을 www.secmem.org codeforces.com/blog/entry/20935 DP on Trees Tutorial - Codeforces codeforces.com www.commonlounge.com/discussion/8573ee40c4cb4673824c867715a5bc7b Dynamic Programming on Trees (or Tree DP) | CommonLounge In this tutori..
2020.12.14 01:28 -
BFS 메모리 줄이는 방법
BFS에서 visit 배열을 거리 저장 용도로 사용하고는 한다. int vis[N][M]={}, dr[] = {1,0,-1,0}, dc[] = {0,1,0,-1}; queue q; q.push({sr,sc}); vis[sr][sc] = 1; while(!q.empty()){ auto t = q.front(); q.pop(); int r = t.first, c = t.second; for(int i=0;i0 ; sz--){ auto t = q.front(); q.pop(); int r = t.first, c = t.second; if(r==er && c==ec) return dist; for(int i=0;i0; sz--) 이 for문이 dist 값을 가진 노드들만이 큐에서 빠지게 해준다.
2020.11.18 12:18 -
Li Chao Tree 공부
어떤 기술 X의 사용 범위를 R(X)라 나타내자. R(Convex Hull Tree ) > 1; /* m에서 high가 더 크면 왼쪽에 high 넘기고 오른쪽 업데이트 */ if(cmp(high,low,m)) { tree[nd].v=high; if(tree[nd].r==-1) {..
2020.11.14 23:11 -
Knuth Optimization
DP Optimization Technique 정의 $ cost[i][j] $가 특정 조건을 만족할 때 아래 dp에서 최적화를 적용할 수 있다. $ dp[i][j] = \min_{i
2020.11.12 10:12 -
KOI에 등장하는 DP 문제들 #2
2020.09.29 1. 부동산 투자 codeup.kr/problem.php?id=3724 정수 수열에서 연속된 1부분 또는 2부분을 골라 합을 최대화하는 문제. 수열 길이 N 0 : Left[N] = dt[N-1] else : Left[N] = N dtR[N] : N번째 수를 시작으로 하는 구간을 고를 때, 구간합의 최대 dt[N]과 똑같이 구한다. mdt[N]을 dt[1]~dt[N] 중 max로 정의하자. mdtR도 마찬가지. dt[N] 중 최대를 구한 후 모든 합최대구간 중 max( mdt[left[N]-1] , mdtR[N+1] , 0)을 구해 2번째 합최대 구간을 구한다. 구현! 놀랍게도 반례가 있었다. 합최대구간을 고르지 않는게 최대일 수도 있다. 위 증명에서 A1,A2중 적어도 하나는 X와 ..
2020.09.29 16:44 -
모든 Mother Vertex를 O(V+E)에 구하는 알고리즘
발행일 : 2020-07-08 UPD1 : 2020-09-25 Find All Mother Vertices in a directed graph. Mother Vertex. 어떤 방향 그래프에서 한 정점이 다른 모든 정점에 도달할 수 있다면 이를 Mother Vertex라 부른다. 이 글에서는 방향 그래프에서 존재하는 모든 Mother Vertex를 구하는 방법에 대해 알아본다. Existence of a Mother Vertex Mother Vertex의 존재성을 판정하는 방법은 두가지가 있다. 첫번째 방법은 각 정점에서 방문이 가능한 정점을 저장하는 bitset을 생성한다. 모든 비트가 체크된 노드가 있다면 그것은 Mother Vertex이다. DFS를 통해 bitset을 갱신한다. 주의할 것은 한번의..
2020.09.25 17:47 -
특정 조건에서 LCS를 O((n+m) log (nm))에 구하는 알고리즘
*LCS Longest Common Subsequence. Subsequence는 부분수열들이 꼭 연속하지 않아도 된다. 예를 들어 두 수열 A,B가 있다 하자. A = 1 5 3 4 2 6 5 B = 1 6 3 2 3 5 A와 B의 부분 수열은 {1}, {3}, {1,2} 등 여러가지가 있다. A와 B의 LCS는 {1,3,4,5}이고 그 길이는 4이다. A의 길이를 n, B의 길이를 m이라 할 때 다이나믹 프로그래밍을 이용해 O(nm)의 시간에 LCS(A,B)를 구할 수 있다. 이는 잘 알려져 있는 알고리즘이므로 쉽게 설명된 글이 많다. 이 글에서는 특정 상황에서 빠르게 LCS를 구하는 방법에 집중한다. 또한 앞으로 LCS를 구하는 것을 LCS의 길이를 구하는 것과 동일하게 취급한다. *특정 조건에서 ..
2020.09.25 16:16 -
과반수 원소 알고리즘
Majority Element / Majority Vote Algorithm 주어진 리스트에서 과반수를 차지하는 원소의 존재성 판정과, 존재 시 과반수 원소를 구하는 알고리즘. A[] = { 1, 3, 1, 1, 2} 리스트 A에서 과반수 원소는 1이다. 정렬하면 슥삭 풀리는 문제이지만 O(N) 시간복잡도에 가능한 알고리즘이 존재한다. O(N) Solution 내가 소개할 것 : Pair 매칭 알고리즘. *기존 길이 $n$ 리스트 A로부터 길이 $[n/2]$ 리스트 B를 만든다. N이 짝수일 때 : 앞에서부터 차례대로 2개씩 묶는다. 각각의 pair (x,y)에 대해 x==y면 하나만 남기고, x!=y면 둘 다 제거한다. A[]={1,3,1,1,2,1} 을 예시로 들자면 (1,3) => (), (1,1)..
2020.08.20 00:40 -
Convex Hull과 Sorting의 관계
정렬 문제를 Convex Hull 문제로 환원하는 방법을 소개합니다. Convex Hull 문제를 정렬 문제로 환원할 수 있다는 것은 널리 알려져 있는 사실이다. Graham Scan알고리즘은 점들을 각도 순으로 정렬한 뒤 한 번의 스캔을 통해 Convex Hull을 구하는 알고리즘이기 때문이다. 곧, 다항 시간 내에 Convex Hull 문제를 점들을 정렬하는 문제로 환원할 수 있다. 여기서는 정렬 후에 이루어지는 스캔 (O(N))이 변환 시간이 된다. 다음과 같이 나타낸다. 여기까지는 Convex Hull과 다항식 시간 변환의 개념을 안다면 누구나 알 수 있는 사실이다. 한 발 더 나아가보자. 정렬 문제를 Convex Hull을 구하는 문제로 변환할 수 있을까? 즉, Convex Hull을 구하는 알..
2020.08.15 12:46 -
첫 Codeforces
Codeforces Div.3에 처음으로 참여했다. https://codeforces.com/contest/1367 Dashboard - Codeforces Round #650 (Div. 3) - Codeforces codeforces.com A,B,C는 문제를 빠르게 읽는 것에 경각심을 느끼게 해주었다. D,E는 문자열 다루기에 익숙해지라는 것을 가르쳐주었다. F1,F2는, 내가 아이디어에 강하지만 애매한 구현을 더 연습해야 좋은 결과를 낼 수 있다는 조언을 주었다. 새벽에 재밌었다.
2020.06.17 01:59 -
강 건너기 문제
※이 글은 사람이 10명 이하일 때의 알고리즘입니다. Large 문제의 해법은 0000 원하는 상태 ==> 1111 이 된다. 탐색 알고리즘 n이 7 이하이기 때문에 사람들이 분포될 수 있는 경우의 수는 2^7 * 2(배의 위치) = 256 으로 매우 작다. 그렇기 때문에 브루트 포스 (DFS)로 충분히 해결될 수 있을 것이라 보았지만 웬걸, 83퍼에서 시간 초과가 걸리고 말았다. 다시 생각해보니 256개의 정점이 있는 것이더라.. 일반적인 DFS로 풀 경우 지수함수에 비례하는 시간이 걸리므로 시간 초과가 날 수 밖에 없다. 그럼 지금 구해야 하는 것은 가중치 그래프에서의 최단 거리이다. 그렇다면 역시 다익스트라 알고리즘을 사용하자. 아래 풀이를 이해하기 위해서는 다익스트라 알고리즘에 대한 기본적인 이해..
2020.02.02 20:23