(매일 BOJ) C++ 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1

이번 문제는 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1이다.

접근법

이 문제는 '이게 왜 브론즈 5 난이도지? 문제가 무슨 말인지 모르겠다.' 라고 생각이 들었던 문제였다.

따라서 이 문제에서 주어진 ManOfPassion 함수를 먼저 해석해보았다. 이 함수는 n을 입력받아서 2로 나누고 버림했을 때 나오는 정수를 Index로 하고 있었다. 이는 A[]라는 배열의 Indexing 값을 구하고 이를 return 하라는 의미이다. 

그리고 문제에서는 이 함수의 수행 횟수를 출력하라고 했기 때문에 이 문제는 시간복잡도를 구하라는 문제임을 알 수 있다

 

따라서 이를 간파했다면 이 함수는 입력값을 받아서 배열의 index 값을 출력하는 함수이므로 입력이 커지더라도 1번 실행하는 것을 알 수 있다. 따라서 첫줄에서는 무조건 1을 출력하게 된다.

 

또한 O(1) 의 시간복잡도를 가지기에 이는 상수항이므로 차수는 항상 0이 됨을 볼 수 있다. 따라서 두번째 줄은 무조건 0을 출력할 것이다.

 

시간복잡도에 대한 내용을 더 알아보고 싶다면 이글을 정독해보자.

 

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

 

작성코드

# include <bits/stdc++.h>
using namespace std;


int main(void){
    ios::sync_with_stdio(0); cin.tie(0);
    cout << 1 << '\n' << 0;
}