[파이썬/Python] 백준 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1

[파이썬/Python] 백준 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1

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

---

문제

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

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

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

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

해설

수행 시간에 대한 배경 지식이 없다면 문제를 처음 첩하면 아리송하다.

코드의 수행 횟수와 알고리즘의 수행 시간을 출력해야하는데, 무엇인지 잘 모르기 때문이다.

 

코드의 수행 횟수는 말 그대로 해당 코드가 몇 번 수행 됐는지 횟수를 나타낸다.

for _ in range(5):
	print("TEST") # CODE 1

위 코드에서 CODE 1 의 수행 횟수는 5회이다.

 

알고리즘의 수행 시간은 알고리즘의 성능 지표로 사용된다.

어떤 작업 A 를 수행해야 되는 코드를 작성한다고 할 때, 그 작업을 수행하는 코드를 작성하는 방법은 여러가지가 될 것이고, 우리는 이를 해결하는 여러가지 방법들을 알고리즘이라고 한다.

 

for _ in range(n):
	print(n) # CODE 2

위 코드는 0부터 n-1 까지의 정수를 출력하는 코드이다.

위 알고리즘의 수행 시간은 얼마일까?

바로 n 이다. n 의 크기에 비례하여 수행되기 때문이다.

 

for i in range(n):
    for j in range(n):
        print(list[i][j]) # CODE 3

위 코드는 n * n 크기의 2차원 리스트를 출력한다.

위 알고리즘의 수행 시간은 얼마일까?

바로 n^2 이다. n*n 번 수행하기 때문이다.

 

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

그렇다면 MenOfPassion 메소드의 코드 1 수행 횟수와 알고리즘 수행시간을 구해보자.

n 에 어떤 값이 입력되든, 내부 연산을 수행한 후 반환할 때 return A[i] 는 한번 수행 된다.

따라서 수행횟수는 1이다.

n에 어떤 값이 입력 되든 한번만 수행하면 되는 코드이므로, n에 비례하는 알고리즘이 아니다.

따라서 수행시간 또한 1이다.

코드

print("""1
0""")

풀이

1. 수행횟수와 수행 시간을 출력조건에 맞추어 출력한다.

print("""1
0""")