BOJ 24313 - 알고리즘 수업 - 점근적 표기 1

문제 링크

문제#

오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.

이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.

함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 $O(n)$ 정의를 만족하는지 알아보자.

입력#

첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 <= |ai| <= 100)

다음 줄에 양의 정수 c가 주어진다. (1 <= c <= 100)

다음 줄에 양의 정수 n0가 주어진다. (1 <= n0 <= 100)

출력#

f(n), c, n0가 $O(n)$ 정의를 만족하면 1, 아니면 0을 출력한다.

풀이#

점근적 표기 정의를 그대로 검사하는 문제다. 결국 f(n) <= c * g(n)가 어떤 n0 이후부터 항상 성립하는지만 보면 되므로, 입력으로 주어진 상수들을 식에 대입해 조건을 확인하면 된다.

코드는 a1, a0, c, n0로 이루어진 부등식을 직접 계산해 판정한다. 알고리즘 문제처럼 보여도 실제로는 정의를 정확히 읽고 경계 조건을 빠뜨리지 않는 것이 더 중요하다.

코드#

#include <iostream>
using namespace std;
 
void solve() {
 
	int a1, a0, c, n0;
	cin >> a1 >> a0 >> c >> n0;
 
	if (a1 <= c && (a1 * n0 + a0) <= (c * n0))
		cout << 1 << '\n';
	else	
		cout << 0 << '\n';
}
 
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	solve();
 
    return 0;
}

복잡도#

• 시간 복잡도: 주어진 식을 조건식으로 한 번 판정하므로 $O(1)$이다.
• 공간 복잡도: 추가 자료구조를 사용하지 않으므로 $O(1)$이다.

마무리#

점근 표기 정의를 식 하나로 압축해 확인하는 문제다. 기울기 조건과 n0에서의 값 조건을 함께 만족해야 이후 구간에서도 정의가 성립한다.