https://codeforces.com/profile/Pentagon03  UCPC 2024 직전에 달성하였습니다. 막상 원할 때는 닿을듯 말듯 하던 것이, 힘 빼고 편안하게 코딩하니 결과가 좋게 나오는 경험입니다.   Div.2 2솔 하고 다시는 안 갈줄 알았던 블루도 가봤습니다. 이후 코포를 잘 못한다는걸 인정하고 계속 응시하니 신기하게도 점점 문제가 잘 풀리네요. 항상 에듀 라운드는 등수가 잘 안 나오는 경향이 있어 꺼리다가,UCPC 전 마지막 기회라 생각하고 도전한 것이 좋은 결과로 돌아와서 정말 행복했습니다. 모두 행운을 빕니다!

한글 문제는 다음 참고: 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로 인식 되어 문제가 생긴다.이게 두 변수가 붙어 있어서 단순히 ""을..

안녕하세요, pentagon03입니다.알고리즘 프로그래밍을 즐기며, 제가 관심 있는 것들에 대한 글을 작성합니다.프로필 링크Baekjoon Solved.Ac Codeforces Github 알고리즘 과외 또한 진행하고 있습니다. (Korean / English)C++/Python/USACO/Competitive Programming pentagon03.codes@gmail.com 혹은 Discord: pentagon03위 채널을 이용하여 문의해주시면 답변 드리겠습니다.

언제나 그렇듯이 잘 풀리면 상관 없는 것들내적 해시- 존재성만 확인하면 되는 상황이라면 굳이 복잡한 라빈카프가 아니라 랜덤 포인트 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..

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..

https://master.d66dlzauezpcp.amplifyapp.com/pentagon031~3일차 푼 문제 정리를 해볼까 한다. 티어는 푼 시점 기준이다. 볼드체 해놓은 문제는 어려웠던거나 추하는것.1일차12581Your Rank is Pure (Small)골546분 대망의 첫 문제고 골드가 나와서 당황했다.dp로 잘 비빌 수 있을거 같지만 n이 작아서 비트마스크로 모든 가능한 경우를 다 해보는 쪽으로 방향을 선회했다.Off-by-One error의 심각성을 확연히 알 수 있었던 문제.구현하면서도 계속 헷갈려서 46분을 허비했다. 비트마스크만 나오면 요상한? 최적화를 해서 등수를 높이려는 욕심이 있는데 여기서 이걸 확실히 느꼈다. --- 23884알고리즘 수업 - 선택 정렬 4골414분 다음 문..

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$까지 가는 모든 간선을 끊는 ..

https://people.cs.uchicago.edu/~borja/pubs/sigcse2016-programming-contests.pdf 이 글은 Aaron Bloomfield와 Borja Sotomayor의 "A Programming Contest Strategy Guide"를 읽고 한국어로 요약한 내용입니다. 핵심을 간단하게 전달하기 위해 필자의 해석이 담겨 원문과 다른 내용이 있을 수 있습니다. 세줄 요약 저자는 북미 대학 ICPC 코치들이다. 1999년 이후로 한 번도 북미 출신 대학이 우승 못하고 항상 러시아 / 중국 / 폴란드만 우승한다는 사실에 안타까움을 금치 못한다. 따라서 "어떤 팀들이 ICPC에서 활약하는가"를 자신들의 월드파이널(줄여서 월파) 코치 경험을 통해 사례 기반 연구하여 ..

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..

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-05 오늘 끝냈다. PS를 제대로 하기로 다짐한 사람이라면 단계별로 풀어보기부터 강의 듣듯이 빠르게 배운 후 OI / ICPC 스타일 문제를 풀어보는 것도 하나의 가장 효율적인 방법이라고 생각한다. 하나의 Tool Box를 다 채우고 시작하는 느낌.

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..

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..

- 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++ 관련 확장 프로그램..

*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..

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..

상위 100개 문제를 다이아 이상의 문제로 채웠다! 공부하고 연습한 기록이 이만큼 쌓여서 뿌듯하다. 이제는 사고력을 키워보자. 스스로 사고해서 문제를 풀어내는 것이 재밌어지는 그날까지 연습!

정말 주세혁은 레전드다.. 9년 전 월드컵 경기. 저 때가 그들의 최정점이 아니라면 언제일까 주세혁의 수비수 플레이는 스스로 기회를 만들어나간다는 점에서 정말 멋지다고 생각한다. 저렇게 빠른 공을 여유롭게 받을 수 있을 때까지 얼마나 많은 연습을 했을까 탁구를 한 번이라도 쳐봤다면 저렇게 수비하는 게 보이는 것보다 수백배 어렵다는 사실을 깨달을 것이다. 아무 회전 없이 공을 넘기는 데만 해도 온 신경을 기울여야 하는데, 저렇게 빠른 스매시 / 상회전 걸린 드라이브 등을 자유롭게 방향까지 조절해가며 커트를 친다. 한편 티모 볼 또한 대단한 선수이다. 티모 볼은 독일 선수로, 중국이 점령하고 있던 현대 탁구에서 세계 1등까지 찍었다. 당시 유럽에서 영웅 취급을 받았다고 ㅎㅎ 잘생김 + 매너 있는 행동으로 인..

