티스토리 뷰

공부/기타

Deep Cuts

구사과 2023. 5. 19. 00:17

(2023/05/19 최근 과제들을 추가했습니다.)

(2020/06/13 6월 과제가 완성되어서 공개했습니다.)

(2020/04/18 초판 작성.)

이미 아시는 분들도 계시겠지만, 2017년 가을 이후 포스팅되는 대부분의 글은 삼성전자 SW멤버십의 지원을 받아 작성되고 있습니다. 매달 컴퓨터 과학에 관한 글을 주기적으로 SW멤버십에 제공하고, 이에 따른 지원금을 받는 식입니다. 비정기적으로 관리하던 블로그에 매달 주기적으로 글이 올라올 수 있게 된 것은 SW멤버십의 지원 덕분이 큽니다. 감사합니다.

SW멤버십에 제공하는 대다수의 글은 제 블로그에 같이 올립니다. 일반적으로 제출 기한이 있는 SW멤버십에 글을 먼저 제출한 후, 데드라인 안에 손보지 못한 부분이 있으면 이 부분을 보강해서 블로그에 올리는 식입니다. 잘못된 사실이나 오탈자 등도 블로그 글 우선으로 반영하기 때문에 (일반적으로는 SW멤버십 글도 반영하려고 하고 있으나 우선순위는 블로그가 높습니다.) 블로그에 올라오는 글이 약간 더 정리되어 있을 것입니다.

대다수의 글을 블로그에 같이 올린다고 하였으나, 올리지 않는 글들도 있습니다. 이들은 대부분

  • 글의 내용이 일반적인 알고리즘 문제 해결과 동떨어져 있거나
  • 작성자인 저도 잘 모르는 부분에 대한 글이라서 블로그에 올릴만큼 책임지기 힘들다고 판단했거나
  • 급하게 썼다 등등의 이유로 퀄리티가 떨어진다고 판단했거나
  • 까먹었거나, 부끄러웠거나, 귀찮았거나, 별 생각 없었거나, 등등...

등등의 이유로 블로그에 올라오지 않았습니다.

