中庸 中庸

어떤 문제를 해결하는 데 걸리는 소요시간의 lower bound 를 찾는 방법 중의 하나인 방해꾼 논법에 대해 알아보겠습니다. 방해꾼 논법 (Adversary Argument) 1. 해결하는 사람 (Solver) 와 상대방 (Adversary) 간의 일종의 스무고개 같은 게임입니다. 2. Adversary 는 input 을 가지고 있고, solver 는 input 이 무엇인지 확인할 수 없습니다. 3. solver는 adversary 에게 질문을 할 수 있습니다. 이 때, 질문은 형식에 맞춰 질문해야 합니다. ( 알고리즘의 계산 모델 제약 조건이 질문의 형식 제약이라고 생각할 수 있습니다. ) 4. adversary는 solver 의 질문에 대해 답변을 해주어야 합니다. 이 때, solver 가 최대한 ..