구사과

그냥 아카이빙 목적으로 짧게 씁니다. 현대모비스 본선 대회 본인은 2021년 대회에서 8등인지 9등인지 했고, 2022년 대회에서 예선 탈락을 해서, 2023년 대회 참가가 가능했다. 1번을 열었는데 딱 봐도 따져야 할게 많아 보여서 힘들어 보였다. 따져야 할 걸 안 따지는 풀이를 짜니 10.2/15점이 나왔다. 일단 뒤로 넘어간 다음에, 뒤쪽 문제에서 주는 점수 기댓값이 4.8 미만일 때 돌아오기로 했다. 2번 뭔가 잘 안 읽혀서 뇌절하다가 대충 간선 하나 빼고 dag 경로 없는지 체크? 로 환원했다. 도미네이터 트리로 "풀 수는 있다" 는 것을 알았다. 더 생각해서 간단하게 만들 수도 있겠지만, 그냥 짤만해 보여서 도미네이터 트리를 짜기로 했다. 일반 그래프의 도미네이터 트리는 굉장히 테크니컬하지만,..

많은 일반적인 알고리즘은 하나의 프로세서에서 작동함을 가정하지만, 현실의 계산에서는 컴퓨팅 기계가 하나의 프로세서가 아닌 여러 프로세서를 사용할 수도 있다. Parallel Algorithm의 경우는 효율성을 위해서 여러 개의 프로세서를 두고 동시에 중앙적으로 컨트롤하지만, 가끔은 여러 프로세서를 두는 것이 단순 효율성 때문이 아니라 실제적인 시공간적 제약에 의해서일 수도 있다. 예를 들어, 세계 각지에서 정보를 모으는 컴퓨터가 있고, 이 정보들을 한데 모아서 특정한 계산을 하고 싶은데, 정보들이 하나로 모으기에는 너무 크거나, 아니면 장거리 네트워크를 사용하는 것이 아주 비효율적인 상황들이 있을 것이다. Distributed Algorithm이란 어떠한 알고리즘이 하나의 프로세서가 아니라 여러 분할된 ..

(2023/05/19 최근 과제들을 추가했습니다.) (2020/06/13 6월 과제가 완성되어서 공개했습니다.) (2020/04/18 초판 작성.) 이미 아시는 분들도 계시겠지만, 2017년 가을 이후 포스팅되는 대부분의 글은 삼성전자 SW멤버십의 지원을 받아 작성되고 있습니다. 매달 컴퓨터 과학에 관한 글을 주기적으로 SW멤버십에 제공하고, 이에 따른 지원금을 받는 식입니다. 비정기적으로 관리하던 블로그에 매달 주기적으로 글이 올라올 수 있게 된 것은 SW멤버십의 지원 덕분이 큽니다. 감사합니다. SW멤버십에 제공하는 대다수의 글은 제 블로그에 같이 올립니다. 일반적으로 제출 기한이 있는 SW멤버십에 글을 먼저 제출한 후, 데드라인 안에 손보지 못한 부분이 있으면 이 부분을 보강해서 블로그에 올리는 식..