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

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

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

---

문제 정의

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

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

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

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

입력

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

출력

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

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

---

개인적인 해석

<알고리즘 수업 - 알고리즘의 수행 시간 3> 문제는 반복문이 두번 포함되어있는 문제이다. 따라서 해당 알고리즘의 규칙을 찾는데 조금 시간이 걸릴 수 있을 것이다.

---

개인적인 풀이

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

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

00 01 02 03 04 05 06 = 7
10 11 12 13 14 15 16 = 7
20 21 22 23 24 25 26 = 7
30 31 32 33 34 35 36 = 7
40 41 42 43 44 45 46 = 7
50 51 52 53 54 55 56 = 7
60 61 62 63 64 65 66 = 7

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

00 01 02 03 04 05 = 6
10 11 12 13 14 15 = 6
20 21 22 23 24 25 = 6
30 31 32 33 34 35 = 6
40 41 42 43 44 45 = 6
50 51 52 53 54 55 = 6

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

00 01 02 03 04 = 5
10 11 12 13 14 = 5
20 21 22 23 24 = 5
30 31 32 33 34 = 5
40 41 42 43 44 = 5

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

00 01 02 03 = 4
10 11 12 13 = 4
20 21 22 23 = 4
30 31 32 33 = 4

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

00 01 02 = 3
10 11 12 = 3
20 21 22 = 3

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

00 01 = 2
10 11 = 2

n = 1
i = [0]
j = [0]

00 = 1

앞선 알고리즘보다 훨씬 길고 복잡하게 보인다.

MenOfPassion 알고리즘은 배열 A와 입력값 n이 주어졌을 때 배열의 모든 조합을 곱하는 코드이다.

천천히 규칙을 찾아보면 n, i, j의 조건에 따른 규칙을 찾을 수 있으며,

 

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

n = 1, N = 1    1               = 1
n = 2, N = 4    2 2             = 2 * 2
n = 3, N = 9    3 3 3           = 3 * 3
n = 4, N = 16   4 4 4 4         = 4 * 4
n = 5, N = 25   5 5 5 5 5       = 5 * 5
n = 6, N = 36   6 6 6 6 6 6     = 6 * 6
n = 7, N = 49   7 7 7 7 7 7 7   = 7 * 7

 입력값 n이 증가함에 따라 시행 횟수 N은 (n)^2에 비례하여 증가하게 되므로, 제출 형식에 맞게 코드를 작성하면 아래와 같이 표현할 수 있을 것이다.

import sys

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

print(n*n)
print(2)

---