[백준 - python] 24262~7번: 알고리즘 수업 - 알고리즘의 수행 시간 1~6

문제 링크

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

24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2

24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3

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

24266번: 알고리즘 수업 - 알고리즘의 수행 시간 5

24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6

문제 풀이

1

print(1)
print(0)

2

n = int(input())
print(n)
print(1)

3

n = int(input())
print(n**2)
print(2)

4

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

5

n = int(input())
print(n**3)
print(3)

6

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

 

*key point: 이 문제들은 시간 복잡도 개념의 기초를 다루고 있다. 단순히 실행횟수를 출력해보고, 이를 일반화해서 n(input값)에 관한 식으로 나타내면서 감을 잡을 수 있다. 중요한 것은 결국 n에 대한 식으로 나타냈을 때 최고차항의 차수가 중요함을 알면 된다. 빅오(Big-O) 표기법에 대해 공부해보면 더욱 좋다.

 

6번 문제의 경우 하나씩 경우의 수를 작성하다 보면 n개의 수 중 순서 상관없이 3개의 수를 뽑는 방법의 수와 동일 함을 알 수 있다.