[BOJ] 백준 24265 알고리즘 수업 - 알고리즘의 수행 시간 4 (Swift)

문제

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

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

풀이

문제의 알고리즘은 n에 영향을 받아, 중첩된 for문이 약 $n^2$번 실행됩니다.
빅오 표기법으로 $O(n^2)$ 입니다.

수행횟수는 어떻게 될까요?

7을 예시로 들어보겠습니다.

첫 번째 for문에서는 1, 2, 3, 4, 5, 6 까지 실행되겠네요.

두 번째 for문에서는
첫 번째 for문이 1일 때, 6번 실행 (2, 3, 4, 5, 6, 7)
첫 번째 for문이 2일 때, 5번 실행 (3, 4, 5, 6, 7)
첫 번째 for문이 3일 때, 4번 실행 (4, 5, 6, 7)
...
첫 번째 for문이 6일 때, 1번 실행 (7)

21 = 6 + 5 + 4 + 3 + 2 + 1 번 실행이 됩니다.

$\sum_{i=1}^{n-1} t_1 = \frac{(n - 1) \times n}{2}$ 입니다.

따라서 수행 횟수는 $\frac{(n - 1) \times n}{2}$번,
최고차항의 차수는 2 입니다. ($\frac{(n - 1) \times n}{2} = \frac{n^2 - n}{2}$ 이므로)

소스코드

후기

기존 1, 2, 3번 문제와 다르게 의사코드를 조금 더 읽어야 했던 문제입니다.
수행 횟수가 어떻게 될지 생각해보면 쉽게 풀 수 있는 문제인 것 같습니다.
또한, 시간복잡도를 계산하는 방법에 대해 이해하고 있어야 합니다.