BOJ 24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4

핵심 포인트

• 시간 복잡도

제출코드

n = int(input())
print((n - 1) * n // 2)
print(2)

해설

이 문제를 풀 때 중요한 것은 주어진 문제 내의 코드를 분석하는 것 입니다. 주어진 MenOfPassion 함수는 2개의 변수 (A, n)를 입력으로 받습니다. 내부 알고리즘에서 중요한 부분은 반복문입니다. 보시면 2개의 반복문으로 구성되어 있음을 알 수 있습니다. i가 1 ~ n - 1까지 반복한다고 가정했을 때 i = 1이면 j = 2 ~ n까지 반복하므로 총 (n - 2) + 1 = n - 1 번 반복합니다. i = 2 라면 j = 3 ~ n까지 반복하므로 총 (n - 3) + 1 = n - 2 번 반복합니다. 이 과정을 계속 수행하면 $(n - 1) + (n - 2) + \cdots + 2 + 1 =  \frac{(n - 1)n}{2}$번 만큼 반복되는 것을 알 수 있습니다. 따라서, 시간복잡도는 $O(n^{2})$이 되므로 최대 차수는 2을 출력하면 됩니다. 

참고자료 및 그림출처

백준 코딩 문제