[Python] 백준 24262번 알고리즘 수업-알고리즘의 수행 시간 1

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다.

아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.

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

 

https://www.acmicpc.net/problem/24262

24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1

입력

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

출력

첫째 줄에 코드1 의 수행 횟수를 출력한다.
둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 

단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

예제

__input__
1
__output__
1
0

문제 풀이

print(1, 0, sep='\n')

주어진 MenOfPassion 함수는 A[i]를 return하는 함수로, 입력값과는 무관하게 단 1회 함수를 실행합니다.

하여 첫번째 줄에는 1을 출력하고, 상수항이기에 두번째 줄에는 0을 출력합니다.

 

시간 복잡도에 관한 개념을 알고 있어야 풀이가 가능하며,

하기 포스팅을 통해 개념을 배워 참고차 공유 드립니다.

 

알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기 by Chulgil.Lee

 

---

파이썬을 독학하시는 분들에게 도움이 되길 바라며,

혹 더 좋은 방법이 있거나 오류가 있다면 편하게 말씀 부탁드립니다.