구사과

2023년 정보화진흥원 역량강화 교육 내용을 바탕으로 작성합니다. AC로 검증 못한 풀이들이 있어 주의를 요합니다. 2차 교육 B: L과 R의 중간 지점을 기준으로, 왼쪽에 있다면 R+1에 갈 필요가 없고, 오른쪽에 있다면 L-1에 갈 필요가 없다. 따라서, L과 R 중 하나를 고려할 필요가 없다. L을 고려하지 않고 문제를 해결하고, 반대의 경우는 대칭적으로 해결한다. R이 존재하지 않을 때 한 사람이 최대로 이동하는 거리 및 그 때의 총 이동 거리를 전처리해 두면, 사람이 있는 곳과 R이 주어졌을 때의 cost를 O(1)에 구할 수 있다. 이 때, 이 cost는 monge function이고, 2023 선발고사에 나왔던 “팀 만들기”의 60점 풀이를 그대로 사용하면 해결할 수 있다. D: $S < X..

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

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