구사과

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

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

1. Separating Hyperplane Theorem 2차원 평면에 겹치지 않는 두 원이 있을 때, 두 원을 분리하는 직선을 찾을 수 있을까? 다시 말해, 직선의 한 쪽에 첫 번째 원이, 직선의 다른 쪽에 두 번째 원이 존재하게 직선을 그을 수 있을까? 어렵지 않게, 두 원의 공통 접선을 적절히 그어서 나누면 될 것이다. 같은 원리로, 겹치지 않는 두 볼록 다각형이 있을 때 둘을 분리하는 직선 역시 찾을 수 있다. 조금 더 복잡하지만, 3차원 공간에서도 겹치지 않는 두 볼록 다면체를 분리하는 평면이 존재할 것 같다. 즉, 평면의 한 쪽에 볼록 다면체 하나가, 다른 한 쪽에 볼록 다면체 하나가 있는 것이다. 이를 $n$ 차원으로 일반화하면 다음과 같다. 두 개의 Disjoint한 ($A \cap B ..

알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 알고리즘 연구에서 분할 정복이 가지는 중요성은 어마어마하지만, 그래프에 대한 분할 정복에 대해서는 좋은 결과를 얻지 못했다. 오랜 시간 동안 이러한 분할 정복 은 트리, 평면 그래프, 혹은 이와 유사한 그래프에서만 가능한 것으로 알려져 있었다. 하지만, 그래프 알고리즘과 최적화 이론의 결합이 여러 의미 있는 성과들을 내면서, 이러한 분할 정복 기법을 그래프에서도 적용할 수 있는 좋은 프레임워크가 생겼고, 그 결과 중 하나가 Expander Decomposition이다. Expander는 잘 연결된 그래프를 뜻한다. 보통 그래프..

티스토리 렌더링 문제로 수식이 많이 깨진다. 일단 깨진 형태로 올려두지만 쉽게 볼 수 있는 PDF를 첨부한다. PDF를 보는 것을 추천한다. Chapter 4. $\boxdot$ 연산자의 빠른 구현 현재 우리의 알고리즘이 $O(N^5)$ 인 이유는 다음과 같다: $\boxdot$ 연산자가 $O(N^3)$ 에 구현됨 $\boxdot$ 연산자를 $O(N^2)$ 번 호출함 잠시 $\boxdot$ 연산자의 실제 이름을 짚고 넘어가자면, 논문에서는 위 연산자가 unit-Monge matrix-matrix distance multiplication 라는 이름으로 소개되었다. Part 1에서는 괜히 글이 어렵다는 인상을 줄 것 같아서 의도적으로 언급하지 않은 이름이다. 이제부터는 (순열의) unit-Monge 곱 이..

티스토리 렌더링 문제로 수식이 많이 깨진다. 일단 깨진 형태로 올려두지만 쉽게 볼 수 있는 PDF를 첨부한다. PDF를 보는 것을 추천한다. 이번 글에서는 다음과 같은 쿼리를 수행하는 자료 구조에 대해 다룬다: 길이 $N$ 의 수열 $A$ 와 $Q$ 개의 쿼리 $1 \le i \le j \le N$ 가 주어질 때, $A[i], A[i + 1], \ldots, A[j]$ 의 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) 를 계산하라. LIS 문제의 경우 동적 계획법으로 해결할 수 있는 가장 기초적인 문제 중 하나로, 수학적으로 여러 의미를 가지기 때문에 변형된 문제들이 다방면으로 연구되고 있다. 위와 같은 쿼리 문제는 다들 자료 구조 문제를 고민해 보다가 한번쯤 ..

문자열의 부분문자열에 대한 복잡한 문제를 풀 때 Suffix Array와 같은 접미사 구조 는 아주 강력한 도구가 된다. SCPC 2021 3번, 서울 리저널 2022 H 등 여러 중요한 대회에서도 이러한 접미사 구조를 응용한 문제들이 정말 많이 나온다. 한국에서 많은 사람들이 알고 있는 접미사 구조로는 Suffix Array 가 있다. Suffix Array는 모든 문자열의 접미사를 정렬한 순열로, 흔히 부분문자열 탐색 쿼리를 빠르게 처리하거나 두 접미사의 LCP를 구할 때 많이 쓰인다. 문자열 접미사 구조 중 알려진 자료구조는 크게 Suffix Array, Suffix Tree, Suffix Automaton 이 있는데, 한국에서는 Suffix Array만이 알려져 있는 편이고, 그 외 다른 자료구조..

Codeforces에 올린 글을 보관 목적으로 블로그에도 올립니다. Yesterday I participated in a local contest involving a problem about Monge arrays. I could've wrote some d&c optimization, but I got bored of typing it so I copypasted maroonrk's SMAWK implementation to solve it. Today, I somehow got curious about the actual algorithm, so here it goes. 1. Definition I assume that the reader is aware of the concept o..

A 단순 구현 문제. 물어보는게 복잡해서 약간의 전처리를 했다. 모든 자연수의 진약수의 합을 전처리하면 짧게 할 수 있었다. B 물어보는 게 모든 가방의 평균 중 몇 번째의 어쩌구 같은 아주 복잡한 무언가였다. 특히 가방의 개수가 많으면 사실상 관리가 불가능한 수치이다. 그런데 가방의 개수가 많으면 첫 번째 / 두 번째로 큰 가방만 남겨두고 나머지는 그냥 다 합쳐주면 된다. 그러니까 최적해에서 가방이 많지 않을 거라고 짐작할 수 있고 그 원리에 입각해서 생각하면 된다. 그런 식이었다. 더 정확하게는 기억이 나지 않는다 (...) $(K+1)/2$ 를 올림하고 내림하는 걸 헷갈려서 한번 틀렸다. C 애드혹 문제도 기출 패턴이 있고 웰노운이 있다. 이 문제 와 비슷하게 해결할 수 있다. D 재밌게 풀었다. ..

(첨부 자료는 발표에 사용한 슬라이드이다.) 이론전산학에서 논의되는 가장 주된 문제 중 하나는 어떠한 문제가 "쉽다" (algorithm) 내지는 "어렵다" (hardness) 는 논의이다. 쉽다는 것을 증명하려면, 효율적인 알고리즘을 찾아 빠르게 해결하면 된다 (constructive proof). 대단히 명료하고, 알고리즘 대회를 통해서 많이 연습되는 방법이기도 하다. 어렵다는 것을 증명하는 것은 쉽다를 증명하는 것만큼 명료하지 않다. $P=NP$ 가설이 오랜 난제로 남아있는 것도 "어려움을 증명하는" 쉬운 방법을 찾지 못해서라고 볼 수 있다. 통상적으로는, 가장 대표성있는 문제를 잡아서 "어떠한 문제는 풀 수 없다" 라는 가설을 만들고, 이 문제가 풀렸을 때 다른 문제를 풀 수 있는 알고리즘을 고안..