백준 24262번 알고리즘의 수행 시간 1 | [BACKJOON/Python / 24262]

문제링크

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

문제

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

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

MenOfPassion 알고리즘은 다음과 같다.

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

입력

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

출력

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

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

 

 

예제 입력 & 출력

 

 

풀이

해당 문제를 풀기위해서는 시간복잡도개의 개념을 알고 있어야 조금더 쉽게 풀수 있습니다.

시간복잡도에 관한 내용을 찾아보던중 잘 정리해서 알려주는 블로거가 있어서 시간복잡도에 관한 내용을 먼저 배우고 왔습니다.

 

간단하게 얘기하자면 시간 복잡도를 표기하기 위해서 Big-O 표기법이 있는데 Big-O표기법의 종류로는 다섯가지로 나뉩니다. 자세한 설명은 해당내용을 설명한 블로그에 잘 정리되어있으므로 읽어보는걸 추천

• O(1) - 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있음
• O(n) - 입력값에 비례하여 시간도 그만큼 증가하는 알고리즘을 의미함
• O(log n) - Binary Search Tree구조로 경우의 수를 계속 절반으로 줄여나가며 정답을 찾아냄
• O(n2) - 입력값이 증가함에 따라 시간이 n의 제곱수 비율로 증가함
• O(2n) - Big-O표기법 중 가장 느린 시간복잡도 재귀로 구현하는 피보나치 수열이 대표적인 예시

이 Big-O 표기법중 오늘 반드시 알아냐 할 내용은 O(1)입니다.

 

문제의 MenOfPassion  알고리즘을 보면  입력값 n이 주어지는데 n의 값이 아무리 커져도 즉시 출력값을 반환해줍니다. n이 100이어도 100/2 로 i값에 계산결과를 저장하고 index의 배열에서 i값의 위치를 반환한다음 코드가 종료됩니다. 입력값의 숫자와 상관없이 코드가 1번만 실행됩니다.

 

출력내용에 첫째 줄에는 코드1의 수행횟수를 출력한다고 하였으니 수행횟수인 1을 출력해주면 됩니다.

그리고 두번째줄에는 수행횟수를 다항식으로 나타냈을때의 최고차수 0을 출력해주면 됩니다.

 

print(1)
print(0)