[백준] 24262(알고리즘 수업 - 알고리즘의 수행 시간 1) C, Python

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

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

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

입력

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

출력

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

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

---

목표 : 알고리즘 수행 횟수 분석 (시간복잡도 분석)

주어진 MenOfPassion 함수의 수행 횟수와 그에 해당하는 시간 복잡도의 최고차항 차수를 출력한다. 

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

MenOfPassion : 배열의 중간 원소 하나 반환 

• 실제 연산은 한번만 일어난다. → 배열 접근 
• 코드1은 항상 1번만 실행되며 시간 복잡도는 입력 크기 n에 상관없이 항상 1회 수행되므로 O(1)이다. 즉, 최고차항의 차수는 0이다. 

 

문제에 '단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.'고 되어 있는데, 

MenOfPassion 함수는 무조간 한 번만 실행되므로 조건에 해당될 수 없다.

• n에 관계없는 상수 수행 시간 다항식으로 표현 → f(n) = 1
• 차수가 0인 다항식이므로 최고차항 차수는 0

 

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    // 문제의 알고리즘은 항상 A[n/2] 한 번 접근하는 구조이므로,
    // 코드1 수행 횟수는 항상 1이고, 시간 복잡도는 O(1), 즉 차수는 0
    printf("1\n");    // 코드1의 실제 수행 횟수
    printf("0\n");    // 다항식 최고차항의 차수

    return 0;
}

a = int(input())

print(1)
print(0)

 

문제 접근 방법

이런 유형의 문제는 처음이라 지피티한테 어떻게 접근해야 하는지 물어봤다..