단계별: 시간 복잡도 (24262, 24263, 24264, 24265, 24266, 24267, 24313) (python3)

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

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

위 코드 1을 보면 수행횟수는 1임. n의 입력값과 상관없이 항상 1이기 때문에 최고차항의 차수는 항상 0.

print(1)
print(0)

 

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

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

n의 입력값만큼 코드 1이 수행됨

import sys

n = int(sys.stdin.readline().rstrip())
print(n)
print(1)

 

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

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

2중 for문이기 때문에 코드 1은 $n^2$만큼 수행됨

import sys

n = int(sys.stdin.readline().rstrip())
print(n**2)
print(2)

 

알고리즘 수업 - 알고리즘의 수행 시간 4 - 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;
}

코드를 보면 다음과 같이 수행됨

i=1, j=2,3,4,5,6,7
i=2, j=3,4,5,6,7
i=3, j=4,5,6,7
i=4, j=5,6,7
i=5, j=6,7
i=6, j=7

전 문제와 동일하게 2중 for문이기 때문에 최고차항의 차수도 2임

import sys

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

print(n*(n-1)//2)
# 처음에 print((n-1)*(n-1)//3)으로 했다가 틀렸음
print(2)

 

알고리즘 수업 - 알고리즘의 수행 시간 5 - 24266

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

3중 for문, 코드 1은 $n^3$만큼 수행됨

import sys

n = int(sys.stdin.readline().rstrip())
print(n**3)
print(3)

 

알고리즘 수업 - 알고리즘의 수행 시간 6 - 24267

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

24265 문제와 비슷한 형식임

import sys

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

print(n*(n-1)*(n-2)//6)
# 처음에 print(n*(n-2)*(n-4)//3)으로 제출했다가 틀림
print(3)

 

알고리즘 수업 - 점근적 표기 1 - 24313

처음 코드를 제출할 때 if문에 다음과 같이 입력했더니 틀려서 다시 한번 생각해봄

(a1*n0)+a2 <= n0*c

문제에 나와있는 빅오의 정의는 다음과 같음

O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}

입력 범위는 다음과 같다

첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 ≤ |ai| ≤ 100)

다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)

다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)

$a_i$는 음수도 입력이 가능함

a0, a1이 각각 양수, 음수일 때로 구분하고 c보다 작을 때, 같을 때, 클 때 3가지 경우로 나눠서 다음과 같이 생각해봄

a0이 음수
7*10-7 < 10*8
8*10-7 < 10*8
9*10-7 > 10*8

7*10-7 < 10*8
7*10-8 < 10*8
7*10-9 < 10*8

a1이 음수
-7*10+7 < 10*8
-8*10+7 < 10*8
-9*10+7 < 10*8

-7*10+7 < 10*8
-7*10+8 < 10*8
-7*10+9 < 10*8

둘 다 양수
7*10+7 < 10*8
8*10+7 > 10*8
9*10+7 > 10*8

7*10+7 < 10*8
7*10+8 > 10*8
7*10+9 > 10*8

둘 다 음수
-7*10-7 < 10*8
-8*10-7 < 10*8
-9*10-7 < 10*8

-7*10-7 < 10*8
-7*10-8 < 10*8
-7*10-9 < 10*8

위 예시처럼 a1이 c보다 크면 조건이 성립하지 않는다는걸 알 수 있음

import sys

a1, a2 = map(int, sys.stdin.readline().rstrip().split())
c = int(sys.stdin.readline().rstrip())
n0 = int(sys.stdin.readline().rstrip())

if (a1*n0)+a2 <= n0*c and a1<=c:
    print(1)
else:
    print(0)