백준 알고리즘 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1 (C++/C언어)

브론즈Ⅴ

 

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

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

 

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	4911	3803	3530	78.936%

 

문제

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

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

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

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

 

 

입력

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

출력

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

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

 

예제 입력 1 복사

1

예제 출력 1 복사

1
0

 

코드1 이 1회 수행되고 알고리즘은 상수 시간이 소요된다.

 

풀이 방법

반응형

이 문제는 주어진 MenOfPassion 알고리즘 속 코드1(return A[i])의 수행 횟수와 수행횟수를 다항식으로 나타냈을 때의 최고차항의 차수를 출력하는 문제입니다. 

 

MenOfPassion 함수는 배열 A와 정수 n을 인자로 전달받아 생성된 정수형 변수에 n의 값을 2로 나눈 후 소수점 아래를 버리고 정수형으로 변환하여 변수 i에 리스트 형태로 저장한 후 A의 i번째 인덱스에 저장된 값을 return하는 함수입니다.

 

이 함수가 실행될 때 'return A[i];' 는 입력값 n이 몇이든 한번만 실행 된다는 사실을 알 수 있습니다. 따라서 코드1의 수행 횟수는 매번 1이 되며, 이를 다항식으로 나타내면 '1'이 되므로 최고차항의 차수는 0임을 알 수 있습니다.

 

즉, 이 코드의 시간 복잡도(Time Complexity)를 빅오 표기법(Big-O Notation)으로 나타내면 O(1)임을 알 수 있습니다.

 

내 코드

#include <iostream>
 
using namespace std;
 
int main() {
 
    int n;
 
    cin >> n; //C언어 : scanf("%d",&n);
 
    cout << 1 << '\n' << 0 << '\n'; //C언어 : printf("%d\n%d", 1, 0);
 
    return 0;
}

코드설명

 

코드1의 수행횟수와 코드1을 다항식으로 나타냈을 때의 최고차항의 차수는 n의 값이 몇이든 항상 1과 0이기 때문에 n을 입력 받고 1과 0을 출력하면 된다.