*Reference의 번역과 필자의 분석이 담긴 글입니다. 글을 인용하거나 공유할 때는 이 글의 주소를 맨 위에 표시해주시기 바랍니다. 감사합니다. 1. 공의 회전을 분석한다 임팩트 순간에 상대방의 라켓의 이동방향을 본다. (관찰자가 상대편의 라켓을 봤을 때) 아래에서 위로 => 상회전 위에서 아래로 => 하회전 왼쪽에서 오른쪽으로 => 왼쪽으로 휘어진다 오른쪽에서 왼쪽으로 => 오른쪽으로 휘어진다 손목 스냅과 사선 방향 타격은 횡회전이 섞인 상회전, 하회전 공을 만든다. 상대방이 전면으로 공을 빗겨 칠 때, 라켓이 공 오른쪽에 있을 경우는 공이 왼쪽으로 휜다. 라켓이 공 왼쪽에 있을 경우는 공이 오른쪽으로 휜다. *공의 방향는 임팩트 방향과 관련이 있다. ($\vec F = m\vec a$). 특히 서..

Special Thanks to Cgiosy Slope Trick: 함수 개형을 이용한 최적화 백준 13323 BOJ 수열 1 풀이 백준 13324 BOJ 수열 2 풀이 *20210513 수정#1 2021/05/13 정보과학세미나 시간에 보고서 및 발표자료의 내용으로 사용함. WhiteBoard Tutorial BOJ수열1 BOJ수열2

나도 다른 블로그를 참 많이 읽는다.나만 그런 것인지는 모르겠지만알고리즘 글을 읽을 때 유난히"이게 무슨 개소리야" 하는 상황이 많이 닥친다.철없을 때는 다른 사람이 글 참 못 쓴다.. 생각했지만내가 블로그를 해보고 나니, 그 귀차니즘에 대해 이해해버렸다.문제 풀고 맞추는게 재밌지, 그 지식을 다른 사람에게 전달하는 것에서 재미를 느끼는 것은 또 전혀 다르다.흥미를 느끼지 않는데 글이 술술 잘 써질리 전무하다.그런데, 대부분 그 사실을 잘 모른다. 알고리즘 정리/문제 풀이 글에는 대부분 댓글이 거의 달리지 않기 때문이다. (...)내 블로그를 떠나서 PS블로그계는 정말 질문에 인색하다는 생각이 많이 든다.나부터도 글을 읽다 막혀도 대부분 혼자 고민하고, 정 안되면 다른 글로 그냥 넘어간다.다른 분들도 마..

센트로이드 분할 1. 존재의의 센트로이드 분할 = 트리에서의 분할 정복 기법 트리에서 어떠한 문제( i.e.) 길이가 K인 경로의 개수를 구하라)를 해결해야 될 때 트리를 크기가 더 작은 서브 트리들로 분할하여 문제를 적용한다. 이때 효율적인 분할의 대표적인 기법이 센트로이드 분할이다. 2. 센트로이드란 트리의 무게중심인 정점. 트리를 어떤 정점을 기준으로 차수만큼의 서브트리들로 나눌 수 있다. 이때 모든 서브트리의 크기가 전체 트리 크기의 절반 이하일 때, 그 정점을 Centroid라 한다. Q) 센트로이드는 항상 존재하는가? A) 그렇다 증명 1) 센트로이드 탐색 알고리즘 임의의 노드를 고르자. 그 노드를 루트로 하는 트리를 생각한다. 모든 서브트리의 크기가 조건을 만족한다면 그 노드가 센트로이드다...

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

이정도로 망친건 꽤나 오랜만이다.애드혹, 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분 가량 붙들었다. 펑파라메트릭이 성립할 ..

codeforces.com/contest/1486 총평: 전체적으로 문제 셋이 재밌었고 선방했다. 정확히 1달만에 즉흥적으로 친 코포라 걱정 반 설렘 반이였는데 오히려 더 나은 결과를 얻었다 A -> B -> C1 -> C2 -> E 순으로 풀었다. A는 직관적으로 생각하면 쉬울 것을 너무 성급하게 찍어버렸다. i -> i+1 단방향만 가능하므로 i=0->n-1까지 따라가면서 가능한지 검사하는게 중요 포인트 B는 수학. 무난히 빨리 풀었다. C1, C2는 재미있는 인터랙티브 문제이니 꼭 풀어보는 것을 추천한다. 로그를 붙이는 다양한 알고리즘에 관하여 숙고한 경험이었다. C1 구현에 오래 걸리고, C2는 자칫 못 풀 뻔 했지만 관점을 완전히 바꾸니 시간 투자 후 해결할 수 있었다. E는 다익스트라 문제인데..

