[백준 24313] 점근적 표기 1 문제 풀이 & 해설 - 파이썬

백준 24313 문제에 대해 풀어보겠습니다.

 

이 문제는 알고리즘 수행 시간에 관한 문제로 "점근적 표기 (asymptotic notation)"에 관해 알고 있는지를 묻고 있습니다.

 

Background: 점근적 표기

 

점근적 표기에 대해 간략히 설명을 하자면, Big-O를 계산할 때 입력값의 크기에 따라 함수가 얼마나 빨리 커지는지 알아볼 때 중요하지 않은 항과 상수 계수를 제거하면서 이해를 방해하는 불필요한 부분을 없앤 표기법이라고 볼 수 있습니다.

 

즉, 간략한 예로 

$ y = 0.0006n^3 - 1000 $라고 했을 때, $O(y)=n^3$ 가 되는 반면에, 

$ x = 1000n^2 + 1000 $의 Big O는 $O(x)=n^2$ 가 되기 마련입니다. 

 

따라서 y의 수행시간이 x보다 더 크다고 할 수 있습니다. 

 

백준 문제

 

Big-O에 대해 익숙하지 않으시다면 처음에는 헷갈릴 수 있습니다. 

도대체 문제의 요지가 무엇인지 말이죠.

 

위 background에서 설명한 내용을 보고, 문제를 풀어보면 조금 낫지 않을까 생각합니다.

 

위 문제에서 사용한 수식은 다음과 같습니다.

• $ f(n) = a_1 n + a_0 $
• $ g(n) = n $

$n$을 변수라고 했을 때, 두 식 모두 1차 식 (선형)임을 알 수 있습니다.

이것을 고려했을 때 풀이는 더욱 더 간단해집니다.

 

같은 1차 식이라면, 다음 두가지만 집중하면 됩니다.

1. $a_1 n$ 의 크기와 $c g(n)$의 크기 확인
2. $n_0$ 값에 따른 전체 출력 값 비교: $f(n)$ vs $c * g(n)$ 

 

정답 코드는 다음과 같이 작성해보았습니다.

더 쉽게 작성 가능하나, 논리적 흐름을 살필 수 있게 작성해보았습니다.

# define g function
def g(n: int) -> int:
    return n


# define f function
def f(a0: int, a1: int, n: int) -> int:
    return (a1 * n) + a0


if __name__ == '__main__':
    # input
    a1, a0 = map(int, input().split())
    c = int(input())
    n0 = int(input())

    # think about asymptotic notations
    # constant doesn't matter
    if c >= a1:
    	# compare two functions' initial outcomes
        if c * g(n0) >= f(a0, a1, n0):
            print(1)
        else:
            print(0)
    else:
        print(0)

 

계수를 비교하고, 초깃값을 비교하면 풀리는 문제였습니다.

 

조금 더 짧은 버전으로는 다음과 같이 작성할 수 있습니다.

if __name__ == '__main__':

    a1, a0 = map(int, input().split())
    c = int(input())
    n0 = int(input())

    if ((a1*n0 + a0) <= (c * n0)) and (a1 <= c):
        print(1)
    else:
        print(0)