백준 파이썬 264262번 알고리즘 수업 - 알고리즘의 수행 시간 1 (Today I Learn 2024.03.15)

20240315 백준 파이썬 공부
264262번 알고리즘 수업 - 알고리즘의 수행 시간 1

1. 문제
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 
아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.
>>> MenOfPassion 알고리즘코드
MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

2. 입력
첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

3. 출력
첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 
단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

>>>코드

n = int(input())
print(1)
print(0)

>>>해설
처음 보고 당황했지만 이 문제는 코딩 문제라기보다는 "시간 복잡도"라는 코딩 개념에 대한 주관식 문제라고 생각하는 것이 올바르다.

시간 복잡도.
코드를 짜게 되면 코드가 실행되는데 걸리는 시간을 의미하는데
시간 복잡도는 코드에 따라 굉장히 다양한 경우가 나타난다.
- 입력 숫자에 관계없이 항상 걸리는 시간이 일정한 경우
- 입력 숫자의 비례하여 시간이 느는 경우
- 입력 숫자의 거듭제곱에 비례하여 시간이 급격하게 느는 경우

그리고 이것은 코드의 실행 횟수와 관련이 있으며, 
따라서 이 문제는 주어진 코드에 n을 입력했을때 n과 관련하여 시행횟수가 어떻게 변하는지 다항식을 만들고, 입력한 숫자를 해당 다항식에 대입했을 때의 결과값과 다항식의 최고차향의 계수를 물어보는 문제인 것이다.

그러나 해당 코드를 보았을 때, n에 어떠한 숫자를 넣던간에 시행횟수는 1로 고정이며, 따라서 시행횟수 다항식도 O = 1로 최고차항의 계수가 0이다.

따라서 코드가 위와 같이 나온다.

>>>시간 복잡도 관련 자료 사이트
https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

>>> 문제 링크
https://www.acmicpc.net/problem/24262