[BOJ / C++] 24262번 : 알고리즘 수업 - 알고리즘의 수행 시간 1

문제

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

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

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

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

입력

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

출력

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

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

Solved.ac 레벨

브론즈 V

풀이

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cout << 1 << '\n' << 0;

    return 0;
}

위의 코드1은 파라미터 n의 값이 어떻든 단 한 번 실행된다. 따라서 첫째 줄에 1을 출력한다.

배열의 탐색은 시간복잡도 O(1)로 상수 시간이 소요되므로 둘째 줄에는 0을 출력한다.

브론즈 V는 단순히 입출력이라 크게 어렵지 않은게 포인트인듯.

 

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