[Algorithm] Interactive Problem (인터랙티브 문제, 대화형 문제)

 알고리즘 문제를 풀던 중 문제에 해당 문제는 Interactive Problem라는 설명이 있었고, 이 문제 유형에서 어려움을 겪어 Interactive Problem이 무엇인지 알아봤다.

 

 Interactive Problem는 실행 과정에서 작성자의 프로그램(코드)이 주어진 문제(흔히 judge라고 한다)와 상호 작용해야 하는 유형이다. 단순히 표준 입력을 읽고 표준 출력을 하는 대신, 작성자의 코드는 judge와 오가며 소통을 하게 된다.

 예를 들면 아래와 같다.

 judge만 알고 있는 숫자 x가 있고, 문제를 푸는 사람은 못한다고 가정해보자. 그리고 judge는 x가 1에서 100 사이의 int(정수)라는 것만 알려준다.

 각 단계에서 작성자는 이를 추측해 y라는 숫자를 제시하면, judge는 이 숫자가 x보다 크거나 작은지 혹은 같은지를 알려준다. 작성자는 judge의 답변을 바탕으로 x를 계속 추적해 나간다.

 이런 Interactive Problem 문제는 일반적인 문제보다 까다로울 수 있다.