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 Hay BOJ 6116 케이크 1st Step First, 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 event..

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

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

Link to original note: [[Flow Graph]] Cut은 Flow Graph에서 정점 s에서 t까지 가는 유량이 없도록 어떤 간선들을 자를 때, 그 간선들의 집합을 의미한다. 이때 Min Cut이란 간선 용량의 합이 최소가 되는 집합을 의미한다. 먼저 모든 flow f에 대하여 모든 cut C와의 관계를 알아보자. |f| t flow는 A->B flow의 크기와 똑같고, 이는 A->B 용량보다 작거나 같으므로 |f| e.g f(u,v) V-S로 향하는 간선은 없다. 따라서 모든 V-S -> S 간선만 보자. V-S에 속한 정점을 v, S에 속한 정점을 u라고 할 때 1)v -> u가 역간선일 경우 u->v가 존재하면 안되므로, u->v의 여유 용량은 0이다, 즉 f(u,v) = c(u..

체크리스트 대부분의 IDE에서는 컴파일 에러 이유를 보여줍니다. 모든 실행문 끝에는 세미콜론을 적었나요? 지금 사용한 변수를 선언했나요? 중괄호가 열렸다면, 닫혀야 합니다. '들여쓰기’를 맞추면 코드가 눈에 보입니다. 'A’와 A는 다릅니다. main 함수 안에 있는 변수는 자동으로 초기화되지 않습니다. scanf에 들어가는 인자들은 주솟값이어야 합니다. &를 붙였나요? scanf에서 공백과 줄바꿈 문자를 넣지는 않았나요? scanf/printf에서 형식 지정자를 잘 맞췄나요? 문제의 입력과 출력 부분, 조건을 다시 한 번 꼼꼼히 읽어보세요. 자료형을 확인하세요. 실수 계산을 정수 계산으로 대체할 수 있나요? 배열 인덱스를 확인하세요. 배열 크기는 늘 넉넉하게 잡는 것이 편합니다. 함수가 제대로 동작하지..

Link to original note: 2023-10-26 목 10:34:07 종이에 생각중 10:40:31 문제 요약 ${A_{i}}$ 가 있을 때 적당한 순서로 배열해서 $$S = \sum_{i=1}^{n}{i*A_{i}}$$ 를 maximize 해야 한다. 이제 $Q$개의 쿼리가 들어온다. 쿼리 $i ; j$는 $A_i$를 $j$로 바꿨을 때, $S$의 최댓값을 구하고, $A_i$를 원상복구 시키는 것이다. 문제 풀이 당연히, 그리디 하게 ${A_{i}}$ 를 단조 증가하도록 바꾼 ${B_{i}}$ 를 관리하면 된다. ${B_{i}}$ 에서 최댓값이 나오기 때문이다. 편의 상 $B_{0}=-\infty, B_{n+1} = \infty$ 로 두자. $id_{i}$를 $A_{i}$의 $B_i$에서의 ..

보호되어 있는 글입니다.

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

고등학교 때 처음 보고, 굉장히 오랫동안 풀고 싶어했던 문제들입니다. https://www.acmicpc.net/problem/2625 2625번: DNA유사도 모든 생물의 DNA 서열은 A, C, G, T 네 개의 문자로만 표현된다. 한 DNA 서열에서 두 문자의 거리 는 두 문자 사이에 있는 문자들의 개수이다. DNA 서열의 부분서열은 DNA 서열에서 몇 개의 문자를 제 거 www.acmicpc.net 이 가혹한 문자열 문제에 가로막혀 오랫동안 생각하지 않고 있다가, 북마크를 보고 다시 떠올려 오늘 해결했습니다. 더보기 기본적으로 최장길이는 O(N^2K^2) dp를 통하여 LCS/편집거리와 비슷하게, 쉽게 구할 수 있다. 한 단계 발전시켜 한 방향으로 덱이나 누적합 등을 사용하면 O(N^2K)에 구할..

https://www.acmicpc.net/problem/26035 PS는 원래 폰으로 하는거다. 추가) 이 문제는 우리 갓 https://www.acmicpc.net/user/heeda0528가 만든 갓 문제입니다. 모두 찬양하시기 바랍니다.

https://www.acmicpc.net/problem/25972 문제를 과대해석 하는 경향이 있다. 오 이거 재밌겠는데? 하는 생각이 들면 그렇게 문제를 풀어버린다. 정렬하면 모든 도미노는 인접한 도미노에만 영향을 준다.

https://www.acmicpc.net/problem/3679 3679번: 단순 다각형 첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트 케이스의 첫 번째 숫자는 점의 개수 n (3 ≤ n ≤ 2000) 이다. 다음 숫자는 점의 좌 www.acmicpc.net CCW 정렬하면 될 것이라는 추측 실제로 된다. 1. 왼쪽 아래 점 (기준 8개 다 된다. 아래 오른쪽, 왼쪽 위 등) 기준으로 정렬 2. ccw가 같은 마지막 t개(t>=1) 점들의 경우 순서를 뒤집어주자. = 거리가 가까운 것부터 이어야 하므로

https://www.acmicpc.net/problem/20295 난이도 기여 창에서 추천 받은 문제 심플 비트마스킹이 편하지만 배열을 써도 충분히 여유로울듯 하다. 1e5 * 20 * 5 = 1e7 1-based랑 0-based를 헷갈려서 디버깅 때 고생 좀 했다. 되도록 0-based로 통일하자. 이런식으로 디버깅 매크로를 만들어서 쓰는데 주석을 안 치고 제출하면 "시간초과"를 받는다. 로컬에서 디버깅하고 주석 안 쳐도 되게 만들었다. http://boj.kr/1b071128a8194d42bbf23c604971e9fa

https://www.acmicpc.net/problem/3176 이 문제를 아직까지 안 풀었었다니! sparse table 이용한 LCA 기본형 문제. HLD도 이용할 수 있다. LCA할 때 이런 식으로 i를 -1까지 보내면 한층 편하다. 코드가 못생겨지지만 편한게 장땡.

https://www.acmicpc.net/problem/13334 http://boj.kr/d7291475a4294aa58c892481968bf9e3 문제를 보자 말자 세그나 mergesort tree 풀이만 생각나서 고생했다. 골드2인데, 그게 정해일리도 없을 뿐더러, 구현이 빠른 풀이를 생각해보고 싶었다. 문제를 보면 2가지 접근이 기본적으로 생각난다. 스위핑 혹은 파라메트릭 서치. 이 문제의 경우 파라메트릭이 오히려 더 어렵다. 바로 스위핑으로 접근해도 된다. 위치를 받아서 선분 형태로 만들어주고 끝점 기준으로 정렬한 뒤 시작 점들만 관리해주면 된다. 현재 보고 있는 끝점을 b라 했을 때 지금까지 추가해준 시작점들 중에서 b-d 이상인 개수만 구해주면 된다. 시작점을 a라 하면 a도 정렬되게 관리..

http://boj.kr/943e1681a633468ea54da59124647d2d 공유 소스 보기 www.acmicpc.net 단조스택에 한 방 먹었다. 나였으면 i v[j] , v[i] == v[j] 인 경우 나눠서 세그로 비비고 복잡하게 쓰는 풀이만 떠올랐다. 스택.. 스택은 일단 단조 증가, 단조 감소 한 번 박아놓고 그때부터 명확하게 생각하는게 중요하다. '스택에 있는 값'에 대해 현재의 값을 보는 건지 현재의 값에 대해 '스택에 있는 값'을 보는 건지 알아내면 문제는 끝.

"문제를 잘 읽기" 얼리어답터가 아닐 경우, 친구 중 한 명만 얼리어답터면 되는줄 알았다. 이 문제는 모두 얼리어답터야 하므로 dfs 한 번만 돌리면 된다 http://boj.kr/0fe8012660474815898b5860116efc1e 친구 중 한명만 얼리어답터여도 되면 어떻게 풀어야 할까? N^2말고 N으로. N^2 문제를 만들면 사람들이 N으로 잘 풀어줄거다. “인터넷에서 원하는 답을 얻으려면, 질문 말고 틀린 답을 올리면 된다." – 워드 커닝햄 Cunningham’s Law: “The best way to get the right answer on the Internet is not to ask a question, but to post the wrong answer.”

https://www.acmicpc.net/problem/1533 http://boj.kr/42cd430fb1f94613bdc6b6d2feb6a7fd 인접행렬 거듭제곱이라는 개념을 사용해야 하는건 본대 산책 시리즈를 풀어봤으면 바로 보인다. 다만 길에 가중치가 있어 이를 적절히 1짜리 길로 나누어줘야 하는데, 각 길마다 정점을 새로 만들어주면 N = 10*10*5 = 500으로 행렬 곱셈을 할 때 시간이 너무 많이 걸린다. 따라서 각 정점마다 4개의 새로운 정점을 추가하는 방식으로 해결할 수 있다. 앞으로 바로 못 푼 문제나 신기한 아이디어를 사용하는 문제는 복습용 문제집에 저장해둔다. https://www.acmicpc.net/workbook/view/13241

https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net http://boj.kr/d30f68e9ef95427789c8bf855081ed79 dp: 시작 행의 상태, 끝 행의 상태를 기준으로 O(N*4*4) DP다. 재귀 dp를 한 1년만에 짜는 듯하다. 노가다 케이스워크 오랜만에 하니까 재밌었다. 나는 원형이기 때문에 양쪽 끝 4개씩 4*4=16개의 상태를 사용했는데 한쪽 4개만으로 가능하다. https:/..

컴퓨터를 초기화할 때마다 필자도 이 글을 켜고 설정한다. 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..

연습 주기를 바꿨습니다. 월화수목 셋은 4문제, 금토일 셋은 6문제 셋 제작자: pentagon03 A - 산업 스파이의 편지 B - 해킹 C - 시저 암호 D - 보안 업체 E - 수열과 쿼리 14 F - 여우 퀴즈 A. dfs + 에라토스테네스의 체 B. 우선순위큐로. 이를 구조화하면 다익이라고 하는데 다익 생각 안 나도 우선순위큐 쓰는게 당연해 보입니다 C. Step 1 원문을 쉬프트하는게 아니라, 거꾸로 암호문을 쉬프트합시다 Step2: 원문의 pi배열이 그대로이므로 각 쉬프트마다 빠르게 kmp를 쓸 수 있습니다~ D. Step1: 한 번 움직일 때 경로 상에 있는 모든 경유 점을 방문하는게 이득입니다. 즉 (start,start)구간에서 한 번 움직일 때마다 구간의 길이가 1씩 늘어나는 방식으로..

영진닷컴에서 진행하는 이벤트에 당첨되어 백엔드를 위한 GO 프로그래밍 책을 받았습니다. 아래는 파릇파릇한 새 책입니다. 디자인이 예뻐서 내용도 기대됩니다. 제가 매기는 책의 별점은 다음과 같습니다. 내용 4.9 / .5.0 구성/디자인 5.0 / 5.0 저는 개발보다는 컴퓨터 알고리즘 문제풀이에 훨씬 가중치가 많이 부여되어 있는 사람이므로 개발자나 개발입문자의 관점보다는 '새로운 언어에 관심이 있는, 취미로 코딩하는 사람'의 관점으로 책을 읽었습니다. 물론 책 제목에 '백엔드를 위한'이 붙어있으므로 "이 책 하나로 나도 백엔드 개발자?"라는 상상도 잠깐 했습니다. 어디까지나 상상입니다. 책의 내용, 구성, 그리고 실제로 배운 것 3가지에 대해 알아보겠습니다. 이 글은 계속 업데이트될 수 있습니다. UPD..

셋 제작자: surface03 A - LCM(1, 2, ..., n) B - Wiring C - 효율적으로 소 사기 D - The Bus E - 퀼린드롬 (Hard) F - Drum Decorator (Large) G - Justice for All 오늘, 내일 휴식 A: B: C: D: E: F: G:

셋 제작자: imtore A - 게임 닉네임 B - 마법의 문자열 C - 복붙하기 D - 가장 긴 공통 부분 문자열 E - 가장 긴 공통부분 팰린드롬 F - 적절한 문자열 문제 G - IQ 테스트 H - Sequence Conversion 2 I - 홀수 싸이클 A~F는 문자열 셋이고 G,H,I는 내가 참여하지 않았던 어떤 셋의 imtore님의 업솔빙이다. (이 3문제 빼고 다 업솔빙하셨다고 한다 :god:) A: 트라이 기본. 문자열의 끝을 나타낼 변수를 따로 정해줘야 합니다. http://boj.kr/2d9a845d3d0a4ab789996d416312ff7f B: 첫번째 단어는 고정시킬 수 있습니다. (하면 빠릅니다.) 가능한 모든 순열에 대해 이어붙인 문자열을 검사하면 됩니다. 방법1: 문자열을 $..

https://www.acmicpc.net/problem/4786 풀 때 도움 되는 몇가지 사실. 0. 표기: worker 수를 W, production 수를 P, 그 턴에서 적 수를 A 1. P랑 W의 관계를 파악하기 위해서 일단 모든 A를 0으로 가정할게요. 2. 각 턴에서 만들 수 있는 최대 army는 min(P,W)에요. 3. 마지막 두 턴에서 최대로 만들 수 있는 army의 수는 마지막 2번째에서 P,W를 기준으로 항상 min(P,W)+W에요. 증명은 케이스 나눠서 하면 돼요 4. 그러면 결국 마지막에서 3번째 턴까지 min(P,W) + W를 최대화 시키는게 목표가 되는데 여기서 그리디가 들어가요. 생각하기 쉬운게 P가 W보다 클 경우 W를 2배하고 W가 P보다 클 경우 돈을 P를 W로 키우는데..

셋 제작자: sean9892 A - 동차 수열 B - 핑크 플로이드 C - 복도 뚫기 D - Xor Maximization E - 성싶당 F - 2,3 거듭제곱의 합 G - XOR과 집합과 트리와 쿼리 H - 다각형 자르기 A: 모든 2x2 부분행렬만 살펴보면 됩니다. 각각의 독립인 위치에 대하여 버블 정렬 느낌으로 2개씩 교환했을 때도 값이 바뀌지 않아야 때문. https://www.acmicpc.net/source/share/fa847a663c5a45b99ac4074096e15d89 B:MST를 만들어주면 되는걸 알 수 있습니다. MST를 만드는 과정에서 가장 작은 경로를 고르기 때문. https://www.acmicpc.net/source/share/510077d7aed645fab6b9e1d3e1f..

0816부터 시작 클래스 5 더보기 클래스 5 안 푼 문제 중에 귀찮은 문제들이 많다 9328 열쇠 흔한 비트마스크 bfs 문제인줄 알았는데 열쇠 개수가 100개 문을 만나면 열쇠가 있는 경우 바로 큐에 삽입하고, 없다면 문 리스트에 삽입한다. bfs를 돌리는데 열쇠 하나를 새로 얻으면 지금까지 봤던 문 리스트에 있던 문들을 큐에 삽입한다. 맵 테두리를 0으로 감싸주면 single source bfs가 가능해서 구현이 훨~씬 편하다. 랜디 더보기 0816 A - 물병 B - 고층 건물 C - 방 번호 D - 롤러코스터 E - 큐빙 F - 스타 대결 A: 이진법으로 나타냈을 때 비트의 개수가 K개 이하인 N 이상의 최소 자연수를 구하면 됩니다. N이 작아서 __buitlin_popcount(X)로 반복문 ..