최근 Solved.ac 티어 계산 시스템이 바뀌었다. 1번 항목과 2번 항목은 푼 문제를 어려운 순으로 정렬해 상위 100개 문제를 합산하는 것으로 수정되었다. 솔브드 Slack에서 얻은 정보들이다. 첨언 하자면 푼 문제 수에 따른 값은 최대 175이며, 거의 증가하지 않는다. 675문제 푼 내가 169점이고, 9000문제 가량 푸신 구사과님이 175점인 것을 보면 된다! 기여 수에 따른 값은 최대 25이고 135문제 기여 -> 25, 8문제 기여 -> 14인 것을 보면 티어와 거의 무관한 수치다. 티어와 가장 유관한 것은 푼 문제들 중 가장 어려운 것과 클래스가 되시겠다. 다이아, 루비를 많이 풀자 의도

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..

난 이 글의 마지막 부분을 보고 퍼시스턴트 세그먼트 트리를 익혔다. 일단 내 나름대로 퍼시스턴트 트리를 떠올려 보았다. 과거 기록을 모두 가지고 있는 트리. 때마침 수쿼22가 그런 컨셉의 문제였고, 나는 스스로 이 문제를 풀어보았다. 어떤 원소를 업데이트할 때 그 원소로 인해 업데이트 되는 세그먼트 트리의 노드는 최대 O(log N)개다. 그럼 각 쿼리마다 log N개의 '기록'만 추가된다는 것. 세그먼트 트리의 각 노드를 '벡터'로 만들어서 k번째 쿼리에는 이 값을 가지고 있었다는 사실을 저장하면 되지 않을까? 별도로 인덱스 배열을 만들어서 나는 'x번째 쿼리'때 이 값으로 변경되었어요~를 저장하면 추후 이분탐색으로 2번 쿼리를 처리할 수 있다. 구현 성공! 업뎃 쿼리는 O(log N), k번째 업뎃 ..

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..

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 값을 가진 노드들만이 큐에서 빠지게 해준다.

어떤 기술 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) {..

DP Optimization Technique 정의 $ cost[i][j] $가 특정 조건을 만족할 때 아래 dp에서 최적화를 적용할 수 있다. $ dp[i][j] = \min_{i

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-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을 갱신한다. 주의할 것은 한번의..

*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의 길이를 구하는 것과 동일하게 취급한다. *특정 조건에서 ..

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)..

정렬 문제를 Convex Hull 문제로 환원하는 방법을 소개합니다. Convex Hull 문제를 정렬 문제로 환원할 수 있다는 것은 널리 알려져 있는 사실이다. Graham Scan알고리즘은 점들을 각도 순으로 정렬한 뒤 한 번의 스캔을 통해 Convex Hull을 구하는 알고리즘이기 때문이다. 곧, 다항 시간 내에 Convex Hull 문제를 점들을 정렬하는 문제로 환원할 수 있다. 여기서는 정렬 후에 이루어지는 스캔 (O(N))이 변환 시간이 된다. 다음과 같이 나타낸다. 여기까지는 Convex Hull과 다항식 시간 변환의 개념을 안다면 누구나 알 수 있는 사실이다. 한 발 더 나아가보자. 정렬 문제를 Convex Hull을 구하는 문제로 변환할 수 있을까? 즉, Convex Hull을 구하는 알..

Codeforces Div.3에 처음으로 참여했다. https://codeforces.com/contest/1367 Dashboard - Codeforces Round #650 (Div. 3) - Codeforces codeforces.com A,B,C는 문제를 빠르게 읽는 것에 경각심을 느끼게 해주었다. D,E는 문자열 다루기에 익숙해지라는 것을 가르쳐주었다. F1,F2는, 내가 아이디어에 강하지만 애매한 구현을 더 연습해야 좋은 결과를 낼 수 있다는 조언을 주었다. 새벽에 재밌었다.

※이 글은 사람이 10명 이하일 때의 알고리즘입니다. Large 문제의 해법은 0000 원하는 상태 ==> 1111 이 된다. 탐색 알고리즘 n이 7 이하이기 때문에 사람들이 분포될 수 있는 경우의 수는 2^7 * 2(배의 위치) = 256 으로 매우 작다. 그렇기 때문에 브루트 포스 (DFS)로 충분히 해결될 수 있을 것이라 보았지만 웬걸, 83퍼에서 시간 초과가 걸리고 말았다. 다시 생각해보니 256개의 정점이 있는 것이더라.. 일반적인 DFS로 풀 경우 지수함수에 비례하는 시간이 걸리므로 시간 초과가 날 수 밖에 없다. 그럼 지금 구해야 하는 것은 가중치 그래프에서의 최단 거리이다. 그렇다면 역시 다익스트라 알고리즘을 사용하자. 아래 풀이를 이해하기 위해서는 다익스트라 알고리즘에 대한 기본적인 이해..