[python/파이썬] 백준 24262 24263 24264 24265 알고리즘 수업 - 알고리즘의 수행 시간

[문제 출처 - 24262]

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

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

[문제 출처 - 24263]

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

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

[문제 출처 - 24264]

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

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

[문제 출처 - 24265]

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

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

 

[문제 풀이]

 

✅ 소스 코드 24242

 

입력에 상관없이 주어진 코드는 한 번만 실행되므로 답은 1, 0이 된다.

print(1)
print(0)

 

✅ 소스 코드 24243

 

입력 n에 따라 수행 횟수가 달라진다. n번 수행되기에 알고리즘 수행 시간은 n에 비례하여 최고차항의 차수는 1이다.

n = int(input())

print(n)
print(1)

 

✅ 소스 코드 24244

 

이중 for문이므로 n의 제곱번 수행된다. 알고리즘 수행 시간은 n^2에 비례하기에 최고차항의 차수는 2가 된다.

n = int(input())

print(n**2)
print(2)

 

✅ 소스 코드 24245

 

❌ 시간초과

주어진 코드대로 작성하여 횟수를 세면 n^2에 비례하는 수행 시간이 걸리게 된다. 따라서 아래의 코드는 시간 초과가 발생한다.

n = int(input())

cnt = 0
for i in range(n):
  for j in range(i+1,n):
    cnt += 1

print(cnt)
print(2)

 

⭕ 맞았습니다!!

 

이중 for문이기에 알고리즘의 수행시간은 n^2에 비례한다. 수행 횟수는 n-1번, n-2번, n-3번... 1번 이렇게 수행되므로 for문을 통해 합을 구해주었다.

n = int(input())

cnt = 0
for i in range(n-1, -1, -1):
  cnt += i

print(cnt)
print(2)