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

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

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

---

문제 정의

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

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        sum <- sum + A[i]; # 코드1
    return sum;
}

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

def MenOfPassion(A, n):
    sum = 0
    for i in range(n):
        sum += A[i]
    return sum

입력

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

출력

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

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

---

개인적인 해석

<알고리즘 수업 - 알고리즘의 수행 시간 2> 문제는 반복문이 추가된 알고리즘으로 반복되는 형태와 조건에 따라 순열을 만들어 보면 문제를 해석하는데 도움이 된다.

---

개인적인 풀이

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

n = 7
i = [0,1,2,3,4,5,6]

0 1 2 3 4 5 6 = 7

n = 6
i = [0,1,2,3,4,5]

0 1 2 3 4 5 = 6

n = 5
i = [0,1,2,3,4]

0 1 2 3 4 = 5

n = 4
i = [0,1,2,3]

0 1 2 3 = 4

n = 3
i = [0,1,2]

0 1 2 = 3

n = 2
i = [0,1]

0 1 = 2

n = 1
i = [0]

0 = 1

따라서 해당 알고리즘을 유추해 보면,

MenOfPassion 알고리즘은 배열 A와 입력값 n이 주어졌을 때 배열 A의 값들을 순차적으로 더하는 코드이다.

여기서는 알고리즘에 반복문이 하나 포함되어있기 때문에 알고리즘의 소요 시간은 반복문에 따라 결정될 것이다.

 

이러한 조건에서 입력값 n 이 증가함에 따라 수행 횟수 N을 도출하면 아래와 같다.

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

입력값 n이 증가함에 따라 시행횟수 N는 비례적으로 증가하게 되므로, 제출 형식에 맞게 코드를 작성하면 아래와 같다.

import sys

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

print(n)
print(1)

---