[백준-python] 알고리즘의 수행 시간 2,4,6번

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

아직 눈도 제대로 안떠졌는데 아침부터 이 문제보고 이해를 못해서 아침부터 기분이 팍 상해버렸다.

머리엔 물음표만 가득...했고.... 첫째줄엔 시간복잡도를 의미하는거같은데 둘째줄이 이해가 되지 않았다....😖

 

1. 수행횟수=시간복잡도

2. 시간복잡도를 다항식으로 나타내고, 최고차항의 차수 

 

👉🏻 O(1) = 0(상수)

👉🏻 O(n) = 1

👉🏻 O(n^2) = 2

 

이를 의미하는것이였다.....

계수랑 차수랑 헷갈려서 그걸 어떻게 구하라는거야 이러고 있었다.......

 

 

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

이 코드는 for문이 n만큼 순회하는 반복문이므로, O(n)이다.

👉🏻 첫째줄은 n을 출력

👉🏻 둘째줄은 O(n)의 최고차항 1을 출력하면 되는것

 

 

✨ 정답

# 시간복잡도: O(n) 
# 최고차항으로 나타내면 1

print(input()) 
print(1)

 

 

 

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

https://www.acmicpc.net/problem/24265

 

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

외부 for문 i= 1부터~n-1까지

내부 for문 j= i+1부터 n까지

 

👉🏻 이중 for문은 O(n^2) 이므로, 최고차항은 2

 

n=7이라고 했을때,

i=1 , j=2~7  (6번)
i=2, j=3~7  (5번)
... 
i=6, j=7       (1번)

 

👉🏻 실행횟수는 1부터 n-1까지 합산한 값이 된다.

 

✨ 정답

n=int(input())

#1부터 n-1까지 sum
print(sum([i for i in range(1,n)]))
print(2)

 

 

 

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

https://www.acmicpc.net/problem/24267

total=0
n=7

for i in range(1, n-1):
    for j in range(i+1, n):
        for k in range(j+1, n+1):
            print(i, j, k)
            total += 1

print(total)

 

n=7

#i=1 -> 5+4+3+2+1
#i=2 -> 4+3+2+1
#i=3 -> 3+2+1
#i=4 -> 2+1
#i=5 -> 1

n=7일때, 이와 같은 패턴을 가지고있다.

 

 

✨ 정답

n=int(input())

total=0

#i는 1부터 n-2 순회
for i in range(1,n-1): 
    total+=sum([x for x in range(1,i+1)])   


print(total)

이 방법은 역시 시간초과 발생

 

n=int(input())

total=0
temp=0

#i=1 -> 5+4+3+2+1
#i=2 -> 4+3+2+1
#i=3 -> 3+2+1
#i=4 -> 2+1
#i=5 -> 1

for i in range(1,n-1): 
    temp=temp+i #1 3 6 10 15
    total+=temp 
    

print(total) #순회 횟수
print(3) #삼중 for문 O(n^3)