구사과 - mysetting

3:03 5/30

koosaga.com

mobile screenshot relative

3:03

koosaga.com

mobile screenshot

구사과
https://koosaga.com/

저작도구: TISTORY

최종 피드 수집: 2025-06-04 10:46

전체 (72)

1y

Firefox UI Fix notes

알고리즘 하시던 분들을 현실에서 만나게 되면 자주 듣는 질문이 "왜 ID가 구사과인가" 라는 질문이다. PS를 시작한 것은 고등학교 때지만 "컴덕후" 로 살던 초등학생 시절이 있었다. 2008년 집에서 새로 산 (보급형) 컴퓨터에

생각

0023

1y

Randomized algorithms - 2023.12.08

Example 1 (https://koosaga.com/319 마지막 단락)
그래프가 주어질 때 이 그래프의 maximal independent set 을 구하는 문제를 생각해 보자.
maximal independent set은

CS theory

000

1y

2023.12.05 problem solving

PA 2016. Shuffle
문제에서 주어진 셔플 연산은 카드 덱을 뒤집는 연산과 동일합니다. 이 사실은 수학적 귀납법으로 증명 가능합니다.
$2$ 개의 카드에 대해서는 자명히 뒤집는 연산과 동일합니다.
$2^k$ 개의 카드에

Problem solving

000

1y

A deterministic near-linear time algorithm for ﬁnding minimum cuts in planar graphs

https://dl.acm.org/doi/pdf/10.5555/982792.982916
Cut-cycle duality에 의해 $G$ 에서 minimum cut을 찾는 것은 $G^*$ 에서 minimum cycle을 찾는 것과 동

CS theory

002

1y

3-edge-connectivity notes

대충 이 노트 의 끝자락에서 한 얘기를 정리했다.
그래프가 2-edge-connected 라고 가정하자. (그렇지 않다고 하더라도 코드가 크게 바뀌지 않는다)
알고리즘은 재귀적이다. 그래프 $G$ 의 DFS 트리에 대해서, 특정

Problem solving

002

1y

Incremental approximate $s - t$ max flow in $m^{1/2+o(1)}$ update time

https://arxiv.org/pdf/2211.09606.pdf
생각보다 내용이 많이 쉬워서 살짝 날먹이라고도 생각했다. 일단 핵심 내용은 다음과 같은 알고리즘의 존재성이다:
$s, t$ flow가 $T$ 이하일때까지 $s, t

CS theory

000

1y

2023.10.22 problem solving notes

Min-plus convolution
두 수열 $A = [a_0, a_1, ..., a_n]$, $B = [b_0, b_1,..., b_m]$ 이 있을 때 $c_k = \min_{k = i + j}(a_i + b_j)$ 를 구하는

Problem solving

000

1y

IOI 2023 Day 2

IOI 2023 Day 2 대회가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다.
박상훈, 43 / 60 / 65.5 / 31 / 100 / 54, 353.5점, 22등 (금메달)
이동현, 52 / 70 / 65.5 / 31

Problem solving

003

1y

IOI 2023 Day 1

IOI 2023 Day 1 대회가 종료되었다. 올해 대회의 개최지는 헝가리로, 한국 팀은 2019년 이후 처음으로 현지에서 오프라인으로 대회를 진행하고 있다.
한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점

Problem solving

002

1y

2023.08.29 problem solving

Algorithmic Engagements 2021. Koszulki
수열을 역순으로 정렬한 후 값이 $a_k$ 이상인 수를 출력하면 됩니다.
POI 2019/2020. Najmniejsza wspólna wielokrotnoś

Problem solving

000

1y

2023.08.13 problem solving

2023년 정보화진흥원 역량강화 교육 내용을 바탕으로 작성합니다. AC로 검증 못한 풀이들이 있어 주의를 요합니다.
2차 교육
B: L과 R의 중간 지점을 기준으로, 왼쪽에 있다면 R+1에 갈 필요가 없고, 오른쪽에 있다면 L-1

Problem solving

000

1y

현대모비스 본선 / UCPC 2023 후기

그냥 아카이빙 목적으로 짧게 씁니다.
현대모비스 본선 대회
본인은 2021년 대회에서 8등인지 9등인지 했고, 2022년 대회에서 예선 탈락을 해서, 2023년 대회 참가가 가능했다.
1번을 열었는데 딱 봐도 따져야 할게 많아 보

생각

003

1y

Introduction to Distributed Graph Algorithms

많은 일반적인 알고리즘은 하나의 프로세서에서 작동함을 가정하지만, 현실의 계산에서는 컴퓨팅 기계가 하나의 프로세서가 아닌 여러 프로세서를 사용할 수도 있다. Parallel Algorithm의 경우는 효율성을 위해서 여러 개의 프

CS theory

000

2y

Deep Cuts

(2023/05/19 최근 과제들을 추가했습니다.)
(2020/06/13 6월 과제가 완성되어서 공개했습니다.)
(2020/04/18 초판 작성.)
이미 아시는 분들도 계시겠지만, 2017년 가을 이후 포스팅되는 대부분의 글은 삼

공부

000

2y

Separating Hyperplanes, Lagrange Multipliers, KKT Conditions, and Convex Duality

1. Separating Hyperplane Theorem
2차원 평면에 겹치지 않는 두 원이 있을 때, 두 원을 분리하는 직선을 찾을 수 있을까? 다시 말해, 직선의 한 쪽에 첫 번째 원이, 직선의 다른 쪽에 두 번째 원이 존재

공부

000

2y

The Cut-Matching Game: Expanders via Max Flow

알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 알고리즘 연구에서 분할 정복이 가지는 중요성은 어

공부

000

2y

구간 최장 증가 부분 수열 쿼리 (Part 2)

티스토리 렌더링 문제로 수식이 많이 깨진다. 일단 깨진 형태로 올려두지만 쉽게 볼 수 있는 PDF를 첨부한다. PDF를 보는 것을 추천한다.
Chapter 4. $\boxdot$ 연산자의 빠른 구현
현재 우리의 알고리즘이 $O(N

공부

000

2y

구간 최장 증가 부분 수열 쿼리 (Part 1)

티스토리 렌더링 문제로 수식이 많이 깨진다. 일단 깨진 형태로 올려두지만 쉽게 볼 수 있는 PDF를 첨부한다. PDF를 보는 것을 추천한다.
이번 글에서는 다음과 같은 쿼리를 수행하는 자료 구조에 대해 다룬다:
길이 $N$ 의 수

공부

000

2y

Suffix Automaton

문자열의 부분문자열에 대한 복잡한 문제를 풀 때 Suffix Array와 같은 접미사 구조 는 아주 강력한 도구가 된다. SCPC 2021 3번, 서울 리저널 2022 H 등 여러 중요한 대회에서도 이러한 접미사 구조를 응용한 문

공부

000

2y

APIO 2019 Bridges is not easier than Undirected Unit APSP

두 $n \times n$ 행렬 $A, B$ 의 Min-Max Product는 $C_{i, j} = \min_k \max(A_{i, k}, B_{k, j})$ 로 정의된다. 만약 이 문제를 $T(n)$ 시간에 해결할 수 있다고 하

공부

000