티스토리 뷰

공부

Deep Cuts

구사과 2020. 6. 13. 17:45

(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

201712.pdf
2.15MB
201802.pdf
2.40MB
201809.pdf
2.67MB
202001.pdf
0.69MB
202004.pdf
2.04MB
202006.pdf
3.19MB

'공부' 카테고리의 다른 글

Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms  (2) 2020.07.24
Petrozavodsk Summer 2019. Part 1  (1) 2020.06.16
Deep Cuts  (5) 2020.06.13
Matroid Intersection  (0) 2020.06.07
2020.05.27 problem solving  (0) 2020.05.27
그래프의 간선 색칠 문제  (2) 2020.05.19
댓글
댓글쓰기 폼
공지사항
Total
423,289
Today
85
Yesterday
454