[ MR 05. 백준 - 24313. 알고리즘 수업 - 점근적 표기 1 ]

[ MR 05. 백준 - 24313. 알고리즘 수업 - 점근적 표기 1]

언어 : C++

주말 제외
습관 만들기 위한 1일 1코테 챌린지

습관 만들기를 위해 기록중입니다. 도움이 안되실 수도 있습니다!
저와 같이 습관 만들기 챌린지를 해보시는 건 어떨까요?? ㅎㅎ

문제

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

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

O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}

이 정의는 실제 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을 출력한다.

입출력 예제

내 풀이

bool isBigO = true; // 초기 상태를 true로 설정

    for (int n = n0; n <= 100; ++n) {
        if (a1 * n + a0 > c * n) {
            isBigO = false; // 조건을 만족하지 않는 경우
            break;
        }
    }

    // 결과 출력 (조건을 만족하면 1, 만족하지 않으면 0)
    if (isBigO) {
        cout << 1 << endl;
    } else {
        cout << 0 << endl;
    }

전체코드 보러가시려면 여기를 눌러주세요.

후기

오늘은 쉬어가는 느낌으로 풀어봤습니다...!
코테 언제 익숙해지는 걸까...