앞으로는 블로그 포스팅이 약간 뜸해질 수 있고 (지금 당장 쓰고 싶은 내용이 없습니다), 이러한 글들도 모두 공유해 드리는게 모두에게 좋을 것 같아서 이 글에 SW멤버쉽 과제로 올라온 모든 글을 공유하려고 합니다. 블로그에 올라오지 않으나 SW멤버십에 제출한 글이 추가될 때 마다 글을 업데이트할 예정입니다.

  • 2017년 11월: Concave Monge cost function을 가진 동적 계획법의 최적화
  • 2017년 12월: Undirected edge geography in grid graph
    • 상태: 포스팅하지 않음. 201712.pdf 참고
  • 2018년 1월: 방향 그래프에서의 Dominator Tree
  • 2018년 2월: EERTREE
    • 상태: 포스팅하지 않음. 201802.pdf 참고
  • 2018년 3월: 그래프의 최소 컷에 대하여
  • 2018년 5월: Proving the 5-color theorem
  • 2018년 6월: Offline Dynamic MST Problem
  • 2018년 7월: Atcoder Regular Contest 035-057
  • 2018년 8월: Scheduling Unit-time tasks with Release time and Deadline
  • 2018년 9월: Length-Bounded Cuts and approximation
    • 상태: 포스팅하지 않음. 201809.pdf 참고
    • 2018년 10월 부터 2019년 4월까지 작성 기록이 없는데 이 때 진짜 못한 건지 잃어버린 건지 기억이 나지 않는다.
  • 2019년 5월: Berlekamp-Massey
  • 2019년 6월: 계산 복잡도 위계와 불리언 식
  • 2019년 7월: 2019 KOI 중등부/고등부 해설
  • 2019년 8월: 2019 IOI 해설
  • 2019년 9월: $O(N^{1/4+e})$ 시간 복잡도에 소인수 분해하기
  • 2019년 10월: 장애물을 포함하지 않는 가장 큰 직사각형 찾기
  • 2019년 11월: 동적 계획법을 최적화하는 9가지 방법 (1/4)
  • 2019년 12월: 동적 계획법을 최적화하는 9가지 방법 (2/4)
  • 2020년 1월: Geometric spanning tree
    • 상태: 포스팅하지 않음. 202001.pdf 참고
  • 2020년 2월: 동적 계획법을 최적화하는 9가지 방법 (3/4)
  • 2020년 3월: 동적 계획법을 최적화하는 9가지 방법 (4/4)
  • 2020년 4월: FPT Inapproximability of Directed Multicut
    • 상태: 포스팅하지 않음. 202004.pdf 참고.
  • 2020년 5월: 그래프의 간선 색칠 문제
  • 2020년 6월: Parametrized inapproximability for Steiner Orientation by Gap Amplification
    • 상태: 포스팅하지 않음. 202006.pdf 참고.
  • 2020년 7월: Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
  • 2020년 8월: General Matching and applications
  • 2020년 9월: APIO 2020
  • 2020년 10월: IOI 2020
  • 2020년 11월: ACM-ICPC Seoul Regional 2020
  • 2020년 12월: Dynamic MSF with Subpolynomial Worst-case Update Time (Part 1)
  • 2021년 1월: Dynamic MSF with Subpolynomial Worst-case Update Time (Part 2)
  • 2021년 2월: Dynamic MSF with Subpolynomial Worst-case Update Time (Part 3)
  • 2021년 3월: Top Tree로 Dynamic Tree 관리하기
    • 상태: 포스팅하지 않음. 202103.pdf 및 Project-TCS S2L1 참고. (그렇게 좋은 글이 아니라고 생각해서 블로그에 올리지 않았습니다. 시간이 나면 제대로 다시 작성해서 올리고 싶네요)
  • 2021년 4월: Expander Decomposition and Pruning: Faster, Stronger, and Simpler
  • 2021년 5월: Incremental Topological Ordering and Strong Component Maintenance
  • 2021년 6월: Fully Dynamic Min Cut
    • 상태: 포스팅하지 않음. 202106.pdf 참고
  • 2021년 7월: IOI 2021
  • 2021년 8월: APIO 2021
  • 2021년 9월: Minimum $s - t$ cut of a planar undirected graph in $O(n \log^2 n)$ time
    • 상태: 포스팅하지 않음. 202109.pdf 참고
  • 2021년 10월: Constructing a Distance Sensitivity Oracle in $O(n^{2.5794}M)$ Time
  • 2021년 11월: 2021 ICPC Seoul Regional
  • 2021년 12월: Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
    • 상태: 포스팅하지 않음. 202112.pdf 참고
  • 2022년 1월: Efficient Primal-Dual Algorithms for MapReduce
  • 2022년 2월: Push Relabel Algorithm (1)
  • 2022년 3월: Introduction to Width Independent MWU
    • 상태: 포스팅하지 않음. 202203.pdf 참고
  • 2022년 4월: Push Relabel Algorithm (2)
  • 2022년 5월: Densest Subgraph: Supermodularity, Iterative Peeling, Flow
    • 상태: 포스팅하지 않음. 202205.pdf 참고
  • 2022년 6월: Congestion Balancing
  • 2022년 7월: Treewidth를 사용한 PS 문제 해결
  • 2022년 8월: Conditional Hardness for Sensitivity Problems
  • 2022년 9월: IOI 2022
  • 2022년 10월: Inapproximability in computational hardness
  • 2022년 11월: 2022 ICPC Seoul Regional
  • 2022년 12월: Segment Tree Beats와 Kinetic Segment Tree
  • 2023년 1월: Introduction to APSP Conjecture and BMM Conjecture
  • 2023년 2월: Suffix Automaton
  • 2023년 3월: 구간 최장 증가 부분 수열 쿼리 (Part 1)
  • 2023년 4월: 구간 최장 증가 부분 수열 쿼리 (Part 2)
  • 2023년 5월: Advanced Graph Algorithms and Optimization: Convexity and Second Derivatives, Gradient Descent and Acceleration
    • 상태: 포스팅하지 않음. 202305.pdf 참고
  • 2023년 6월: The Cut-Matching Game: Expanders via Max Flow
  • 2023년 7월: Separating Hyperplanes, Lagrange Multipliers, KKT Conditions, and Convex Duality
  • 2023년 8월: Introduction to Distributed Graph Algorithms

201712.pdf
2.15MB
201802.pdf
2.40MB
201809.pdf
2.67MB
202001.pdf
0.69MB
202004.pdf
2.04MB
202006.pdf
3.19MB
202012.pdf
3.11MB
202101.pdf
2.51MB
202102.pdf
2.51MB
202103.pdf
0.62MB
202106.pdf
0.96MB
202109.pdf
0.29MB
202112.pdf
0.32MB
202203.pdf
0.37MB
202205.pdf
0.38MB
202305.pdf
0.31MB

'공부 > 기타' 카테고리의 다른 글

나의 VS Code 개발 환경 설정  (0) 2022.11.01
공유하기 링크
댓글
공지사항
최근에 올라온 글
Total
Today
Yesterday