'분류 전체보기' 카테고리의 글 목록

Circulation

목표Circulation 문제를 Max Flow(혹은 Min Cost Flow) 문제로 환원시킬 수 있음을 이해한다.Circulation이란Definition주어진 flow graph $G(V, E)$에 대하여,$l(a, b)$: $a$에서 $b$로 가는 flow의 lower bound,$u(a, b)$: $a$에서 $b$로 가는 flow의 upper bound,$l(a,b) \le f(a,b) \le g(a,b)$를 만족하고$inflow(x) - outflow(x) = \sum\limits_{(v, x) \in E} f(v, x) - \sum\limits_{(x, v) \in E} f(x, v) = 0$을 만족한다.$src$와 $sink$가 정의되지 않았음에 유의하라.Min cost Circulatio..

2024.12.22

코드포스 오렌지 달성

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

2024.08.06

[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

About Me

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

2024.06.16

문제풀이 흑마법

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

랜덤디펜스 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

랜덤디펜스 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

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

[요약] 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

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

백준 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

백준 단계별로 풀어보기 완.

컨벡스헐부터 정체되어 있던 백준 단계별 풀어보기를 2024-02-05 오늘 끝냈다. PS를 제대로 하기로 다짐한 사람이라면 단계별로 풀어보기부터 강의 듣듯이 빠르게 배운 후 OI / ICPC 스타일 문제를 풀어보는 것도 하나의 가장 효율적인 방법이라고 생각한다. 하나의 Tool Box를 다 채우고 시작하는 느낌.

2024.02.05

USACO 가르치기

보호되어 있는 글입니다.

2023.10.07

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

보호되어 있는 글입니다.

보호되어 있는 글입니다.

[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

System Programming - Attack Lab

보호되어 있는 글입니다.

2022.10.28

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

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

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

Full Diamond

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

2021.06.11

주세혁 VS 티모 볼

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

보호되어 있는 글입니다.

보호되어 있는 글입니다.

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

2021.05.19

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

독자들에게 가끔씩 바라는 점

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

2021.03.09

Centroid Decomposition - 센트로이드 분할

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

2021.02.28

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

Pentagon

Pentagon

분류 전체보기(45)

티스토리툴바