Constructive 문제를 어떻게 풀 것인가
Constructive 문제를 어떻게 풀 것인가 들어가며 알고리즘 대회에서 Constructive Algorithm(구성적 알고리즘)은, 말뜻 그대로 답을 증명할 수 있는 실제 예시를 구성하는 것이다. 이 용어는 수학의 Constructive Proof(구성적 증명, 존재성의 증명 등에서 귀류법이나 귀납법을 쓰지 않고 직접 조건을 만족하는 예시를 만들어 증명하는 방법)에서 왔다고 할 수 있다. Constructive 문제에서 구성해야 하는 대상은 대개 Sequence나 Graph이다. 무에서 유를 창조해내야 하는 문제의 특성상, 많은 배경 지식을 필요로 하기도 하며, 특정 문제에서의 테크닉을 일반화하기 어렵다는 Ad-hoc의 특징도 가지고 있다. 그렇다고...