시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 171 | 30 | 20 | 16.949% |
지금껏 문제를 풀면서 시간 초과 메시지를 본 적이 있을 것이다.
시간 초과의 이유엔 여러 가지가 있지만, 주로 제출한 코드의 시간복잡도가 문제에서 요구하는 최대 한도의 시간복잡도를 상회했을 때 발생한다.
이번 문제를 풀면서 시간복잡도에 대한 이해도를 높이고 시간 초과 메시지를 덜 받도록 해보자.
어떤 소스 코드가 주어지면 이 소스 코드의 시간복잡도를 계산하면 된다.
물론 그냥 계산하기엔 너무 어려우므로, 다음과 같은 간소화된 방식으로 계산해보도록 하자.
프로그램은 단 네 개의 명령어만을 가진다고 가정한다. 목록은 아래와 같다.
프로그램 분석은 아래의 규칙에 따라 시행한다.
시간복잡도는 basic 구문의 실행 횟수를 함수로 나타낸 뒤 빅오 표기법을 사용하여 분석한다.
빅오 표기법의 정의는 다음과 같다.
어떤 임의의 양의 상수 c와 d를 잘 골라, 1 이상인 모든 x에 대하여 c*g(x) ≤ f(x) ≤ d*g(x)를 만족하게 할 수 있다면 f(x)의 빅오 표기는 O(g)이다.
좀 더 쉽게 설명하면, 모든 상수부는 떼어내버릴 수 있다는 의미이다.
예를 들면 4x 3의 빅오 표기는 x3가 된다.
또한, 어떤 항보다 낮은 차수를 가지는 항들은 통째로 제거하는 것이 가능하다.
예를 들어, x 3 + x2의 빅오 표기는 x3이 되며, x2 + 7의 빅오 표기는 x2가 된다.
하지만 여러 서로 다른 변수가 섞여있다면 다른 항보다 작다고 확신할 수 없는 항들은 모두 표기해야 한다.
예를 들어, x 2y + y2x + xy + x2 의 빅오 표기는 x2y + y2x가 되며, x2 + 17xy + y2 의 빅오 표기는 x2 + y2이 된다.
첫 줄에 테스트 케이스의 수 K가 주어진다.
각 테스트 케이스는 빈 줄로 구분한다.
프로그램은 문제에서 설명한 네 가지의 명령어로만 구성되어 있으며, endprogram은 항상 가장 바깥의 loop문보다 더 아래에 단 하나 존재한다.
loop와 전달인자 x 사이에는 단 한개의 공백이 있으며, 이 경우를 제외하고는 프로그램 내에 어떤 공백이나 이상한 문자가 주어지는 경우는 없다.
loop문의 최대 중첩 횟수는 50회이다.
각 테스트 케이스마다 Data Set K: 를 출력한 뒤, 입력으로 주어진 프로그램의 시간복잡도를 출력한다.
각 항은 x의 차수가 높은 것부터, x의 차수가 같다면 y의 차수가 높은 것부터 차례대로 출력한다.
각 항을 출력할 땐 최대한 축약해야 한다. 예를 들어, x^1y^1을 출력하는 대신에 xy를 출력해야 하며, x^1y^0을 출력하는 대신에 x를 출력해야 한다.
그 외의 출력 형식에 대한 내용은 예제 출력을 보면 된다.
각 테스트 케이스의 사이엔 빈 줄을 하나 출력한다.
3 loop x endloop endprogram basic basic endprogram loop y basic loop y basic basic endloop endloop loop x loop y basic endloop loop x basic endloop endloop endprogram
Data Set 1: 0 Data Set 2: 1 Data Set 3: x^2 + y^2
University > The USC Programming Contest > Fall 2007: Programming Contest Programming Contest D번