[백준] 알고리즘 수업 - 알고리즘의 수행 시간 1

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

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

---

문제 정의

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

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

해당 코드를 python3 형태로 바꾸면 아래와 같이 표현할 수 있다.

def MenOfPassion(A, n):
    i = n // 2 
    return A[i]

입력

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

출력

첫째 줄에 코드 1의 수행 횟수를 출력한다.

둘째 줄에 알고리즘의 수행 시간이 상수 시간이 소요되면 0, n에 비례하면 1, n2에 비례하면 2, n3에 비례하면 3, n3보다 큰 시간에 비례하면 4를 출력한다.

---

개인적인 해석

<알고리즘 수업 -  알고리즘의 수행 시간문제 1>는 처음에 보면 단순히 함수를 만들고 해당 함수의 반복 횟수와 수행 시간을 측정하여 계산을 하여 정답을 도출하는 것처럼 보인다.

하지만 문제의 핵심은 알고리즘의 시간복잡도에 대한 기초적인 이해를 요구하는 문제로 해석할 수 있다.

---

개인적인 풀이

해당 코드 블럭을 n≤7인 조건에서 n과 i를 표시해 보면 아래와 같이 나열할 수 있다.

n = 7
i = 7//2, A[3]

n = 6
i = 6//2, A[3]

n = 5
i = 5//2, A[2]

n = 4
i = 4//2, A[2]

n = 3
i = 3//2, A[1]

n = 2
i = 2//2, A[1]

n = 1
i = 1//2, A[0]

따라서 해당 알고리즘의 의미를 유추해 보면,

MenOfPassion의 알고리즘은 배열 A와 입력값 n이 주어졌을 때 A 배열에서 i index 값을 출력하는 코드이다.

여기서 i는 입력값 n을 2로 나눈 값으로 해당 계산은 단순히 상수 시간이 소요될 것으로 보인다.

 

따라서 n이 증가함에 따라서 수행 횟수 N은 아래와 같다.

n = 1, N = 1
n = 2, N = 1
n = 3, N = 1
n = 4, N = 1
n = 5, N = 1
n = 6, N = 1
n = 7, N = 1

이것을 제출 형식에 맞춰 코드를 작성하면 아래와 같은 코드를 작성할 수 있을 것이다.

import sys

input = sys.stdin.readline().rstrip()
n = int(input)

print(1)
print(0)

---